# Aart Bik's Sudoku Solver Page

A Sudoku puzzle
consists of placing the numbers 1 through 9 into the cells
of a 9x9 grid divided into nine 3x3 regions, where some cells
already contain numbers (called the "givens" or "clues"),
such that eventually every row, every column and every
region contains each of the numbers 1 through 9 exactly once.
For more information on Sudoku, see
The Sudoku Programmers Forum
or Solving Sudoku.

# Sudoku Solver

Aart Bik
wrote a simple Sudoku solver in C that will
find all solutions for any given initial placement of numbers
on the grid or report that no solution is possible (even
though a pure Sudoku puzzle should always have exactly one solution).
In the standard mode, the solver simply reports solutions,
while in the verbose mode, the solver also explains which
steps are taken. Sample output is shown below.
To reduce state space search, the solver
always proceeds with a cell that has a minimum set
of candidates. After some hand-optimization and when compiled with
the Intel® C++ compiler,
the solver can search the state space up to over 20 million
nodes-per-second on a 3.4GHz Pentium 4 processor. Due to the
simplicity of state space pruning, the solver typically considers
many more nodes than more 'intelligent' solvers with lower
nodes-per-second rating, which can easily nullify all gains
obtained by the fast search.
Fast search still seems to have some potential in filtering out
multi-solution puzzles, where it is not as clear yet which
kind of solver performs better.
### Sample Output

In the verbose mode, the solver explains each step with a
`must-be`, when there is a unique candidate,
or a `try`, when only
non-singleton sets of candidates appear
(under the simple pruning rules used by this solver) and, hence,
backtracking is required. A `dead-end` indicates the end of a trial
for which no further solutions are possible. The notation `x,y = z` is
used as a shorthand for placing the number `z` on the
cell at row `x` and column `y` (with `1,1` top-left
and `9,9` bottom-right).
PROBLEM:
+---+---+---+
|...|4..|5..|
|...|27.|.8.|
|..6|..8|..4|
+---+---+---+
|3..|6..|4..|
|.4.|.5.|.7.|
|..2|..9|..6|
+---+---+---+
|2..|9..|7..|
|.8.|.3.|.5.|
|154|762|..8|
+---+---+---+
must-be 7,3 = 3
must-be 7,2 = 6
must-be 7,9 = 1
must-be 7,8 = 4
must-be 7,5 = 8
must-be 7,6 = 5
must-be 8,4 = 1
must-be 8,6 = 4
try 1,5 = 1 from {19}:#2
must-be 3,5 = 9
must-be 4,5 = 2
must-be 6,5 = 4
try 8,9 = 2 from {29}:#2
try 9,8 = 3 from {39}:#2
must-be 9,7 = 9
must-be 6,8 = 1
must-be 8,7 = 6
must-be 3,8 = 2
must-be 4,8 = 9
must-be 1,8 = 6
must-be 1,6 = 3
must-be 5,9 = 3
must-be 6,7 = 8
must-be 5,6 = 1
must-be 5,4 = 8
must-be 5,3 = 9
must-be 5,1 = 6
must-be 4,9 = 5
must-be 6,2 = 7
must-be 4,6 = 7
must-be 8,3 = 7
must-be 1,3 = 8
must-be 4,2 = 1
must-be 6,4 = 3
dead-end 4,3 = ?
try 9,8 = 9 from {39}:#2
must-be 4,8 = 1
must-be 4,6 = 7
must-be 4,2 = 9
must-be 8,7 = 6
must-be 6,8 = 3
must-be 6,4 = 8
must-be 3,8 = 2
must-be 1,8 = 6
must-be 5,9 = 9
must-be 2,9 = 3
must-be 3,7 = 1
must-be 5,4 = 3
must-be 1,9 = 7
must-be 2,2 = 1
must-be 4,9 = 5
must-be 4,3 = 8
must-be 5,3 = 1
must-be 9,7 = 3
must-be 1,3 = 9
must-be 1,1 = 8
dead-end 6,7 = ?
try 8,9 = 9 from {29}:#2
must-be 8,3 = 7
must-be 9,8 = 3
dead-end 8,1 = ?
try 1,5 = 9 from {19}:#2
must-be 3,5 = 1
must-be 6,5 = 4
must-be 4,5 = 2
try 4,8 = 1 from {19}:#2
must-be 6,8 = 3
must-be 6,7 = 8
must-be 9,8 = 9
must-be 4,6 = 7
must-be 4,2 = 9
must-be 8,9 = 2
must-be 8,7 = 6
dead-end 6,4 = ?
try 4,8 = 9 from {19}:#2
must-be 4,9 = 5
must-be 9,8 = 3
must-be 9,7 = 9
must-be 6,8 = 1
must-be 6,2 = 7
must-be 4,2 = 1
must-be 8,9 = 2
must-be 8,7 = 6
must-be 3,8 = 2
must-be 1,8 = 6
must-be 1,6 = 3
must-be 1,2 = 2
must-be 3,7 = 3
must-be 2,9 = 9
must-be 1,9 = 7
must-be 2,2 = 3
must-be 4,6 = 7
must-be 4,3 = 8
must-be 5,3 = 9
must-be 8,3 = 7
must-be 1,3 = 1
must-be 1,1 = 8
must-be 8,1 = 9
must-be 3,4 = 5
must-be 3,2 = 9
must-be 3,1 = 7
must-be 5,6 = 1
must-be 2,7 = 1
must-be 2,6 = 6
must-be 2,3 = 5
must-be 5,9 = 3
must-be 5,4 = 8
must-be 6,4 = 3
must-be 6,1 = 5
must-be 5,7 = 2
must-be 6,7 = 8
must-be 2,1 = 4
must-be 5,1 = 6
SOLUTION:
+---+---+---+
|821|493|567|
|435|276|189|
|796|518|324|
+---+---+---+
|318|627|495|
|649|851|273|
|572|349|816|
+---+---+---+
|263|985|741|
|987|134|652|
|154|762|938|
+---+---+---+
#PUZZLES=1 #SOLUTIONS=1

Please note that this page is privately maintained by
Aart Bik.