import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class SudokuSolver {
    
    ///////////////////
    // INNER CLASSES //
    ///////////////////
    
    private class Position {
        public int row;  // note, given the simplicity of this inner Position class, we violate
        public int col;  // our normal practice of keeping instance variables private
        
        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    
    private class Choice {
        
        private int digit;
        
        private Choice(int digit) {
            this.digit = digit;
        }
        
        public boolean equals(Object o) {
            return (o != null) && (o instanceof Choice) && ((Choice) o).digit == this.digit;
        }
        
        public String toString() {
            return ("" + this.digit);
        }
        
    }
    
    private class State implements StateAllowingBacktracking<Choice> {
        
        private Choice[][] grid;
        private boolean[][] editable;
        private int size = 0;
        private Position nextChoicePosition;
        private int capacity = 0;
        
        public State(int[][] grid) {
            int n = grid.length;
            this.grid = new Choice[n][n];
            editable = new boolean[n][n];
            boolean nextChoicePositionFound = false;
            
            
            for (int row = 0; row < n; row++) {
                for (int col = 0; col < n; col++) {
                    this.grid[row][col] = new Choice(grid[row][col]);
                    editable[row][col] = (this.grid[row][col].digit == 0);
                    if (editable[row][col]) {
                        capacity++;
                        if (! nextChoicePositionFound) {
                            nextChoicePosition = new Position(row,col);
                            nextChoicePositionFound = true;
                        }
                    }
                }
            }
        }
        
        private Position nextEditableAfter(Position currentPos) {
            int r = currentPos.row;
            int c = currentPos.col;
            int n = grid.length;
            int pos = r*n+c;
            boolean posFound = false;
            while ((! posFound) && (pos < n*n)) {
                pos++;
                if (pos == n*n) 
                    break;
                r = pos / n;
                c = pos % n;
                if (editable[r][c]) {
                    posFound = true;
                    break;
                }
            }
            return (posFound ? new Position(r,c) : null);
        }
        
        private Position previousEditableBefore(Position currentPos) {
            int n = grid.length;
            int r = currentPos.row;
            int c = currentPos.col;
            int pos = r*n+c;
            boolean posFound = false;
            while ((! posFound) && (pos >= 1)) {
                pos--;
                r = pos / n;
                c = pos % n;
                if (editable[r][c]) {
                    posFound = true;
                    break;
                }
            }
            return (posFound ? new Position(r,c) : null);
        }
        
        public String toString() {

            final String CENTER_DOT = "\u00B7";        
            final String VERTICAL_LINE = "\u2503";     //(bold & covers entire width of char and horizontally centered)
            final String HORIZONTAL_LINE = "\u2501";   //(bold & covers entire height of char and vertically centered)
            final String VERT_HORIZ_CROSS = "\u254B";  //(bold & covers entire width and height of char and centered)
            
            // Note: if your terminal doesn't support colored text, try not to be too sad
            // and then change the next two strings to both be empty strings (i.e., "")
            final String ANSI_RESET = "\u001B[0m"; 
            final String ANSI_CYAN = "\u001B[36m";
            
            String s = "";
            for (int r = 0; r < grid.length; r++) {
                for (int c = 0; c < grid[0].length; c++) {
                    if (! editable[r][c]) 
                        s += ANSI_CYAN + grid[r][c] + ANSI_RESET;
                    else
                        s += (grid[r][c].digit != 0 ? grid[r][c] : CENTER_DOT);  
                    if (c == 2 || c == 5)
                        s += VERTICAL_LINE;  
                }
                if (r == 2 || r == 5) 
                    s += "\n" + HORIZONTAL_LINE + HORIZONTAL_LINE + HORIZONTAL_LINE + VERT_HORIZ_CROSS +
                                HORIZONTAL_LINE + HORIZONTAL_LINE + HORIZONTAL_LINE + VERT_HORIZ_CROSS +
                                HORIZONTAL_LINE + HORIZONTAL_LINE + HORIZONTAL_LINE;
                s += "\n";
            }
            return s;
        }
        
        private boolean isInRow(Choice choice) {
            int r = nextChoicePosition.row;
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c].equals(choice)) return true;
            }
            return false;
        }
        
        private boolean isInCol(Choice choice) {
            int c = nextChoicePosition.col;
            for (int r = 0; r < grid.length; r++) {
                if (grid[r][c].equals(choice)) return true;
            }
            return false;
        }
        
        private boolean isInBox(Choice choice) {
            int boxR = (nextChoicePosition.row/3)*3;
            int boxC = (nextChoicePosition.col/3)*3;
            for (int r = boxR; r < boxR+3; r++) {
                for (int c = boxC; c < boxC+3; c++) {
                    if (grid[r][c].equals(choice)) return true;
                }
            }
            return false;
        }
        
        public boolean isSolution() {
            return (size == capacity);
        }                                                              
        
        public List<Choice> nextChoicesToConsider() {
            
            List<Choice> listOfChoices = new ArrayList<Choice>();
            for (int c = 1; c <= 9; c++) {
                listOfChoices.add(new Choice(c));
            }

            return listOfChoices;
        }
        
        public boolean isValid(Choice choice) {
            // returns false when the choice is invalid or otherwise undesirable
            // (false-returning choices will "prune" the search tree)
            if (choice.digit > 9) return false;
            if (nextChoicePosition == null) return false;
            boolean inRow = isInRow(choice);  
            boolean inCol = isInCol(choice);
            boolean inBox = isInBox(choice);
            return (!(inRow | inCol | inBox));
        }
        
        public void makeChoice(Choice choice) {
            grid[nextChoicePosition.row][nextChoicePosition.col] = choice; 
            nextChoicePosition = nextEditableAfter(nextChoicePosition); 
            if (nextChoicePosition == null) {
                nextChoicePosition = (editable[0][0] ? (new Position(0,0)) : nextEditableAfter(new Position(0,0)));
            }
            size++;
        }
        
        public void undoChoice(Choice choice) {
            if (size == 0) throw new RuntimeException();
            Position pos = previousEditableBefore(nextChoicePosition);
            if (pos == null) {
                int n = grid.length;
                pos = (editable[n-1][n-1] ? (new Position(n-1,n-1)) : previousEditableBefore(new Position(n-1,n-1)));
                size--;
            }
            else {
                grid[pos.row][pos.col] = new Choice(0);  
                nextChoicePosition = pos;
                size--;
            }
        }
        
    }
    
    ////////////////////////
    // INSTANCE VARIABLES //
    ////////////////////////
    
    int boardSize;
    StateAllowingBacktracking<Choice> state;
    private Stack<String> stackOfSolutions;
    
    int cnt = 0;
    /////////////////
    // CONSTRUCTOR //
    /////////////////
    
    public SudokuSolver(int[][] grid) {

        state = new State(grid);
        stackOfSolutions = new Stack<String>();
    }
    
    //////////////////////
    // INSTANCE METHODS //
    //////////////////////
    
    void searchFromCurrentState() {
        
        if (state.isSolution()) {
            reactToSolution();
            return; // stop pursuing this path
        }
        
        for (Choice choice : state.nextChoicesToConsider()) {
            if (state.isValid(choice)) {
                state.makeChoice(choice);
                searchFromCurrentState();  // <-- the recursive call!
                state.undoChoice(choice);  // try another path
            }
        }
    }
    
    public void reactToSolution() {
        stackOfSolutions.push(state.toString());
    }
    
    public static void main(String[] args) {
        int[][] solvableGrid = {{0,3,9,0,0,0,7,0,0},
                                {0,0,0,7,0,0,1,0,0},
                                {6,0,0,0,8,0,0,0,4},
                                {8,0,4,0,0,7,0,0,6},
                                {0,0,0,8,0,0,4,0,0},
                                {0,5,0,2,0,6,8,1,0},
                                {0,0,0,0,0,0,0,7,0},
                                {5,8,0,0,0,3,9,4,0},
                                {7,2,3,4,0,8,6,0,0}}; 

        SudokuSolver sudokuSolver = new SudokuSolver(solvableGrid);
        System.out.println("NEW PUZZLE:\n\n" + sudokuSolver.state);
        sudokuSolver.searchFromCurrentState();
        System.out.println(sudokuSolver.stackOfSolutions.size() + " solutions(s) found:\n");
        for ( String solution : sudokuSolver.stackOfSolutions) {
            System.out.println(solution);
        }   

        
        System.out.println("-----------------\n");

        int[][] unsolvableGrid = {{3,1,6,5,7,8,4,2,0},
                                  {5,2,0,0,0,0,0,0,0},
                                  {0,8,7,0,0,0,0,3,1},
                                  {0,0,3,0,1,0,0,8,0},
                                  {9,0,0,8,6,3,0,0,5},
                                  {0,5,0,0,9,0,6,0,0},
                                  {1,3,0,0,0,0,2,5,0},
                                  {0,0,0,0,0,0,0,7,4},
                                  {0,0,5,2,0,6,3,0,0}};

        sudokuSolver = new SudokuSolver(unsolvableGrid);
        System.out.println("NEW PUZZLE:\n\n" + sudokuSolver.state);
        sudokuSolver.searchFromCurrentState();
        System.out.println(sudokuSolver.stackOfSolutions.size() + " solutions(s) found:\n");
        for ( String solution : sudokuSolver.stackOfSolutions) {
            System.out.println(solution);
        }
    }
}