/**
 * A program to solve "easy" Sudoku puzzles. Used as a CIT591 assignment
 * during the Fall of 2007. This class provides all the necessary computation,
 * but control and printing are handled by the SudokuSolver class.
 * 
 * @author Dave Matuszek
 * @version Oct 18, 2007
 */
class Sudoku {
    private int[][] problem;

    /**
     * Takes a 9x9 array of numbers and sets it up as a Sudoku problem. Zeros
     * in the array indicate places to be filled in.
     * 
     * @param problem The array representing the Sudoku problem.
     */
    public Sudoku(int[][] problem) {
        this.problem = problem;
    }


    /**
     * Solves this Sudoku problem, and returns the solution.
     * 
     * @return The 9x9 array representing the solution.
     */
    public int[][] solve() {
        int[][] solution = problem;
        boolean makingProgress = true;
        int digit;
        
        while (makingProgress) {
            makingProgress = false;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (solution[i][j] > 0) continue; // already filled in
                    digit = getOnlyPossibleDigit(i, j);
                    if (digit != 0) {
                        solution[i][j] = digit;
                        makingProgress = true;
                    }
                }
            }
        }
        return solution;
    }

    /**
     * Returns a 3x3 array representing a "box" of the 9x9 array. The parameters
     * boxRow and boxColumn are in the range 0 to 2, since there are three rows and
     * three columns of "boxes."
     * 
     * @param boxRow The row number, 0, 1, or 2.
     * @param boxColumn  The column number, 0, 1, or 2.
     * @return The indicated 3x3 subarray of th
     */
    int[][] getBox(int boxRow, int boxColumn) {
        int[][] box = new int[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                box[i][j] = problem[3 * boxRow + i][3 * boxColumn + j];
            }
        }
       return box;
    }

    /**
     * Returns true if the given digit (which must be 1..9) occurs in the given row
     * (rows are 0..8), and false otherwise.
     * 
     * @param digit The digit to be searched for in the given row.
     * @param row The row to search.
     * @return <code>true</code> if the digit is found.
     */
    boolean occursInRow(int digit, int row) {
        for (int column = 0; column < problem[row].length; column++) {
            if (problem[row][column] == digit) return true;
        }
        return false;
    }

    /**
     * Returns true if the given digit (which must be 1..9) occurs in the given
     * column (columns are 0..8), and false otherwise.
     * 
     * @param digit The digit to be searched for in the given column.
     * @param column The column to search.
     * @return <code>true</code> if the digit is found.
     */
    boolean occursInColumn(int digit, int column) {
        for (int row = 0; row < problem.length; row++) {
            if (problem[row][column] == digit) {
                return true;
            }
        }
        return false;
    }

    /**
     * Returns true if the given digit (which must be 1..9) occurs in the box
     * containing the location at the given row and column of the 9x9 array, and
     * false otherwise. Note that this method is given a row and column in the
     * complete 9x9 array, but must search for the given digit in the box containing
     * that (row, column) location.
     * 
     * @param digit The digit to be searched for in the appropriate box.
     * @param row A row number in the range 0 to 8.
     * @param column  A column number in the range 0 to 8.
     * @return <code>true</code> if the given digit is found in the same box
     *  that contains the given row and column.
     */
    boolean occursInBox(int digit, int row, int column) {
        int rowStart = (row / 3) * 3;
        int columnStart = (column / 3) * 3;
        for (int i = rowStart; i < rowStart + 3; i++) {
            for (int j = columnStart; j < columnStart + 3; j++) {
                if (problem[i][j] == digit) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Returns true if the given digit (which must be 1..9) occurs in the given 3x3
     * box, and false otherwise.
     *
     * @param digit The digit to search for.
     * @param box A 3x3 array in in which to search.
     * @return <code>true</code> if the given digit is found.
     */
    boolean occursInBox(int digit, int[][] box) {
        for (int i = 0; i < box.length; i++) {
            for (int j = 0; j < box[i].length; j++) {
                if (box[i][j] == digit) return true;
            }
        }
        return false;
    }

    /**
     * Returns true if the given digit (which must be 1..9) does not occur in the
     * given row, or in the given column, or in the box containing this row and
     * column, and false otherwise. That is, this digit is a possible candidate for
     * putting in this location; there may be other candidates.
     * 
     * @param digit The candidate digit.
     * @param row The row in which we wish to place the digit.
     * @param column  The column in which we wish to place the digit.
     * @return <code>true</code> if the candidate digit does not already occur
     *         in the same row, or in the same column, or in the same box. 
     */
    boolean isPossibleDigit(int digit, int row, int column) {
        // Test column
        if (occursInColumn(digit, column)) {
            return false;
        }
        // Test row
        if (occursInRow(digit, row)) {
            return false;
        }
        // Test 3x3 box
        return !occursInBox(digit, row, column);
    }

    /**
     * Returns true if the given digit can be put in the given row and column, and
     * no other digit can be put there; returns false otherwise.
     * 
     * @param digit The digit we wish to place.
     * @param row The row in which we wish to place the digit.
     * @param column The column in which we wish to place the digit.
     * @return <code>true</code> if this digit, and only this digit, can be so placed.
     */
    boolean isOnlyPossibleDigit(int digit, int row, int column) {
        if (!isPossibleDigit(digit, row, column)) return false;
        for (int d = 1; d <= 9; d++) {
            if (d == digit) continue;
            if (isPossibleDigit(d, row, column)) {
                return false;
            }
        }
        return true;
    }
    /**
     * If the rules of Sudoku allow only one particular digit to be placed in the
     * given (row, column) location, return that digit, else return zero.
     * 
     * @param row The row for which we wish to find the correct digit.
     * @param column  The column for which we wish to find the correct digit.
     * @return The correct digit, if it is the only possible digit; otherwise zero.
     */
    int getOnlyPossibleDigit(int row, int column) {
        for (int digit = 1; digit <= 9; digit++) {
            if (isOnlyPossibleDigit(digit, row, column)) {
                return digit;
            }
        }
        return 0;
    }
}