import java.util.*;

/*
 * Encapsulates a Sudoku grid to be solved.
 * CS108 Stanford.
 */
public class Sudoku {

    /**
     * Stores empty rows in the way to easily test possible values of this spot.
     */
    private class Spot implements Comparable{

        // Private variables
        private int row, column, value, curIndex;
        private int[][] grid;
        private List<Integer> nums;

        /**
         * Constructor to create default empty spot on row and column coordinates
         * @param row
         * @param column
         * @param grid
         */
        public Spot(int row, int column, int[][] grid){
            this.grid = grid;
            this.row = row;
            this.column = column;
            this.value = grid[row][column];
            this.curIndex = -1;
            nums = new ArrayList<>();
        }

        /**
         * Checks if the spot is valid with the current value
         * @return
         */
        private boolean isValid(){
            int bigRow = (row / PART) * PART;
            int bigCol = (column / PART) * PART;
            for(int i = 0; i < SIZE; i++)
                if(grid[i][column] == value && i != row || grid[row][i] == value && i != column) {
                    return false;
                }
            for(int i = 0; i < PART; i++)
                for(int j = 0; j < PART; j++)
                    if(grid[bigRow + i][bigCol + j] == value && (bigRow + i != row || bigCol + j != column)) {
                        return false;
                    }
            return true;
        }

        /**
         * Generates possible values that can be assigned to spot
         * for current condition of grid.
         */
        public void findNums(){
            nums.clear();
            for(int i = 1; i <= SIZE; i++){
                setValue(i);
                if(isValid())
                    addNum(i);
            }
            setValue(0);
        }

        /**
         * Picks next possible value from the list generated by findNums
         * Returns false if all values have been tried
         * If number can't be assigned writes 0 in the spot, but returns true
         * @return
         */
        public boolean setNext(){
            if(++curIndex >= nums.size()) {
                curIndex = -1;
                setValue(0);
                return false;
            }
            setValue(nums.get(curIndex));
            if(isValid())
                return true;
            setValue(0);
            return true;
        }

        /**
         * Sets value
         * @param value
         */
        private void setValue(int value){
            grid[this.row][this.column] = value;
            this.value = value;
        }

        /**
         * Adds number into possible values
         * @param value
         */
        private void addNum(int value){
            nums.add(value);
        }

        /**
         * Compares two spots
         * @param s
         * @return
         */
        @Override
        public int compareTo(Object s){
            if(s == null) throw new NullPointerException();
            return new Integer(this.nums.size()).compareTo(((Spot)s).nums.size());
        }

        /**
         * Puts linebreak after any string or Object.toString
         * @param o
         * @return
         */
        private String ln(Object o){
            return o + "\n";
        }

        /**
         * Writes object details as String
         * @return
         */
        @Override
        public String toString(){
            String res = "";
            res += ln("[");
            res += ln("\trow: " + row);
            res += ln("\tcolumn: " + column);
            res += ln("\tvalue: " + value);
            res += ln("\tcurIndex: " + curIndex);
            res += ln("\tnums: " + Arrays.toString(nums.toArray()));
            res += ln("]");
            return res;
        }
    }


    // Provided grid data for main/testing
    // The instance variable strategy is up to you.

    // Provided easy 1 6 grid
    // (can paste this text into the GUI too)
    public static final int[][] easyGrid = Sudoku.stringsToGrid(
    "1 6 4 0 0 0 0 0 2",
    "2 0 0 4 0 3 9 1 0",
    "0 0 5 0 8 0 4 0 7",
    "0 9 0 0 0 6 5 0 0",
    "5 0 0 1 0 2 0 0 8",
    "0 0 8 9 0 0 0 3 0",
    "8 0 9 0 4 0 2 0 0",
    "0 7 3 5 0 9 0 0 1",
    "4 0 0 0 0 0 6 7 9");

    public static final int[][] myGrid = Sudoku.stringsToGrid(
    "0 0 0 0 0 0 0 0 0",
    "0 0 0 0 0 0 0 0 0",
    "0 0 0 0 0 0 0 0 0",
    "0 0 0 0 0 0 0 0 0",
    "0 0 0 0 0 0 0 0 0",
    "0 0 0 0 0 0 0 0 0",
    "0 0 0 0 0 0 0 0 0",
    "0 0 0 0 0 0 0 0 0",
    "0 0 0 0 0 0 0 0 0");


    // Provided medium 5 3 grid
    public static final int[][] mediumGrid = Sudoku.stringsToGrid(
     "530070000",
     "600195000",
     "098000060",
     "800060003",
     "400803001",
     "700020006",
     "060000280",
     "000419005",
     "000080079");

    // Provided hard 3 7 grid
    // 1 solution this way, 6 solutions if the 7 is changed to 0
    public static final int[][] hardGrid = Sudoku.stringsToGrid(
    "3 7 0 0 0 0 0 8 0",
    "0 0 1 0 9 3 0 0 0",
    "0 4 0 7 8 0 0 0 3",
    "0 9 3 8 0 0 0 1 2",
    "0 0 0 0 4 0 0 0 0",
    "5 2 0 0 0 6 7 9 0",
    "6 0 0 0 2 1 0 4 0",
    "0 0 0 5 3 0 9 0 0",
    "0 3 0 0 0 0 0 5 1");


