package programming.set7.sudoku;

/**
 * Implements a simple backtracking-based Sudoku solver. We start at the
 * top-leftmost non-empty cell and start filling it with numbers. If we find a
 * valid number to put in there, we assume it to be fixed and do the same with
 * the next non-empty field. As soon as we discover that the instance is not
 * solvable with our number, we immediately change to the next valid number and
 * do it all over.
 */
public class SudokuSolver {

	/** The Sudoku to be solved. */
	private Sudoku sudoku = null;

	/**
	 * Creates a new instance to solve the given Sudoku.
	 *
	 * @param s the Sudoku to solve.
	 */
	public SudokuSolver(Sudoku s) {
		// Make a copy of the Sudoku
		sudoku = new Sudoku();

		for (int row = 0; row < 9; row++) {
			for (int col = 0; col < 9; col++) {
				sudoku.setValueAt(row, col, s.getValueAt(row, col));
			}
		}
	}

	/**
	 * Attempts to solve the Sudoku.
	 */
	public void solve() {
		solveFrom(0);
	}

	/**
	 * Solves the Sudoku by trying values for the cell with the given index and
	 * seeing what happens. The cells are numbered starting with 0 for the top-left
	 * cell and iterating in row-major order.
	 *
	 * @param cell the cell index.
	 * @return {@code true} if we found a solution, {@code false} otherwise.
	 */
	private boolean solveFrom(int cell) {
		// Calculate the row and column from the cell index
		int col = cell % 9;
		int row = cell / 9;

		// If we're out of range, we're done
		if (row > 8) {
			return sudoku.isValid();
		}

		// If the Sudoku is currently invalid, don't even start
		if (!sudoku.isValid()) {
			return false;
		}

		if (sudoku.getValueAt(row, col) != Sudoku.EMPTY) {
			// The cell is not empty, so jump to the next
			return solveFrom(cell + 1);
		} else {
			// The cell is empty, so start trying things
			for (int number = 1; number <= 9; number++) {
				sudoku.setValueAt(row, col, number);

				// If this call returns true, we've found a solution
				if (solveFrom(cell + 1)) {
					return true;
				}
			}

			sudoku.setValueAt(row, col, Sudoku.EMPTY);

			// We haven't found a solution
			return false;
		}
	}

	/**
	 * Checks whether the Sudoku was solved or not. A Sudoku is solved if it is
	 * valid and has no empty cells.
	 *
	 * @return {@code true} if the Sudoku was already solved.
	 */
	public boolean isSolved() {
		if (!sudoku.isValid()) {
			return false;
		}

		// Check if all cells are non-empty
		for (int row = 0; row < 9; row++) {
			for (int col = 0; col < 9; col++) {
				if (sudoku.getValueAt(row, col) == NumberBoard.EMPTY) {
					return false;
				}
			}
		}

		return true;
	}

	/**
	 * Returns the solved Sudoku instance.
	 *
	 * @return the solved Sudoku, or {@code null} if the Sudoku wasn't solved (yet).
	 */
	public Sudoku getSolution() {
		return isSolved() ? sudoku : null;
	}

}