/**
 * Class that solves the Asterisk Sudoku.
 * Prints the number of solutions of a Sudoku if there are multiple. If there is only a single solution, prints this solution instead.
 * <p>
 * by Eric Abraham, ID: 1408828
 * and Ilke Yilmaz, ID: 1410067
 * as group 21
 * 30/09/2019
 */
class SudokuSolver {

    int SUDOKU_SIZE = 9;          // Size of the grid.
    int SUDOKU_MIN_NUMBER = 1;    // Minimum digit to be filled in.
    int SUDOKU_MAX_NUMBER = 9;    // Maximum digit to be filled in.
    int SUDOKU_BOX_DIMENSION = 3; // Dimension of the boxes (sub-grids that should contain all digits).
    boolean[] asteriskArray = new boolean[10]; //array used to determine whether the value at position has already been used

    int[][] grid = new int[][]{  // The puzzle grid; 0 represents empty.
            {0, 9, 0, 7, 3, 0, 4, 0, 0},    // One solution.
            {0, 0, 0, 0, 0, 0, 5, 0, 0},
            {3, 0, 0, 0, 0, 6, 0, 0, 0},

            {0, 0, 0, 0, 0, 2, 6, 4, 0},
            {0, 0, 0, 6, 5, 1, 0, 0, 0},
            {0, 0, 6, 9, 0, 7, 0, 0, 0},

            {5, 8, 0, 0, 0, 0, 0, 0, 0},
            {9, 0, 0, 0, 0, 3, 0, 2, 5},
            {6, 0, 3, 0, 0, 0, 8, 0, 0},
    };
    char[][] charAfter = new char[][]{ //used to properly print grid
            {' ', ' ', '|', ' ', ' ', '|', ' ', ' ', '|'},
            {' ', ' ', '|', '>', '<', '|', ' ', ' ', '|'},
            {' ', '>', '|', ' ', ' ', '|', '<', ' ', '|'},

            {' ', ' ', '|', ' ', ' ', '|', ' ', ' ', '|'},
            {'>', '<', '|', '>', '<', '|', '>', '<', '|'},
            {' ', ' ', '|', ' ', ' ', '|', ' ', ' ', '|'},

            {' ', '>', '|', ' ', ' ', '|', '<', ' ', '|'},
            {' ', ' ', '|', '>', '<', '|', ' ', ' ', '|'},
            {' ', ' ', '|', ' ', ' ', '|', ' ', ' ', '|'},
    };
    int[][] solution = new int[SUDOKU_SIZE][SUDOKU_SIZE]; //solution grid

    int solutionCounter = 0; // Solution counter

    // Is there a conflict when we fill in d at position (r, c)?
    boolean givesConflict(int r, int c, int d) {
        // TODO
        if (rowConflict(r, d) || columnConflict(c, d) || boxConflict(r, c, d) || asteriskConflict(r, c, d)) {
            return true;
        }
        return false;
    }

    // Is there a conflict when we fill in d in row r?
    boolean rowConflict(int r, int d) {
        // TODO
        for (int i = 0; i < SUDOKU_SIZE; i++)
            if (grid[r][i] == d) {
                return true;
            }
        return false;

    }

    // Is there a conflict in column c when we fill in d?
    boolean columnConflict(int c, int d) {
        for (int i = 0; i < SUDOKU_SIZE; i++)
            if (grid[i][c] == d) {
                return true;
            }
        return false;
    }

    // Is there a conflict in the box at (r, c) when we fill in d?
    boolean boxConflict(int r, int c, int d) {
        for (int i = r / 3 * 3; i < r / 3 * 3 + 3; i++)
            for (int j = c / 3 * 3; j < c / 3 * 3 + 3; j++)
                if (grid[i][j] == d)
                    return true;
        return false;
    }

    void initializeAsteriskArray() {
        for (int i = SUDOKU_MIN_NUMBER; i <= SUDOKU_MAX_NUMBER; i++)
            asteriskArray[i] = false;
        for (int i = 0; i < SUDOKU_SIZE; i++)
            for (int j = 0; j < SUDOKU_SIZE; j++)
                if (isAsteriskPosition(i, j))
                    asteriskArray[grid[i][j]] = true;
    }

    boolean isAsteriskPosition(int r, int c) {
        if (r == 2 && (c == 2 || c == 6))
            return true;
        if (r == 4 && (c == 1 || c == 4 || c == 7))
            return true;
        if (r == 6 && (c == 2 || c == 6))
            return true;
        if (r == 7 && c == 4)
            return true;
        if (r == 1 && c == 4)
            return true;
        return false;
    }

    boolean asteriskConflict(int r, int c, int d) {
        initializeAsteriskArray(); //refreshes AsteriskArray in order to properly determine conflict
        if (asteriskArray[d] && isAsteriskPosition(r, c))
            return true;
        return false;
    }

    // Finds the next empty square (in "reading order").
    int[] findEmptySquare() {
        // TODO
        for (int i = 0; i < SUDOKU_SIZE; i++)
            for (int j = 0; j < SUDOKU_SIZE; j++)
                if (grid[i][j] == 0)
                    return new int[]{i, j};
        return new int[]{-1, -1};
    }

    void copyGrid() { //copies grid, ready to be printed as solution

        for (int i = 0; i < SUDOKU_SIZE; i++)
            for (int j = 0; j < SUDOKU_SIZE; j++)
                solution[i][j] = grid[i][j];
    }

    // Find all solutions for the grid, and stores the final solution.
    void solve() {
        int[] index = findEmptySquare(); //searches for next empty space
        if (index[0] != -1 && index[1] != -1) {
            for (int i = SUDOKU_MIN_NUMBER; i <= SUDOKU_MAX_NUMBER; i++)
                if (!givesConflict(index[0], index[1], i)) {
                    grid[index[0]][index[1]] = i;
                    solve();
                    grid[index[0]][index[1]] = 0; //when solve 'returns' we are done with our current i of the for
                }
        } else {
            solutionCounter++; //if there is no empty space, we found a solution
            if (solutionCounter == 1) {
                copyGrid();
            }
        }
    }

    // Print the sudoku grid.
    void print() {
        System.out.println("+-----------------+");
        for (int i = 0; i < 9; i++) {
            System.out.print("|");
            for (int j = 0; j < 9; j++) {
                System.out.print(solution[i][j]);
                System.out.print(charAfter[i][j]);
            }

            System.out.print("\n");
            if (i == 2 || i == 5) {
                System.out.println("+-----------------+");
            }
        }
        System.out.println("+-----------------+");

    }

    // Run the actual solver.
    void solveIt() {
        solve();
        if (solutionCounter == 1)
            print();
        else
            System.out.println(solutionCounter);
    }

    public static void main(String[] args) {
        (new SudokuSolver()).solveIt();
    }
}