Overview
A Sudoku solver is backtracking in its most legible form. Find an empty cell, try a digit that does not immediately break a rule, recurse, and if the recursion fails, erase the digit and try the next one.
What makes it finish at all is pruning. A blind search would try 9 digits in each of the empty cells, which for a typical puzzle is a number with fifty digits in it. Checking the row, column and 3×3 box before recursing kills the overwhelming majority of those branches at their first node, and the search that remains is small enough to run in milliseconds.
How Sudoku Solver works
- Scan the grid for the next empty cell. If there is none, the puzzle is solved.
- For each digit 1 through 9, check whether it already appears in that cell's row, column, or 3×3 box.
- If the digit is legal, write it in and recurse on the rest of the grid.
- If that recursion reports success, propagate the success upward and stop.
- If it fails, erase the digit — this is the backtrack — and try the next candidate. If all nine fail, report failure to the caller.
When to use it
- The clearest teaching example of backtracking, because the state, the constraint and the undo step are all visible on one grid.
- The same skeleton solves N-Queens, graph colouring, crosswords and exact-cover puzzles — only the legality check changes.
- Constraint-satisfaction problems in scheduling and timetabling, where a partial assignment must be undone when it leads nowhere.
- Puzzle generation as well as solving: generate a filled grid, then remove clues while the solver still reports a unique solution.
Complexity analysis
The worst case is O(9^m) where m is the number of empty cells, since each could in principle take any of nine digits. That bound is almost meaningless in practice: constraint checking removes most branches before they are entered, and a well-formed puzzle solves far faster than the exponent suggests. Space is O(m) for the recursion stack — the grid itself is modified in place and restored on the way back up.
Frequently asked questions
Why erase the digit instead of copying the grid?
Copying an 81-cell grid at every node would dominate the runtime and the memory. Writing then erasing keeps a single grid that is always consistent with the current path, which is what makes backtracking cheap.
Does the order of empty cells matter?
Enormously. Scanning in reading order is the simple version; picking the empty cell with the fewest legal candidates first — the minimum-remaining-values heuristic — often cuts the search by orders of magnitude, because it forces contradictions to surface early.
How can the solver tell a puzzle has more than one solution?
Do not stop at the first success. Keep counting and abort once you reach two — a proper Sudoku is defined as having exactly one solution, and this is the check used when generating puzzles.