Sudoku FlowHow computers solve Sudoku
Updated 2026-10-05
Backtracking
The solver tries a legal digit in an empty cell and carries on. If no digit leads to a solution, it undoes an earlier choice and tries another. Choosing the cell with the fewest possible digits first often makes the search much shorter.
Sources: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Exact cover and Dancing Links
Sudoku can be rewritten as an exact cover problem: pick placements so that every cell, and every digit in every row, column and box, is covered exactly once. In a paper from November 2000, Donald Knuth described Dancing Links, an efficient way to run his backtracking Algorithm X; applied to the exact cover model of Sudoku, it finds all solutions of a puzzle quickly.
Sources: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Random search
Some programs fill the grid at random and then shuffle numbers to reduce the number of conflicts, with methods such as simulated annealing or genetic algorithms. They have been studied as alternative approaches; how well they do depends on the program and the puzzle.
Sources: Wikipedia: Sudoku solving algorithms
Solvers that think like people
A hint engine has a different job: not just to find the answer, but to show the next step a person can follow. Our app's engine tries human techniques in a fixed order, from the easiest, such as a hidden single, to the hardest, such as chains and almost locked sets, and uses the first one that leads to a placed digit; the harder ones work by ruling out candidates first. The hardest technique it uses on a puzzle sets that puzzle's level in the app.
Sources: What each Sudoku difficulty level asks of you
