Aart'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. 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. For more information on Sudoku, see The Sudoku Forum, The Sudoku Programmers Forum, or Solving Sudoku.

If you like game engines, visit Aart's Computer Chess Page, Computer Checkers Page, or Computer Reversi Page.

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. LinkedIn