Sudoku Solver
Key for colors
Backtracking
AC-3, solved
AC-3, value may change
| 5 | 3 | 7 | ||||||
| 6 | 1 | 9 | 5 | |||||
| 9 | 8 | 6 | ||||||
| 8 | 6 | 3 | ||||||
| 4 | 8 | 3 | 1 | |||||
| 7 | 2 | 6 | ||||||
| 6 | 2 | 8 | ||||||
| 4 | 1 | 9 | 5 | |||||
| 8 | 7 | 9 |
How to Play
A Sudoku board is made up of a 9x9 grid of 81 cells. The grid includes 9 boxes 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 cells contain an integer between 1 and 9, and all of the integers 1-9 appear in every row, column, and 3x3 box of the board.
How the Solver Works
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.
AC-3
To use AC-3, first every cell is given a domain of possible integers 1-9, with the exception of the cells with fixed starting values. For fixed cells, the domain consists of the fixed value.
Next, a list of constraints is created for each cell. For example, the cell at (row, column) = (1,1) must not have the same value as any cell in its row (e.g. the cells at (1,1), (1,2), ... (1,9)), any cell in its column (i.e. (2,1), (3,1), ... (9,1)), or any cell in its box (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 cell (1,1).
AC-3 progresses by going through the list of constraints one by one. For each cell 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 cell 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
Backtracking uses a trial-and-error approach to solve the puzzle. For an empty cell, 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 cell and used to constrain the cells that share the row, column, and 3x3 box. The process is repeated for another empty cell, new constraints are accounted for, and so on.
This continues until either the puzzle is solved, or a cell 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 cell that had multiple values in its domain, emptying cells 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.
Heuristic
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 are as follows.
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.