• Home
• About Sudoku
  • Mathematics of Sudoku
  • Sudoku by Computer
  • Sudoku Solution Methods
• Sudoku - to the Next Level
• Sudoku Links
• Play

For computer programmers it is relatively simple to build a backtracking search. Typically this would assign a value (say, 1, or the nearest available number to 1) to the first available cell (say, the top left hand corner) and then move on to assign the next available value (say, 2) to the next available cell. This continues until a duplication is discovered in which case the next alternative value is placed in the last field changed. Although far from computationally efficient, this method will find the solution, given sufficient computation time; a standard 9×9 puzzle can typically be "solved" within minutes on a modern home computer running this algorithm. A more efficient program could keep track of potential values for cells, eliminating impossible values until only one value remains for a cell, then filling that cell in and using that information for more eliminations, and so on until the puzzle is solved. This more closely emulates the way a human would solve the puzzle without resorting to guesses.

Coding the search for impossibilities based on contingencies and even multiple contingencies (as would be required for the hardest of Sudoku) is quite complex to construct by hand. However, such complications are unnecessary if all the programmer wishes to do is find a solution efficiently. A more efficient way to find solutions involves the use of finite domain constraint programming. A constraint program requires the programmer only to specify the constraints on the solution (the fact that every number in each row, each column, and each 3×3 subgrid must be unique, and the provided "givens"); the finite domain solver does all the work of propagating additional information about possible values to narrow down the solution space until a unique solution is found. The self-imposed constraints of most Sudoku puzzle publishers even ensures that the backtracking search capabilities of the finite domain solver are not required.

A highly efficient way of solving such constraint problems is the Dancing Links Algorithm, by Donald Knuth. It can be shown that his method can be directly applied to solving Sudoku problems, and counting all possible solutions for most puzzles in milliseconds. This is the method now preferred by many Sudoku programmers, mainly by virtue of its speed. A very fast solver is usually required for most trial-and-error puzzle-creation algorithms.

Elaborate, hand-crafted solvers have been designed that apply scanning and marking up in a manner similar to human solvers. This allows these solvers to estimate the difficulty for a human to find the solution, based on the complexity of the rules required by the computer.