---
title: "Sudoku Solver"
description: "Fill the grid cell by cell, backtracking when a digit breaks a constraint."
source: https://vizlearn.app/algorithms/backtracking/sudoku-solver
access: premium (interactive player requires Lifetime; this doc is free)
---

# Sudoku Solver

Sudoku looks like a number puzzle, but a Sudoku solver never does arithmetic with the digits. Each blank asks which members of `1..9` are absent from its row, column, and 3x3 box. The solver writes one surviving digit, recurses, and erases that write if the smaller puzzle has no solution.

That erase is part of the algorithm, not animation cleanup. Candidate sets come from the live board. Leave a failed guess behind and it becomes a fake constraint, poisoning every sibling branch that follows.

## Choosing the next cell with MRV

A correct backtracker may pick the first blank it sees. The **minimum remaining values** heuristic, or MRV, scans every blank and picks the one with the fewest legal digits. Row-major order breaks ties, and digits are tried in ascending order, so both variants remain deterministic.

MRV is a fail-first rule. One candidate means no branch. Zero candidates proves the current branch impossible. Two candidates are more useful than six because a bad choice is exposed closer to the decision that caused it.

The lesson turns that claim into an experiment. Both variants solve the same default board; only the cell-selection block changes.

| Cell selection | First cell | Placements | Backtracks |
| -------------- | ---------- | ---------: | ---------: |
| MRV            | `(0, 4)`   |         46 |          3 |
| First blank    | `(0, 1)`   |         99 |         56 |

First blank still reaches the same solution. It simply walks into 53 extra tentative writes and 53 extra reversals before getting there. That is the evidence for MRV: not a nicer title, but a smaller measured search tree on the same input.

The candidate function builds one `used` set from the nonzero digits in the chosen cell's row, column, and box. Its legal list is `1..9` minus that union. The board shows every blank's candidate count during selection, so you can inspect the minimum instead of taking the status line on faith. Under First blank, lower-count alternatives remain visible as the cells that strategy ignored.

## One clue can remove the branch or kill the puzzle

The input presets run a different experiment: the code stays fixed on MRV while one clue changes.

| Preset        | Value at `(0, 4)` | Result   | Placements | Backtracks |
| ------------- | ----------------: | -------- | ---------: | ---------: |
| Branch + undo |             blank | solved   |         46 |          3 |
| Correct clue 7 |                7 | solved   |         42 |          0 |
| No solution   |                 4 | unsolved |          2 |          2 |

Fixing the correct `7` removes the only two-option decision in the MRV trace. The solver did not get smarter; the puzzle supplied enough information to make every remaining choice forced.

Fixing `4` does something subtler. It creates no immediate duplicate, so the clue is locally legal, yet the partial board has no completion. Two tentative placements later, one blank has no candidates. Search clears both writes, reaches the immutable clue, and reports no solution with the input board restored exactly. Local validity is not extendability.

This direct backtracker is a good fit when the board is small, constraint checks are cheap, and one solution is enough. For batches of difficult puzzles, maintain row, column, and box bitmasks instead of rebuilding sets. For richer constraints or exhaustive solving, exact cover, SAT, or constraint programming is usually a better tool.

## How Sudoku Solver backtracking works

After the selected strategy chooses `(row, col)`, the recursive contract is short and unforgiving:

1. If no blank remains, return `true`.
2. If the chosen blank has no legal digit, return `false`.
3. Write one candidate into the cell.
4. Recurse on the mutated board.
5. If the child succeeds, return `true` and keep the completed board.
6. If the child fails, set the cell back to `0`, then try the next candidate.

The loop invariant does the real work: before each candidate is tried, the board must equal the state this call received. Deeper calls restore their writes while unwinding; the current call clears its own write. When the loop advances, no residue from the failed subtree remains.

The solver returns the first solution. It does not count solutions or continue after a complete board is found.

## Sudoku Solver Step by Step

The default MRV puzzle begins with 38 givens and 43 blanks. Its first selected cell is `(0, 4)`, with legal digits `[4, 7]`.

1. The solver tries `4` at `(0, 4)` and descends.
2. MRV forces `7` at `(2, 4)`, then `3` at `(2, 3)`.
3. Cell `(2, 8)` has zero candidates. Its row, column, and box jointly block all nine digits, so that child returns `false`.
4. The solver clears `3` from `(2, 3)`. That caller has no second option and returns `false`.
5. The next caller clears `7` from `(2, 4)` and exhausts its only option.
6. The root clears `4` from `(0, 4)`. The tried-options strip now keeps `4 x` visible beside the untried `7`.
7. The root tries `7`. Every later MRV choice is forced, and the board completes.

The algorithm makes 46 tentative placements, three backtracks, and reaches depth 43. The player uses 33 visible beats: it preserves the failed branch and all three undos one operation at a time, then summarizes 41 already-understood singleton writes in seven labeled fast-forward checkpoints. Those checkpoints are editorial pacing, not a batch operation in the displayed code; their boards and counters are snapshots from the atomic recursive trace.

The final board is:

```text
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9
```

Three proof beats then check all rows, all columns, and all boxes. Each beat is static and pausable: the proof geometry turns green while the solved digits stay neutral, so the obligation does not disappear into an all-green board.

## Time and Space Complexity

Let `B` be the number of blanks. The loose worst-case time complexity is `O(9^B)` because a cell may branch over nine digits. Sudoku constraints and MRV can shrink the explored tree dramatically, as the 46-versus-99 placement audit shows, but neither changes the exponential worst-case bound.

This implementation recomputes candidates while scanning blanks at each recursive call. On a fixed 9x9 board, each row, column, and box check is bounded by a small constant. The recursion stack and tentative path hold at most `B` choices, so auxiliary space is `O(B)` apart from the board.

MRV changes search order, not correctness. A First blank solver has the same solution set under the same candidate rule; it may pay for a much larger failed prefix.

## Edge Cases

- A complete valid board has no blank to select, so the first search call returns `true` without a placement.
- A blank with zero legal digits is an immediate contradiction, even when every filled cell is locally legal.
- A puzzle may have several solutions. This solver stops at the first one reached by its deterministic cell and digit order; it does not prove uniqueness.
- Duplicate givens are outside the search contract and should be rejected before recursion. The lesson validates all preset boards before tracing.
- The blocked preset has no duplicate givens but no completion. It returns `None` or `null` only after restoring every tentative write.

## Common Mistakes

- **Skipping `board[row][col] = 0`.** The abandoned digit remains in the source of truth and blocks candidates that should be legal.
- **Treating zero candidates as completion.** An empty domain is a contradiction. Completion means there are no blank cells.
- **Returning `false` after the first failed digit.** That digit failed; the current cell may still have another candidate. The false return belongs after the loop.
- **Checking only row and column.** Sudoku's 3x3 boxes are independent constraints. Omitting the box can produce a Latin square that is not a Sudoku solution.
- **Mutating givens.** Only cells blank in the input belong to the tentative trail. Fixed clues are premises.
- **Calling MRV a correctness requirement.** MRV is a search-order heuristic. The First blank variant proves that the rollback algorithm still works without it; it just works harder on this board.