Sudoku Solver

Try a digit, check three units, undo on a dead end

time O(9^m), m = empty cellsspace O(m) recursion depth

There is no way to compute a cell's digit directly; the only information is which digits are already ruled out. So the solver guesses: find the next empty cell, try 1 through 9, and keep the first digit that is absent from the cell's row, column and box. That digit is not a decision, it is a hypothesis. The search recurses to the next empty cell, and if some later cell has no legal digit at all, the hypothesis was wrong: the recursive call returns false, the caller erases its digit and tries the next one. The board is mutated in place and restored on the way back, so a single board carries the whole search. The scan order is left to right, top to bottom, which is why the trace can follow just one row and still show every kind of move.

Details

Animated on: The 9x9 board from the statement, 51 cells empty. Shown: row 0 = [5, 3, ., ., 7, ., ., ., .] which must become [5, 3, 4, 6, 7, 8, 9, 1, 2]. Fill every '.' so each row, column and 3x3 box holds 1-9 exactly once.

Problem:Sudoku SolverHard

Try a digit, check three units, undo on a dead end

step 1 / 14

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

The board has 51 empty cells. The trace follows row 0 only: [5, 3, ., ., 7, ., ., ., .]. Given digits are fixed; each '.' must take a digit that is absent from its row, its column AND its 3x3 box. There is no formula for this — the only tool is try, check, and undo.

Pseudocode

1FUNCTION solve(board)
2  FOR r <- 0 TO 8
3    FOR c <- 0 TO 8
4      IF board[r][c] != '.' CONTINUE
5      FOR d <- 1 TO 9
6        IF d IN row r OR d IN column c OR d IN box(r, c) CONTINUE
7        board[r][c] <- d
8        IF solve(board) = TRUE
9          RETURN TRUE
10        board[r][c] <- '.'
11      RETURN FALSE
12  RETURN TRUE

← / → step · space play · Home restart

Every step in words

Show all 14 steps

The board has 51 empty cells. The trace follows row 0 only: [5, 3, ., ., 7, ., ., ., .]. Given digits are fixed; each '.' must take a digit that is absent from its row, its column AND its 3x3 box. There is no formula for this — the only tool is try, check, and undo.
Cell (0,2): the first candidate survives every check. Digit 1 appears nowhere in row 0, column 2 or its box, so it is placed tentatively and the search moves to the next empty cell. Placement #1 — nothing is proven yet, only not-yet-contradicted.
Cell (0,3): rejected 1 (column, cell (1,3)). Digit 2 appears nowhere in row 0, column 3 or its box, so it is placed tentatively and the search moves to the next empty cell. Placement #2 — nothing is proven yet, only not-yet-contradicted.
Cell (0,5): rejected 1 (row, cell (0,2)), 2 (row, cell (0,3)), 3 (row, cell (0,1)). Digit 4 appears nowhere in row 0, column 5 or its box, so it is placed tentatively and the search moves to the next empty cell. Placement #3 — nothing is proven yet, only not-yet-contradicted.
Cell (0,6): rejected 1 (row, cell (0,2)), 2 (row, cell (0,3)), 3 (row, cell (0,1)), 4 (row, cell (0,5)), 5 (row, cell (0,0)), 6 (3x3 box, cell (2,7)), 7 (row, cell (0,4)). Digit 8 appears nowhere in row 0, column 6 or its box, so it is placed tentatively and the search moves to the next empty cell. Placement #4 — nothing is proven yet, only not-yet-contradicted.
Cell (0,7): rejected 1 (row, cell (0,2)), 2 (row, cell (0,3)), 3 (row, cell (0,1)), 4 (row, cell (0,5)), 5 (row, cell (0,0)), 6 (column, cell (2,7)), 7 (row, cell (0,4)), 8 (row, cell (0,6)). Digit 9 appears nowhere in row 0, column 7 or its box, so it is placed tentatively and the search moves to the next empty cell. Placement #5 — nothing is proven yet, only not-yet-contradicted.
Dead end at (0,8): the rest are blocked outright — 1 (row, cell (0,2)), 2 (row, cell (0,3)), 3 (row, cell (0,1)), 4 (row, cell (0,5)), 5 (row, cell (0,0)), 6 (column, cell (5,8)), 7 (row, cell (0,4)), 8 (row, cell (0,6)), 9 (row, cell (0,7)). No digit can go here, so an EARLIER guess must be wrong. Return false so the caller erases its own digit and tries its next candidate.
Everything to the right of (0,7) failed with 9 here, so 9 was wrong for this cell. Erase it (undo #1) and let the loop try the next digit after 9. This undo IS the backtracking: the board returns to exactly the state before the guess.
Dead end at (0,7): 9 was tried and undone, and the rest are blocked outright — 1 (row, cell (0,2)), 2 (row, cell (0,3)), 3 (row, cell (0,1)), 4 (row, cell (0,5)), 5 (row, cell (0,0)), 6 (column, cell (2,7)), 7 (row, cell (0,4)), 8 (row, cell (0,6)). No digit can go here, so an EARLIER guess must be wrong. Return false so the caller erases its own digit and tries its next candidate.
Everything to the right of (0,6) failed with 8 here, so 8 was wrong for this cell. Erase it (undo #2) and let the loop try the next digit after 8. This undo IS the backtracking: the board returns to exactly the state before the guess.
Cell (0,6): rejected 1 (row, cell (0,2)), 2 (row, cell (0,3)), 3 (row, cell (0,1)), 4 (row, cell (0,5)), 5 (row, cell (0,0)), 6 (3x3 box, cell (2,7)), 7 (row, cell (0,4)). Digit 9 appears nowhere in row 0, column 6 or its box, so it is placed tentatively and the search moves to the next empty cell. Placement #6 — nothing is proven yet, only not-yet-contradicted.
Dead end at (0,7): the rest are blocked outright — 1 (row, cell (0,2)), 2 (row, cell (0,3)), 3 (row, cell (0,1)), 4 (row, cell (0,5)), 5 (row, cell (0,0)), 6 (column, cell (2,7)), 7 (row, cell (0,4)), 8 (column, cell (6,7)), 9 (row, cell (0,6)). No digit can go here, so an EARLIER guess must be wrong. Return false so the caller erases its own digit and tries its next candidate.
Everything to the right of (0,6) failed with 9 here, so 9 was wrong for this cell. Erase it (undo #3) and let the loop try the next digit after 9. This undo IS the backtracking: the board returns to exactly the state before the guess.
The search keeps guessing and undoing the same way across all 81 cells: 4208 placements and 4157 undos in total before a scan finds no '.' left, which is the only success condition. Row 0 ends as [5, 3, 4, 6, 7, 8, 9, 1, 2]. Depth-first with immediate undo means only one board ever exists in memory; the recursion stack is the entire record of what was tried.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Sudoku Solver in the editor All Backtracking problems Back to roadmap