Key for colors
Backtracking
AC-3, solved
AC-3, value may change
Backtracking
AC-3, solved
AC-3, value may change
A Sudoku board is made up of a 9x9 grid of 81 boxes. The grid includes 9 subgrids of size 3x3.
The board starts with preset or "fixed" numbers that cannot be changed. The player's task is to solve the puzzle by filling in the remaining boxes.
The puzzle is solved when each of the 81 boxes contain an integer between 1 and 9, and all of the integers 1-9 appear in every row, column, and 3x3 subgrid of the board.
Sudoku is a type of Constraint Satisfaction Problem, or CSP. The solver uses the Arc Consistency Algorithm #3 ( AC-3), and backtracking with the Minimum Remaining Values and degree heuristics.
To use AC-3, first every box of the cell is given a domain of possible integers 1-9, with the exception of the boxes with fixed starting values. For fixed boxes, the domain consists of the fixed value.
Next, a list of constraints is created for each box. For example, the box at (row, column) = (1,1) must not have the same value as any box in its row (e.g. the boxes at (1,1), (1,2), ... (1,9)), any box in its column (i.e. (2,1), (3,1), ... (9,1)), or any box in its subgrid (i.e. (1,2), (1,3), (2,1), (2,2), (2,3) (3,1), (3,2), (3,3)). Leaving out repeats, these represent the 20 constraints for box (1,1).
AC-3 progresses by going through the list of constraints one by one. For each box xi and constraining box xj, if there is a single value in the domain of xj, that value is removed from the domain of xi. If this causes the domain of xi to contain only a single value, then a new set of "reverse constraints" is added to the list of constraints, to be worked through. For the reverse constraints, the box that was previously xi becomes the constraining box xj for all the boxes that share its row, column, and subgrid.
After all the constraints have been worked through, the puzzle may not be completely solved. Thus AC-3 is not necessarily sufficient to find a solution, if one exists. In this case, another method is needed.
Backtracking uses a trial-and-error approach to solve the puzzle. For an empty Sudoku box, a value is selected from the domain of allowable values. These can be chosen randomly, in order, or using a heuristic as described below.
The guess value is placed in the box and used to constrain the boxes that share the row, column, and subgrid. The process is repeated for another empty Sudoku box, new constraints are accounted for, and so on.
This continues until either the puzzle is solved, or a box is found to have no allowable value (because all values 1-9 are already present in the row, column, and subgrid).
If there is no allowable value, the algorithm "backtracks" to the last box that had multiple values in its domain, emptying boxes as it backs up. A different value from the domain is tried, and the algorithm proceeds forward again for as long as it can. Because of the need to undo changes when the algorithm backtracks, recursion is generally used.
Backtracking can be used alone or with another method like AC-3. For example, if AC-3 gets stuck, backtracking can take over. Unlike AC-3, backtracking can almost always solve a Sudoku puzzle if it is solveable.
To speed up the solver, a heuristic can be used. A heuristic is a problem-solving technique "that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, short-term goal or approximation". Useful heuristics for Sudoku include:
The Minimum Remaining Values (MRV) heuristic speeds up the sover by choosing the next box to solve by identifying the box with the shortest list of allowable values.
The degree heuristic speeds up the solver by choosing the value involved in the largest number of constraints with remaining unassigned values.