Sudoku is a well-known puzzle involving a 9x9 grid filled with the digits 1-9 such that no row, column, or 3x3 subgrid contains any repeats. A Sudoku solver is a targeted constraint satisfiability solver (similar to boolean SAT solvers). In particular, such a solver relies heavily upon constraint propagation to identify solutions for every stage of the board.

A board may be viewed as a grid of "solved" numbers and "potential" numbers for each position. At the start, every position is either "solved" (provided by the initial puzzle) or has the full range of digits (1-9) potentially available. The "solved" numbers are then iterated over to constrain the "potential" value of every position in the same row, column, or square. Any positions with only "potential" solution are then marked "solved" with the remaining number and the process is repeated. For example, the middle-most position is constrained in-row by [1,3,4,8], in-column [1,2,6,7,8,9], and in-square by [2,3,6,8] which leaves a potential set of [5].

These "explicit" constraints solve most simple Sudoku puzzles, but harder puzzles require another insight. It is also possible to constrain values through implied constraints. These constraints apply where the exact position of a value isn't known, but the possibilities within one square are sufficient to constrain the rest of a row or column. For example, the bottom-middle square must have a 6 in the bottom row, which precludes a 6 in the bottom-right square's bottom-row.

The combination of explicit and implicit constraints is sufficient to solve any well-posed Sudoku puzzles (boards with only one solution). Very hard squares may not have a unique solution however, so a comprehensive solver also requires a brute force solver. The brute force solver is used when the application of all constraints provides only "potential" sets of more than 1 element each.

Click here to try it online

Code available on Github