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

public class SudokuSolver {
    
    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;
        
        ///////////////////
        // ADD CODE HERE //
        ///////////////////
        
    }
    
    private class State implements StateAllowingBacktracking<Choice> {
    
        ///////////////////
        // ADD CODE HERE //
        ///////////////////
        
        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;
        }

    }
    
    int boardSize;
    StateAllowingBacktracking<Choice> state;
    private Stack<String> stackOfSolutions;
    
    int cnt = 0;
    
    public SudokuSolver(int[][] grid) {

        state = new State(grid);
        stackOfSolutions = new Stack<String>();
    }
    
    void searchFromCurrentState() {
        
        if (state.isSolution()) {
            //System.out.println("solution found!!");
            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);
        }
        
    }
}