BacktrackingAlgorithmaka 9x9 constraint solver

Sudoku Solver

Fill empty cells one by one with digits that do not conflict in their row, column, or 3×3 box, backtracking on dead ends.

▶ VisualizePattern: BacktrackingPractice (2)
Progress

Overview

Sudoku is N-Queens with three constraint families instead of four attack lines: each digit 1–9 appears once per row, once per column, and once per 3×3 box. Keep rows[r][d], cols[c][d], boxes[b][d] occupancy tables so "is digit d legal at (r, c)" is O(1).

A plain left-to-right scan works for typical puzzles, but the minimum remaining values (MRV) heuristic — always fill the empty cell with the fewest legal digits — prunes dramatically on hard boards and is what a good interviewer wants to hear about.

backtrackingconstraint satisfactionpruningMRV heuristicgrid

Intuition

A mental model before the formal terms.

Fill the grid the way a person does when guessing: write a candidate digit in pencil, keep going, and if you reach a cell with no legal digit, erase back to the last guess and try the next one.

Picking the most constrained cell first is like solving the corner of a jigsaw before the sky: fewer options means fewer wasted guesses and earlier detection of contradictions.

How it works

  1. Initialize rows, cols, boxes from the given digits; box index is (r // 3) * 3 + c // 3.
  2. Collect the empty cells. Choose the next cell to fill (first empty, or the one with the fewest legal digits under MRV).
  3. Base case: no empty cells remain — the board is solved; return true.
  4. For each digit d legal at that cell: place it, update the three tables, recurse; on true propagate success, otherwise undo and try the next digit.
  5. If no digit works, return false so the caller backtracks.

Why it works

The three tables are exactly the Sudoku rules, so a placement passing the check never violates a rule with already-placed digits; conflicts are monotone, so pruning on any violation is sound.

Depth-first search over cell assignments is exhaustive: if a solution exists, some branch places each of its digits in turn, and each such placement passes the check.

MRV does not change correctness, only order — but a cell with 0 legal digits is detected immediately, and cells with 1 legal digit are forced moves, so the effective branching factor drops close to 1.

Recognition

How to tell a problem wants this.

  • Fill a grid subject to "each value once per row / column / region" rules.
  • Fixed tiny board (9×9) with a guarantee that a solution exists — exhaustive search is expected.
  • Any exact-cover-flavored puzzle (Kakuro, KenKen) for which you would otherwise reach for Dancing Links.
“all combinations” → Backtracking

Interactive visualization

Play, step, change the input. ← → and space work too.

1
4
1
3
4
2
1/36Solve the 4×4 sudoku by filling empty cells left-to-right, top-to-bottom, trying digits 1..4 and undoing any choice that leads to a dead end.
Given cluePlaced by searchCell being triedConflicting cell
PseudocodeLearn Sudoku Solver →
1solve():
2  find next empty cell (r, c); if none: return true
3  for v in 1 .. N:
4    if valid(r, c, v):
5      board[r][c] = v
6      if solve(): return true
7      board[r][c] = 0        // backtrack
8  return false
Variables
placements0
backtracks0
Complexity
worst O(9^m)
space O(m)
Speed

Pseudocode

1solve():
2  cell = pick empty cell (first, or fewest candidates)
3  if none: return true
4  for d in 1..9:
5    if d in rows[r] or cols[c] or boxes[box(r,c)]: continue
6    place d; mark tables
7    if solve(): return true
8    remove d; unmark tables
9  return false

Implementations

1def solve_sudoku(board: list[list[str]]) -> bool:
2    """Solves in place; '.' marks empty cells. Returns True if solvable."""
31 · Occupancy bitmasks from the given board
4    rows = [0] * 9
5    cols = [0] * 9
6    boxes = [0] * 9
7    empties: list[tuple[int, int]] = []
8    for r in range(9):
9        for c in range(9):
10            ch = board[r][c]
11            if ch == ".":
12                empties.append((r, c))
13            else:
14                bit = 1 << int(ch)
15                rows[r] |= bit
16                cols[c] |= bit
17                boxes[(r // 3) * 3 + c // 3] |= bit
18 
192 · Legal-digit mask for a cell
20    def used_mask(r: int, c: int) -> int:
21        return rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]
22 
23    def fill() -> bool:
24        if not empties:
25            return True
263 · MRV: fill the most constrained cell first
27        best = min(range(len(empties)),
28                   key=lambda i: 9 - (used_mask(*empties[i]) & 0x3FE).bit_count())
29        empties[best], empties[-1] = empties[-1], empties[best]
30        r, c = cell = empties.pop()
31        b = (r // 3) * 3 + c // 3
324 · Try each legal digit, recurse, undo
33        for d in range(1, 10):
34            bit = 1 << d
35            if used_mask(r, c) & bit:
36                continue
37            board[r][c] = str(d)
38            rows[r] |= bit
39            cols[c] |= bit
40            boxes[b] |= bit
41            if fill():
42                return True
43            rows[r] ^= bit
44            cols[c] ^= bit
45            boxes[b] ^= bit
46            board[r][c] = "."
475 · Dead end: restore the cell list and backtrack
48        empties.append(cell)
49        empties[best], empties[-1] = empties[-1], empties[best]
50        return False
51 
52    return fill()
Walkthrough
  1. Section 1 builds integer bitmasks per row, column, and box; Python ints are arbitrary precision, so a 10-bit mask is just a small int.
  2. used_mask ORs the three masks; the nested fill closure mutates the enclosing lists directly, so no parameters are threaded through.
  3. Section 3 uses min(range(len(empties)), key=...) with int.bit_count() to find the cell with the fewest legal digits (MRV).
  4. r, c = cell = empties.pop() binds the tuple and unpacks it in one statement after the swap-to-end.
  5. Section 4 tries each legal digit: set the bits with |=, recurse, and undo with ^= plus restoring the "." marker.
  6. Section 5 reinserts the cell and reverses the swap so every sibling candidate sees the same empties order.
Complexity (this implementation)
time O(9^m) worst case, m = empty cells · space O(m) recursion depth plus O(1) tables

Recursion depth is at most 81, far below CPython's default limit of 1000 — no sys.setrecursionlimit needed here.

Language notes
  • int.bit_count() needs Python 3.10+; on older versions use bin(x).count("1").
  • Sets of used digits (rows[r] = set()) read more naturally but are several times slower than int bitmasks in CPython.
  • The closure over rows/cols/boxes works because the code only mutates elements; rebinding the names would need nonlocal.
Common mistakes in this language
  • Wrong box index — (r // 3) * 3 + c // 3, not r // 3 + c // 3.
  • Using / instead of // so the box index becomes a float and raises TypeError on indexing.
  • Forgetting to restore board[r][c] = "." on failure, leaving stale digits that corrupt later checks.
Language differences that matter here
  • Popcount: C++ has __builtin_popcount (or C++20 std::popcount), Python 3.10+ has int.bit_count(), JS/TS hand-roll the Kernighan loop.
  • C++ mutates char cells directly; JS/TS/Python boards hold one-character strings, so digits must be converted with String(d) / str(d).
  • C++ wraps the state in a class; the other three use closures over local arrays, which is the idiomatic substitute.
  • JS/TS bitwise operators truncate to 32 bits — irrelevant for 10-bit masks but worth knowing before widening the pattern.

Complexity

Best
—
Average
—
Worst
O(9^m)
Space
O(m)

m = number of empty cells (≤ 81). The bound is never approached in practice; with MRV, typical puzzles take well under 10^4 placements.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Small fixed grids with local "once per group" constraints and a guaranteed solution.
  • Any exact-cover puzzle where implementing Knuth's Algorithm X would be overkill.
Avoid it when
  • Large generalized Sudoku (n² × n² for n ≥ 5) — plain backtracking blows up; use constraint propagation (naked singles, hidden singles) or Dancing Links.
  • You need to count all solutions of a nearly-empty board — the count is astronomically large.

Alternatives

N-QueensRecursion & BacktrackingBit Masks

Common mistakes

  • Wrong box index — (r // 3) * 3 + c // 3, not r // 3 + c // 3.
  • Not undoing the occupancy tables when a digit fails, corrupting later checks.
  • Returning after the first digit placement instead of propagating the recursive result (if solve(): return true).
  • Recomputing the row/col/box scan for every check (O(27) instead of O(1)) — fine for correctness but slow on hard boards.

Interview patterns

  • Valid Sudoku (checking only) is the same three-table pass without recursion.
  • Ask about MRV / forward checking when the interviewer says "the board is hard" — it shows you know why naive order can explode.
  • Bitmask tables (int per row/col/box) are the standard speed-up; popcount gives the candidate count for MRV.
Interview questions on this
Mock interviews

Example problems

N-QueenshardSudoku Solverhard