The idea: try a digit, recurse, undo on a dead end

A Sudoku grid has 81 cells in 9 rows, 9 columns and 9 boxes of 3×3. Each row, column and box must hold the digits 1 to 9 once. Some cells are given; the solver fills the rest.

Backtracking fills one empty cell at a time. It picks a cell, writes a digit that does not clash with anything yet, and moves on to the next empty cell. When it reaches a cell where no digit fits, it has made a wrong guess somewhere earlier. It goes back to the most recent guess, erases it, and tries the next digit there.

Search tree for the Dead ends puzzle: cell r4c2 has candidates 2 and 5; the branch r4c2 = 2 leads to r4c8 with no candidate, marked as a dead end; the search backtracks and the branch r4c2 = 5 gives r4c8 the single candidate 2 and the search continues
Each level of the tree is one cell; a cell with no candidate ends its branch, and the search returns to the last choice that still has another digit.

The page shows the search one move at a time: choose a cell, place a digit, or backtrack. Press Next Move to step by hand, or Solve to run it.

Candidates: the constraint check

When the solver picks a cell, it first looks at the cell's row, column and box. Every digit already there is ruled out. The digits that are left are the cell's candidates, and only they are tried. The digit strip on the canvas marks each digit: ✗ row, col or box says where it already is, ✓ is a candidate still to try.

Cell r4c2 of the Dead ends puzzle with its row, column and box shaded; the digits 1 to 9 below it, with 1, 3, 4, 6, 7, 8 and 9 crossed out because row 4 already holds them (column 2 and the box hold some of them too), leaving 2 and 5 as candidates
Checking the row, column and box before trying anything cuts nine possible digits down to two.

This check is the pruning: a digit that clashes would fail anyway, so the solver never builds the part of the search tree below it. Without it, a solver that only checks a full grid would have to look at up to 951 fillings of the classic puzzle.

Dead ends and backtracking

A dead end is an empty cell whose candidate list is empty (red on the canvas). It does not mean this cell is wrong: it means an earlier guess was wrong. So the solver undoes the most recent placement and tries that cell's next candidate.

If the cell it went back to has no candidate left either, it backtracks again, one level further up. In Demo: dead end and backtrack, r4c2 = 2 leaves r4c8 with nothing, so r4c2 becomes 5. Later r5c6 is stuck, r5c4 had only one candidate, and the search backs up two levels to change r5c3 from 3 to 6.

The call stack

A recursive solver is short:

solve(grid):
    cell = next empty cell        (none left: solved)
    for d in candidates(cell):
        grid[cell] = d
        if solve(grid): return true
        grid[cell] = empty        (undo)
    return false                  (dead end)

Each call that is still running is one frame on the call stack: a cell, its candidate list and how far along that list it is. The panel on the canvas draws those frames, newest on top. The depth is the number of cells the search has filled so far. Returning false pops a frame, and that is a backtrack. See recursion as an explicit stack for how a recursive function turns into this loop.

Which cell next: row order vs fewest candidates

The order in which cells are filled changes everything. Row by row takes the first empty cell in reading order, even if it has many candidates. Fewest candidates first (the MRV heuristic, minimum remaining values) scans every empty cell and takes the one with the fewest candidates. A cell with one candidate is forced, and a cell with none is a dead end found right away instead of many levels later.

Two bars for the classic 51-blank puzzle: row by row needs 4,208 placements and 4,157 backtracks; fewest candidates first needs 51 placements and 0 backtracks
On the same classic puzzle, choosing the most constrained cell first removes every backtrack.
PuzzleBlanksRow by row: placements / backtracksFewest candidates first
Easy1010 / 010 / 0
Dead ends1619 / 316 / 0
Medium2840 / 1228 / 0
Classic514,208 / 4,15751 / 0

The classic puzzle in row order takes 12,573 moves, so Solve animates the first 120 and runs the rest in one step (Demo: classic puzzle, row by row). With fewest candidates first it needs 102 moves and never backtracks (Demo: classic puzzle, fewest candidates first). Here the classic puzzle always has a cell with a single candidate; very hard puzzles reach states where no cell is forced, and then even MRV has to guess and backtrack.

How much work it is

In the worst case backtracking is exponential: with n empty cells it may try up to 9n fillings. In practice the candidate check and a good cell order cut the tree so much that ordinary newspaper puzzles take well under a second. Sudoku on an n×n grid is NP-complete, so no known method avoids exponential time on every puzzle.

The same pattern solves other constraint puzzles: N-Queens (one queen per row), map colouring as a constraint satisfaction problem (with forward checking and MRV) and permutations and subsets (backtracking without constraints).

What the page leaves out

Fast Sudoku solvers do more than check candidates. They propagate constraints after each placement (naked singles, hidden singles: a digit that fits in only one cell of a row, column or box), keep candidate sets as bit masks instead of rescanning, and choose cells and digits with smarter rules. Knuth's Dancing Links (DLX) solves Sudoku as an exact cover problem. The page also skips generating puzzles and checking that a puzzle has exactly one solution.