Sudoku Solver
Backtracking with constraint propagation. The design question isn't 'how do I solve Sudoku' — it's how to model the board so validation, generation, and solving reuse the same code.
Key Abstractions
9x9 grid with cells, plus derived views (rows, columns, boxes)
Position plus current value (0 for empty). Knows its row, column, and 3x3 box.
Strategy interface. Backtracking (MRV), DLX, or constraint-propagation variants plug in.
Produces puzzles by solving a random seed then blanking N cells
Class Diagram
The Key Insight
Sudoku solving looks like an algorithms problem, but the design portion is really about separation of state and strategy. The Board owns the grid and the "is this placement legal" answer. The Solver owns how to search. If those two get tangled, swapping backtracking for Dancing Links (DLX) means rewriting the validator.
The second insight is the bitmask. Representing "which digits appear in row 3" as a 10-bit integer makes every legality check a single (mask & bit) == 0. Three bitmasks (one per row, column, box) replace three O(9) scans per placement. That's what lets the MRV heuristic run fast enough to solve evil-level puzzles in milliseconds.
Requirements
Functional
- Represent a 9x9 grid with empty cells (0) and filled cells (1-9)
- Validate placements against Sudoku rules (row, column, box uniqueness)
- Solve a partially filled board to a full valid board
- Generate a puzzle by solving a random board and removing cells
- Detect when no solution exists
Non-Functional
- O(1) placement validation
- Solve "hard" puzzles in under 10 ms
- Board, Validator, and Solver must be independently testable
- Solver strategy must be swappable (backtracking, DLX, etc.)
Design Decisions
Why bitmasks over sets?
A Set<Integer> per row works, but allocates a hash table and makes "is 5 in this row" a map lookup. A 10-bit integer is a single CPU word. Legality check: three bitwise ANDs. Placement: three ORs. No allocations, no hashing, cache-friendly.
Why the MRV heuristic?
Plain DFS picks the first empty cell in reading order. That often explores branches for cells with 8 candidates before fixing a cell with 1 candidate. MRV (Minimum Remaining Values) picks the cell with the fewest legal digits next. A cell with one candidate gets "forced" immediately. Propagating forced moves collapses the search tree dramatically — a 10x-100x speedup on hard puzzles.
Why separate Solver from Board?
The board stays a pure data structure. Tests can construct boards, inspect state, mutate cells, all without pulling in a solver. Generation uses the board to track what's on the grid; solving uses the board to check legality; rendering uses the board to print. If solving logic lived inside Board, every test would drag along the whole search machinery.
Why undo by remove() rather than snapshotting?
A full Board snapshot is 81 integers plus three masks — small but allocated per recursion frame. Backtracking hits 100,000+ frames on hard puzzles. Incremental place/remove reuses the same board, paying three bit flips per undo. Memory usage stays flat.
Interview Follow-ups
- "How would Dancing Links (DLX) compare?" DLX models Sudoku as exact-cover and uses toroidal doubly-linked lists. Faster on the hardest puzzles but much more complex. For 9x9 the backtracking+MRV approach is fast enough that DLX rarely pays back.
- "How would constraint propagation (naked singles, hidden singles) plug in?" Run propagation as a pre-step before each backtrack. When propagation narrows candidates to one, place the digit without recursing. Works cleanly as a
preProcess(board)hook inside the solver's loop. - "How do you generate a puzzle with a unique solution?" Generate a full board, remove cells one at a time, and after each removal check that the solver still finds exactly one solution. Modify the solver to enumerate solutions up to a cap of 2 and bail on the second.
- "What about 16x16 Sudoku?" Generalize N from 9 and box size from 3. Masks grow to 17 bits — still fits in an int. Solver code is unchanged; Board becomes parameterized.
Code Implementation
1 from __future__ import annotations
2 from abc import ABC, abstractmethod
3 from dataclasses import dataclass
4 import random
5
6
7 @dataclass(frozen=True)
8 class Cell:
9 row: int
10 col: int
11
12 @property
13 def box(self) -> int:
14 return (self.row // 3) * 3 + (self.col // 3)
15
16
17 class Board:
18 """9x9 Sudoku with O(1) placement validation via per-unit bitmasks."""
19
20 N = 9
21
22 def __init__(self, grid: list[list[int]] | None = None):
23 self.grid = [[0] * 9 for _ in range(9)]
24 # bit d is set in row_mask[r] iff digit d already appears in row r.
25 self.row_mask = [0] * 9
26 self.col_mask = [0] * 9
27 self.box_mask = [0] * 9
28 if grid:
29 for r in range(9):
30 for c in range(9):
31 d = grid[r][c]
32 if d != 0:
33 if not self.place(r, c, d):
34 raise ValueError(f"Initial grid invalid at ({r},{c}) = {d}")
35
36 def _box(self, r: int, c: int) -> int:
37 return (r // 3) * 3 + (c // 3)
38
39 def is_legal(self, r: int, c: int, d: int) -> bool:
40 bit = 1 << d
41 return (self.row_mask[r] & bit) == 0 \
42 and (self.col_mask[c] & bit) == 0 \
43 and (self.box_mask[self._box(r, c)] & bit) == 0
44
45 def place(self, r: int, c: int, d: int) -> bool:
46 if self.grid[r][c] != 0 or not (1 <= d <= 9):
47 return False
48 if not self.is_legal(r, c, d):
49 return False
50 bit = 1 << d
51 self.grid[r][c] = d
52 self.row_mask[r] |= bit
53 self.col_mask[c] |= bit
54 self.box_mask[self._box(r, c)] |= bit
55 return True
56
57 def remove(self, r: int, c: int) -> None:
58 d = self.grid[r][c]
59 if d == 0:
60 return
61 bit = 1 << d
62 self.grid[r][c] = 0
63 self.row_mask[r] &= ~bit
64 self.col_mask[c] &= ~bit
65 self.box_mask[self._box(r, c)] &= ~bit
66
67 def candidates(self, r: int, c: int) -> list[int]:
68 if self.grid[r][c] != 0:
69 return []
70 used = self.row_mask[r] | self.col_mask[c] | self.box_mask[self._box(r, c)]
71 return [d for d in range(1, 10) if (used & (1 << d)) == 0]
72
73 def is_complete(self) -> bool:
74 return all(self.grid[r][c] != 0 for r in range(9) for c in range(9))
75
76 def clone(self) -> "Board":
77 b = Board()
78 b.grid = [row[:] for row in self.grid]
79 b.row_mask = self.row_mask[:]
80 b.col_mask = self.col_mask[:]
81 b.box_mask = self.box_mask[:]
82 return b
83
84 def render(self) -> str:
85 lines = []
86 for r in range(9):
87 if r % 3 == 0 and r > 0:
88 lines.append("------+-------+------")
89 row = []
90 for c in range(9):
91 if c % 3 == 0 and c > 0:
92 row.append("|")
93 row.append(str(self.grid[r][c]) if self.grid[r][c] else ".")
94 lines.append(" ".join(row))
95 return "\n".join(lines)
96
97
98 class Solver(ABC):
99 @abstractmethod
100 def solve(self, board: Board) -> bool: ...
101
102
103 class BacktrackSolver(Solver):
104 """Minimum-Remaining-Values heuristic. Picks the cell with fewest candidates next."""
105
106 def solve(self, board: Board) -> bool:
107 cell = self._pick_next(board)
108 if cell is None:
109 return True
110 r, c = cell
111 for d in board.candidates(r, c):
112 board.place(r, c, d)
113 if self.solve(board):
114 return True
115 board.remove(r, c)
116 return False
117
118 def _pick_next(self, board: Board) -> tuple[int, int] | None:
119 best = None
120 best_count = 10
121 for r in range(9):
122 for c in range(9):
123 if board.grid[r][c] == 0:
124 cands = board.candidates(r, c)
125 if len(cands) < best_count:
126 best_count = len(cands)
127 best = (r, c)
128 if best_count == 1:
129 return best
130 return best
131
132
133 class Generator:
134 """Produces a puzzle by solving a random board, then removing digits."""
135
136 def __init__(self, solver: Solver, rng: random.Random | None = None):
137 self._solver = solver
138 self._rng = rng or random.Random()
139
140 def generate(self, holes: int = 40) -> Board:
141 board = Board()
142 # Seed diagonal boxes with random permutations — they don't constrain each other.
143 for box in range(0, 9, 4):
144 digits = list(range(1, 10))
145 self._rng.shuffle(digits)
146 for i in range(3):
147 for j in range(3):
148 board.place((box // 3) * 3 + i, (box % 3) * 3 + j, digits[i * 3 + j])
149 if not self._solver.solve(board):
150 raise RuntimeError("Could not generate solution")
151 # Remove `holes` cells at random.
152 cells = [(r, c) for r in range(9) for c in range(9)]
153 self._rng.shuffle(cells)
154 for r, c in cells[:holes]:
155 board.remove(r, c)
156 return board
157
158
159 if __name__ == "__main__":
160 puzzle = [
161 [5, 3, 0, 0, 7, 0, 0, 0, 0],
162 [6, 0, 0, 1, 9, 5, 0, 0, 0],
163 [0, 9, 8, 0, 0, 0, 0, 6, 0],
164 [8, 0, 0, 0, 6, 0, 0, 0, 3],
165 [4, 0, 0, 8, 0, 3, 0, 0, 1],
166 [7, 0, 0, 0, 2, 0, 0, 0, 6],
167 [0, 6, 0, 0, 0, 0, 2, 8, 0],
168 [0, 0, 0, 4, 1, 9, 0, 0, 5],
169 [0, 0, 0, 0, 8, 0, 0, 7, 9],
170 ]
171 board = Board(puzzle)
172 print("Puzzle:")
173 print(board.render())
174 assert BacktrackSolver().solve(board)
175 print("\nSolved:")
176 print(board.render())
177 assert board.is_complete()
178 print("\nAll cells filled.")Common Mistakes
- ✗Scanning row/col/box on every move. That's O(27) per placement. Bitmasks make it O(1).
- ✗Forgetting to undo placements on backtrack. The mask has a stale bit and the solver deadlocks.
- ✗Choosing cells in reading order. Picking the most-constrained cell first (MRV) is 100x faster.
- ✗Mixing UI state into the board model. A console-free Board is what lets the solver run in tests.
Key Points
- ✓Track used digits per row, column, and box as bitmasks. Validation becomes a single bitwise AND.
- ✓Backtracking picks the cell with fewest candidates first (MRV heuristic). Cuts search space massively.
- ✓Board, Validator, and Solver are separate. Generation reuses Validator; solving reuses Board.
- ✓Solver is a Strategy so the same Board can be solved by backtracking, DLX, or constraint propagation.