    public static final int SIZE = 9;  // size of the whole 9x9 puzzle
    public static final int PART = 3;  // size of each 3x3 part
    public static final int MAX_SOLUTIONS = 100;

    // Provided various static utility methods to
    // convert data formats to int[][] grid.

    /**
     * Returns a 2-d grid parsed from strings, one string per row.
     * The "..." is a Java 5 feature that essentially
     * makes "rows" a String[] array.
     * (provided utility)
     * @param rows array of row strings
     * @return grid
     */
    public static int[][] stringsToGrid(String... rows) {
        int[][] result = new int[rows.length][];
        for (int row = 0; row<rows.length; row++) {
            result[row] = stringToInts(rows[row]);
        }
        return result;
    }


    /**
     * Given a single string containing 81 numbers, returns a 9x9 grid.
     * Skips all the non-numbers in the text.
     * (provided utility)
     * @param text string of 81 numbers
     * @return grid
     */
    public static int[][] textToGrid(String text) {
        int[] nums = stringToInts(text);
        if (nums.length != SIZE*SIZE) {
            throw new RuntimeException("Needed 81 numbers, but got:" + nums.length);
        }

        int[][] result = new int[SIZE][SIZE];
        int count = 0;
        for (int row = 0; row<SIZE; row++) {
            for (int col=0; col<SIZE; col++) {
                result[row][col] = nums[count];
                count++;
            }
        }
        return result;
    }


    /**
     * Given a string containing digits, like "1 23 4",
     * returns an int[] of those digits {1 2 3 4}.
     * (provided utility)
     * @param string string containing ints
     * @return array of ints
     */
    public static int[] stringToInts(String string) {
        int[] a = new int[string.length()];
        int found = 0;
        for (int i=0; i<string.length(); i++) {
            if (Character.isDigit(string.charAt(i))) {
                a[found] = Integer.parseInt(string.substring(i, i+1));
                found++;
            }
        }
        int[] result = new int[found];
        System.arraycopy(a, 0, result, 0, found);
        return result;
    }


    // Provided -- the deliverable main().
    // You can edit to do easier cases, but turn in
    // solving hardGrid.
    public static void main(String[] args) {
        Sudoku sudoku;
        sudoku = new Sudoku(myGrid);

        System.out.println(sudoku); // print the raw problem
        int count = sudoku.solve();
        System.out.println("solutions:" + count);
        System.out.println("elapsed:" + sudoku.getElapsed() + "ms");
        System.out.println(sudoku.getSolutionText());
    }


    // Private variables
    private int[][] grid;
    private int[][] resultGrid;
    private List<Spot> emptySpots;
    private long time;


    /**
     * Sets up based on the given ints.
     */
    public Sudoku(int[][] ints) {
        if(ints.length != SIZE || ints[0].length != SIZE) throw new RuntimeException("Parsing Problem");
        grid = copyGrid(ints);
        emptySpots = new ArrayList<>();
        resultGrid = null;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) {
                    Spot s = new Spot(i, j, grid);
                    emptySpots.add(s);
                    s.findNums();
                }
            }
        }
        Collections.sort(emptySpots);
    }

    /**
     * String constructor
     * @param text
     */
    public Sudoku(String text){
        this(textToGrid(text));
    }


    /**
     * Copies and returns ints grid
     * @param grid
     * @return
     */
    private int[][] copyGrid(int[][] grid){
        int[][] res = new int[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i++)
            System.arraycopy(grid[i], 0, res[i], 0, grid[i].length);
        return res;
    }

    /**
     * Solves sudoku for ith empty spot, assumes that if method is called, everything before it was right
     * @param i
     * @return
     */
    public int solve(int i){
        int res = 0;
        if(i >= emptySpots.size()){
            if(resultGrid == null)
                resultGrid = copyGrid(grid);
            return 1;
        }
        Spot s = emptySpots.get(i);
        s.findNums();
        while(s.setNext()){
//          if(s.value == 0)
//              continue;
            res += solve(i + 1);
            if(res >= MAX_SOLUTIONS) return res;
        }
        return res;
    }

    /**
     * Checks entire board to see if starting grid was bad or not
     * @return
     */
    private boolean checkBoard(){
        for(int i = 0; i < SIZE; i++)
            for(int j = 0; j < SIZE; j++)
                if(grid[i][j] != 0)
                    if(!new Spot(i, j, grid).isValid())
                        return false;
        return true;
    }


    /**
     * Solves the puzzle, invoking the underlying recursive search.
     */
    public int solve() {
        if(!checkBoard())
            throw new RuntimeException("Parsing Problem");
        time = System.currentTimeMillis();
        int res = solve(0);
        time = System.currentTimeMillis() - time;
        return res;
    }

    /**
     * Returns solved puzzle
     * @return
     */
    public String getSolutionText() {
        return gridToString(resultGrid);
    }

    /**
     * Returns time needed to solve puzzle
     * @return
     */
    public long getElapsed() {
        return time;
    }


    /**
     * Returns default grid
     * @return
     */
    @Override
    public String toString(){
        return gridToString(grid);
    }

    /**
     * Makes string from grid
     * @param grid
     * @return
     */
    private String gridToString(int[][] grid){
        String res = "";
        for(int i = 0; i < SIZE; i++){
            for(int j = 0; j < SIZE; j++)
                res = res + grid[i][j] + " ";
            res = res + "\n";
        }
        return res;
    }
}