Capstone: A Sudoku & N-Queens Solver Engine
Module 5 ends with a program that uses every paradigm in it. You will write one small backtracking engine — about twenty lines — and plug two very different puzzles into it: placing queens on an board so that none attack each other, and filling a Sudoku grid. Then you will make the engine fast without changing it, only by changing how each puzzle represents its state (bitmasks) and which decision it makes next (the minimum-remaining-values heuristic). A benchmark shows the effect: on one famous puzzle the naive solver gives up after three million search nodes and the final solver finishes in under four thousand.
Two shorter parts close the loop on the rest of the module. A greedy-versus-DP study finds the exact coin amounts where a cashier's greedy algorithm gives the wrong change, using a theorem that bounds how far you need to look. A randomized part shows that a backtracking search can be wildly unlucky on one input size and fine on the next, and fixes it with random restarts.
This is the Module 5 overview applied. It builds on Recursion & Backtracking (the N-Queens and Sudoku sections there are your starting point), Bit Manipulation and Greedy Algorithms.
Goal
Build a command-line program that:
- runs a generic depth-first backtracking engine over any problem that implements five methods,
- counts N-Queens solutions for and finds one solution for large ,
- solves Sudoku with three interchangeable models — naive, bitmask and bitmask + MRV — and proves each solution unique,
- benchmarks the three Sudoku models by search nodes and seconds,
- decides whether a coin system is safe for greedy change-making, and finds the smallest counterexample when it is not,
- finds N-Queens solutions with randomized value ordering and restarts, and compares the work against deterministic search.
Requirements
- Engine. One recursive function,
search(problem), that knows nothing about queens or digits. A problem supplieschoose()(the next variable,Nonewhen complete, or a dead-end signal),options(var)(values to try, in order),applyandundo(change the state and change it back), andsnapshot()(copy a finished solution). - Metric.
nodes= number of calls tosearch, counting the root. Nodes are identical in every language for the deterministic models, so they are the fair comparison; seconds are reported too, but they depend on the language and the machine. - Stopping. The engine stops after
limit_solutionssolutions or afternode_budgetnodes, whichever comes first. Asking for 2 solutions is how you prove a Sudoku has exactly one: the search must exhaust the whole tree to show there is no second. - Sudoku input. An 81-character string read row by row,
.or0for an empty cell. Reject givens that already contradict each other. - Determinism. Variables and values in a fixed order (lowest cell index, lowest digit, lowest column), so node counts match the acceptance table.
- Tests. The acceptance tests below pass.
The puzzles
The benchmark set mixes easy and hard puzzles from well-known sources. "Givens" are the pre-filled cells; 17 is the minimum for a puzzle with a unique solution (McGuire, Tugemann and Civario, 2012, by exhaustive computer search).
| Name | Givens | Source |
|---|---|---|
wikipedia | 30 | The example puzzle in Wikipedia's Sudoku article |
norvig-easy | 32 | Peter Norvig, Solving Every Sudoku Puzzle — grid1 |
norvig-hard | 17 | Peter Norvig, same essay — grid2 |
inkala-2012 | 21 | Arto Inkala's puzzle that the press called "the world's hardest Sudoku" in 2012 |
wiki-anti-brute | 17 | Wikipedia, Sudoku solving algorithms: a puzzle built so that first-empty-cell brute force is slow |
The exact strings are in the reference solution. Add your own: newspapers' "diabolical" puzzles, or a file of 17-clue puzzles.
flowchart LR
ENG["Backtracking engine: choose, options, apply, recurse, undo"] --> NQ["N-Queens models"]
ENG --> SU["Sudoku models"]
NQ --> NQN["naive: scan placed queens"]
NQ --> NQB["bitmask: 3 masks"]
SU --> SUN["naive: scan row, column, box"]
SU --> SUB["bitmask: 27 masks"]
SU --> SUM["bitmask + MRV + forward checking"]
SUN --> BENCH["Benchmark: nodes and seconds"]
SUB --> BENCH
SUM --> BENCH
NQB --> RR["Randomized order + restarts"]
COIN["Coin systems: greedy vs DP"] --> KZ["Smallest counterexample search"]
The staged plan
Part 1 — The engine
The engine is the backtracking template from Recursion & Backtracking with the problem-specific parts pulled out behind an interface:
search(p):
nodes += 1
if nodes > budget: stop
var = p.choose()
if var is None: record a solution; stop if we have enough
if var is DEAD_END: return
for val in a copy of p.options(var):
p.apply(var, val)
if search(p) says stop: undo and stop
p.undo(var, val)
Three details matter more than they look:
- Copy the options before recursing. If
optionsis a lazy generator (Pythonyield, a Java iterator) that reads the board, it will read the board after the recursive call has changed and restored it — usually fine, but a bug waiting to happen. Materialise the list first. applyandundomust be exact inverses. The cheapest way to make backtracking fast is to never copy state: mutate it in place and restore it on the way back. Every bug in this capstone that is not an off-by-one is anundothat does not quite reverse itsapply. Test it directly: apply then undo, and assert the state is unchanged.- A dead-end signal is separate from "complete". When the problem can tell, before trying any value, that some variable has no legal value left, it should say so (the reference returns
-1). That one line is what turns plain backtracking into forward checking.
Part 2 — N-Queens, two models
Place one queen per row, so a row is a variable and the column is its value. Two queens attack each other if they share a column or a diagonal. Cells on the same "/" diagonal share ; cells on the same "\" diagonal share .
Naive model. options(row) tests each column against every queen already placed: per test, per node.
Bitmask model. Keep three integers: col (bit set if column is taken), d1 (bit ) and d2 (bit , shifted so it is never negative). Testing a column is three bit tests: .
The two models visit exactly the same search tree — same variables, same value order, same pruning — so their node counts are equal. Only the cost per node differs. That distinction (fewer nodes versus cheaper nodes) is the key to reading every benchmark in this capstone.
For counting, the reference also includes the classic shifting-mask counter: carry the diagonal masks down one row at a time by shifting them left and right by one bit, so no row arithmetic is needed, and peel off free columns with free & -free (the lowest set bit; see Bit Manipulation). It is the fastest simple way to count all solutions, and it does not use the engine.
The answers to check: solutions for (OEIS A000170). For the engine visits 2,057 nodes to find all 92 solutions; the first solution, (column of the queen in rows 0 to 7), is found after 114 nodes.
Part 3 — Sudoku, three models
Variables are the 81 cells; values are digits 1–9. A digit is legal in a cell if it does not already appear in the cell's row, column or 3×3 box. The box of cell (row , column ) is .
Naive model. choose returns the first empty cell. options tries 1–9 and, for each, scans the row, column and box: 27 reads per digit.
Bitmask model (constraint propagation through candidate masks). Keep 27 nine-bit masks, one per row, column and box, with bit set when digit is used. The candidates of a cell are then one expression:
(0x3FE has bits 1 to 9 set.) Placing digit ORs bit into three masks; undoing it clears the bit from the same three. This is constraint propagation in its simplest form: every placement immediately updates what every other cell in the same row, column and box may contain, at the cost of three OR instructions. Like the N-Queens pair, the bitmask model visits the same tree as the naive one, only faster.
MRV model. Same masks, different choose: scan the empty cells and return the one with the fewest candidates (minimum remaining values). Use popcount (int.bit_count() in Python 3.10+, Integer.bitCount in Java, std::popcount or __builtin_popcount in C++). Two consequences:
- If some empty cell has zero candidates, the current partial grid is already dead; return the dead-end signal without trying anything. This is forward checking.
- If some cell has one candidate, it is forced; MRV picks it immediately (the reference stops scanning as soon as it sees a count of 0 or 1). Filling forced cells first is exactly the "naked single" rule human solvers use, so MRV gets that propagation for free.
MRV is a greedy rule applied to search: always branch where the branching factor is smallest. It is the fail-first principle (Haralick and Elliott, 1980): if the current path is doomed, the most constrained cell is where you will find out soonest, and if it is not doomed, branching on 2 options instead of 7 shrinks the tree multiplicatively.
Part 4 — Benchmark
For every puzzle and model, ask for two solutions with a budget of 3,000,000 nodes, and record nodes and seconds. A run that hits the budget is reported as "> 3,000,000". Check every returned grid: givens kept, and every row, column and box a permutation of 1–9.
Part 5 — Greedy vs DP: when does the cashier's algorithm fail?
A cashier making change greedily takes the largest coin that fits, again and again. For US coins this always uses the fewest coins. For other systems it does not:
| Coins | Amount | Greedy | Optimal (DP) |
|---|---|---|---|
| 63 | 25+25+10+1+1+1 = 6 coins | 6 coins | |
| 6 | 4+1+1 = 3 coins | 3+3 = 2 coins | |
| 48 | 30+12+6 = 3 coins | 24+24 = 2 coins | |
| 14 | 10+1+1+1+1 = 5 coins | 7+7 = 2 coins |
The third row is a simplified version of the British pre-decimal coinage in pence (penny, threepence, sixpence, shilling, florin, half crown), and the failure at 48 pence is a standard textbook example. A coin system where greedy is always optimal is called canonical.
The DP. best[a] = fewest coins for amount ; best[0] = 0; best[a] = 1 + min(best[a - c]) over coins . . This is the unbounded-knapsack shape you will study in Knapsack in Module 6.
Deciding canonicity. Comparing greedy with DP at every amount forever is impossible, but you do not need to: Kozen and Zaks (1994) proved that if a system with coins has any counterexample, the smallest one is below . So compare greedy and DP for every amount up to that bound; if they always agree, the system is canonical. That is total work. (Pearson (2005) gave an test whose cost does not depend on coin sizes.) Implement smallest_counterexample(coins). Expected: none for US and euro-cent coins ; 6 for ; 48 for the British set; 14 for .
The lesson for the paradigm: greedy is a bet that one branch of the search tree is always safe. The exchange argument that justifies the bet for US coins (any optimal solution can be rearranged to use the greedy coin first) simply fails for , and DP — which keeps every branch's best answer — is the fallback. See When greedy fails.
Part 6 — Randomized restarts
Run the bitmask N-Queens model, deterministic order, to the first solution for and look at the node counts. They do not grow smoothly. takes 8,563 nodes and takes 1,737,189; drops back to 25,429; and do not finish within 3,000,000. The search is not getting harder in any meaningful sense — there are more solutions as grows. It is getting unlucky: the lowest-column-first order sends it into an enormous subtree with no solution near the top.
Fix it with randomness:
- Randomize the value order: shuffle the free columns at every node.
- Restart with a budget: run with a node budget; if it runs out, throw the search away and start again with a fresh shuffle and double the budget.
Doubling guarantees termination: some run eventually has a budget larger than the whole tree, and that run is just a complete randomized backtracking search. (The reference also detects that case, so an unsolvable size such as returns "no solution" instead of looping forever.) Over 20 seeds, report the median and maximum total nodes for .
Why this works: the run time of randomized backtracking on many problems is heavy-tailed — most runs are short, a few are astronomically long (Gomes, Selman and Kautz, 1998). Restarts cut off the tail. Without restarts, a single random order can still be unlucky: in the author's runs of 20 random orders for , the median was 600 nodes, one run needed about 39,000, and one did not finish within 1,000,000 nodes; with restarts the worst of 20 seeds was 10,949. Luby, Sinclair and Zuckerman (1993) showed a universal restart schedule (1, 1, 2, 1, 1, 2, 4, …) that is within a logarithmic factor of the best fixed cutoff for any run-time distribution; doubling is the simpler schedule most people start with. Modern SAT solvers restart thousands of times per problem.
Acceptance tests
Your program passes when:
| Test | Expected |
|---|---|
| N-Queens counts, | 1, 0, 0, 2, 10, 4, 40, 92, 352, 724 |
| Naive vs bitmask N-Queens, | identical solution lists and identical node counts |
| 8-Queens, all solutions | 92 solutions, 2,057 nodes |
| 8-Queens, first solution | after 114 nodes |
wikipedia, two solutions requested | exactly one found; naive 4,632 nodes, bitmask 4,632, MRV 52 |
norvig-easy | naive and bitmask 929, MRV 50 |
norvig-hard | naive and bitmask exceed 3,000,000; MRV 3,723 |
inkala-2012 | naive and bitmask 2,068,781; MRV 24,881 |
wiki-anti-brute | naive and bitmask exceed 3,000,000; MRV 93,952 |
Givens 55 in the first row | rejected as contradictory |
| Empty grid, MRV, first solution | a valid grid, 82 nodes |
| Greedy vs DP | at 6: 3 vs 2; British set at 48: 3 vs 2 |
| Smallest counterexample | US: none; euro: none; : 6; British: 48; : 14 |
| Deterministic first solution, bitmask N-Queens | : 199,636 nodes; : 1,737,189; : over 3,000,000 |
| Randomized restarts, , 20 seeds | every result is a valid placement; returns "no solution" |
Node counts depend on the order of variables and values: cells scanned in index order, MRV ties broken by the lowest index, digits and columns tried smallest first. If yours differ, check those three things first. The randomized numbers depend on the random number generator, so the tests check validity, not counts.
Reference solution
The reference is a single Python 3.10+ file. It runs in about 70 seconds on a laptop, almost all of it the naive and bitmask Sudoku models grinding through their 3,000,000-node budgets; the MRV model and everything else take under a second.
Reference solution (Python)
"""Module 5 capstone reference solution: a backtracking engine, N-Queens and Sudoku
solvers (naive, bitmask, MRV), greedy-vs-DP coin systems, and randomized restarts."""
import random
import time
from typing import Iterable, List, Optional, Protocol
# ---------------------------------------------------------------- Part 1: the engine
class Problem(Protocol):
def choose(self) -> Optional[int]: ... # next variable, or None when complete
def options(self, var: int) -> Iterable[int]: ... # values to try, in order
def apply(self, var: int, val: int) -> None: ...
def undo(self, var: int, val: int) -> None: ...
def snapshot(self) -> object: ... # a copy of the current full assignment
class Stats:
def __init__(self) -> None:
self.nodes = 0 # calls to search(): partial assignments visited
self.solutions = 0
def search(p: Problem, stats: Stats, limit_solutions: int = 1,
out: Optional[list] = None, node_budget: Optional[int] = None) -> bool:
"""Depth-first backtracking. Returns True to stop (enough solutions, or budget exhausted)."""
stats.nodes += 1
if node_budget is not None and stats.nodes > node_budget:
return True
var = p.choose()
if var is None: # every variable assigned: a solution
stats.solutions += 1
if out is not None:
out.append(p.snapshot())
return stats.solutions >= limit_solutions
if var < 0: # choose() found a dead end (no candidates)
return False
for val in list(p.options(var)):
p.apply(var, val)
stop = search(p, stats, limit_solutions, out, node_budget)
p.undo(var, val)
if stop:
return True
return False
def solve(p: Problem, limit_solutions: int = 1, node_budget: Optional[int] = None):
stats, out = Stats(), []
search(p, stats, limit_solutions, out, node_budget)
return out, stats
# ---------------------------------------------------------------- Part 2: N-Queens
class QueensNaive:
"""Variable = row; value = column. Safety check scans the queens already placed: O(n) per test."""
def __init__(self, n: int) -> None:
self.n, self.cols = n, []
def choose(self):
return None if len(self.cols) == self.n else len(self.cols)
def options(self, row):
for c in range(self.n):
if all(c != pc and abs(c - pc) != row - pr for pr, pc in enumerate(self.cols)):
yield c
def apply(self, row, col): self.cols.append(col)
def undo(self, row, col): self.cols.pop()
def snapshot(self): return tuple(self.cols)
class QueensBitmask:
"""Same search, but attacked columns and diagonals live in three bitmasks: O(1) per test."""
def __init__(self, n: int, rng: Optional[random.Random] = None) -> None:
self.n, self.full, self.rng = n, (1 << n) - 1, rng
self.cols: List[int] = []
self.col = self.d1 = self.d2 = 0 # d1: row+col diagonals, d2: row-col+n-1
def choose(self):
return None if len(self.cols) == self.n else len(self.cols)
def options(self, row):
res = [c for c in range(self.n) # three bit tests per column
if not (self.col >> c) & 1
and not (self.d1 >> (row + c)) & 1
and not (self.d2 >> (row - c + self.n - 1)) & 1]
if self.rng is not None:
self.rng.shuffle(res)
return res
def apply(self, row, c):
self.cols.append(c)
self.col |= 1 << c
self.d1 |= 1 << (row + c)
self.d2 |= 1 << (row - c + self.n - 1)
def undo(self, row, c):
self.cols.pop()
self.col &= ~(1 << c)
self.d1 &= ~(1 << (row + c))
self.d2 &= ~(1 << (row - c + self.n - 1))
def snapshot(self): return tuple(self.cols)
def count_queens_fast(n: int) -> int:
"""The classic shifting-mask counter (no engine overhead): diagonals shift as rows advance."""
full = (1 << n) - 1
def go(cols: int, ld: int, rd: int) -> int:
if cols == full:
return 1
total = 0
free = full & ~(cols | ld | rd)
while free:
bit = free & -free # lowest free column
free ^= bit
total += go(cols | bit, ((ld | bit) << 1) & full, (rd | bit) >> 1)
return total
return go(0, 0, 0)
def valid_queens(cols) -> bool:
n = len(cols)
return (len(set(cols)) == n and len({r + c for r, c in enumerate(cols)}) == n
and len({r - c for r, c in enumerate(cols)}) == n)
# ---------------------------------------------------------------- Part 3: Sudoku
def parse(grid: str) -> List[int]:
cells = [0 if ch in ".0" else int(ch) for ch in grid if ch in ".0123456789"]
assert len(cells) == 81, "a puzzle has 81 cells"
return cells
def box_of(i: int) -> int:
return (i // 27) * 3 + (i % 9) // 3
class SudokuNaive:
"""First empty cell; try 1..9; check row, column and box by scanning (27 reads per test)."""
def __init__(self, grid: str) -> None:
self.g = parse(grid)
def choose(self):
for i, v in enumerate(self.g):
if v == 0:
return i
return None
def options(self, i):
r, c = divmod(i, 9)
br, bc = r - r % 3, c - c % 3
for d in range(1, 10):
if any(self.g[r * 9 + k] == d for k in range(9)):
continue
if any(self.g[k * 9 + c] == d for k in range(9)):
continue
if any(self.g[(br + a) * 9 + bc + b] == d for a in range(3) for b in range(3)):
continue
yield d
def apply(self, i, d): self.g[i] = d
def undo(self, i, d): self.g[i] = 0
def snapshot(self): return "".join(map(str, self.g))
class SudokuBitmask:
"""Same order as naive, but row/column/box 'used' sets are 9-bit masks.
candidates(i) = ~(row | col | box): one OR and one NOT instead of 27 reads.
With mrv=True, choose() picks the empty cell with the fewest candidates (minimum remaining
values) and reports a dead end (-1) as soon as some empty cell has none (forward checking)."""
ALL = 0x3FE # bits 1..9
def __init__(self, grid: str, mrv: bool = False) -> None:
self.g = parse(grid)
self.mrv = mrv
self.row = [0] * 9
self.col = [0] * 9
self.box = [0] * 9
for i, d in enumerate(self.g):
if d:
bit = 1 << d
r, c, b = i // 9, i % 9, box_of(i)
if (self.row[r] | self.col[c] | self.box[b]) & bit:
raise ValueError("the givens contradict each other")
self.row[r] |= bit; self.col[c] |= bit; self.box[b] |= bit
self.empty = [i for i, d in enumerate(self.g) if d == 0]
def cand(self, i: int) -> int:
return self.ALL & ~(self.row[i // 9] | self.col[i % 9] | self.box[box_of(i)])
def choose(self):
if not self.mrv:
for i in self.empty:
if self.g[i] == 0:
return i
return None
best, best_count = None, 10
for i in self.empty:
if self.g[i] == 0:
k = self.cand(i).bit_count()
if k < best_count:
best, best_count = i, k
if k <= 1: # 0 = dead end, 1 = forced: cannot do better
break
if best is None:
return None
return -1 if best_count == 0 else best
def options(self, i):
m = self.cand(i)
while m:
bit = m & -m
m ^= bit
yield bit.bit_length() - 1
def apply(self, i, d):
bit = 1 << d
self.g[i] = d
self.row[i // 9] |= bit; self.col[i % 9] |= bit; self.box[box_of(i)] |= bit
def undo(self, i, d):
bit = 1 << d
self.g[i] = 0
self.row[i // 9] &= ~bit; self.col[i % 9] &= ~bit; self.box[box_of(i)] &= ~bit
def snapshot(self): return "".join(map(str, self.g))
def valid_sudoku(sol: str, puzzle: str) -> bool:
g = [int(ch) for ch in sol]
givens = parse(puzzle)
if any(p and p != v for p, v in zip(givens, g)):
return False
units = ([[r * 9 + c for c in range(9)] for r in range(9)]
+ [[r * 9 + c for r in range(9)] for c in range(9)]
+ [[i for i in range(81) if box_of(i) == b] for b in range(9)])
return all(sorted(g[i] for i in u) == list(range(1, 10)) for u in units)
PUZZLES = {
# Wikipedia's "Sudoku" article example puzzle
"wikipedia": "53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79",
# Peter Norvig, "Solving Every Sudoku Puzzle": grid1 (easy) and grid2 (hard)
"norvig-easy": "..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..",
"norvig-hard": "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......",
# Arto Inkala's 2012 "world's hardest sudoku" (as reported in the press)
"inkala-2012": "8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..",
# Wikipedia "Sudoku solving algorithms": a puzzle built to defeat first-empty-cell brute force
"wiki-anti-brute": "..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9",
}
# ---------------------------------------------------------------- Part 4: greedy vs DP coins
def greedy_coins(coins: List[int], amount: int) -> Optional[int]:
count = 0
for c in sorted(coins, reverse=True):
count += amount // c
amount %= c
return count if amount == 0 else None
def dp_coins(coins: List[int], amount: int) -> Optional[int]:
INF = amount + 1
best = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1
return None if best[amount] == INF else best[amount]
def smallest_counterexample(coins: List[int]) -> Optional[int]:
"""Smallest amount where greedy uses more coins than optimal, or None if the system is canonical.
Kozen & Zaks (1994): if a counterexample exists, one exists below c[-1] + c[-2]."""
cs = sorted(coins)
if cs[0] != 1:
raise ValueError("include a 1-coin so every amount is payable")
bound = cs[-1] + cs[-2] if len(cs) >= 2 else 1
for a in range(1, bound):
if greedy_coins(cs, a) != dp_coins(cs, a):
return a
return None
# ---------------------------------------------------------------- Part 5: randomized restarts
def queens_with_restarts(n: int, seed: int, first_budget: int = 64):
"""Random column order; restart with a fresh shuffle when a run exceeds its node budget.
The budget doubles after each failure, so some run eventually has enough to finish."""
rng = random.Random(seed)
budget, total, restarts = first_budget, 0, 0
while True:
p = QueensBitmask(n, rng)
sols, st = solve(p, node_budget=budget)
total += min(st.nodes, budget)
if sols:
return sols[0], total, restarts
if st.nodes <= budget: # whole tree searched within budget: no solution
return None, total, restarts
restarts += 1
budget *= 2
# ---------------------------------------------------------------- acceptance tests + benchmark
BUDGET = 3_000_000 # nodes per Sudoku run before we give up
def benchmark_sudoku() -> dict:
solvers = {"naive": lambda p: SudokuNaive(p),
"bitmask": lambda p: SudokuBitmask(p),
"mrv": lambda p: SudokuBitmask(p, mrv=True)}
print(f"{'puzzle':<16}{'givens':>6}" + "".join(f"{k + ' nodes':>16}{k + ' s':>10}" for k in solvers))
results = {}
for name, puzzle in PUZZLES.items():
line = f"{name:<16}{sum(1 for v in parse(puzzle) if v):>6}"
for key, make in solvers.items():
t = time.perf_counter()
out, st = solve(make(puzzle), limit_solutions=2, node_budget=BUDGET) # 2: proves uniqueness
secs = time.perf_counter() - t
if st.nodes > BUDGET:
results[name, key] = None
line += f"{'> 3,000,000':>16}{secs:>10.2f}"
else:
assert len(out) == 1 and valid_sudoku(out[0], puzzle)
results[name, key] = st.nodes
line += f"{st.nodes:>16,}{secs:>10.3f}"
print(line)
return results
def main() -> None:
# Part 2: N-Queens solution counts (OEIS A000170)
expected = [1, 0, 0, 2, 10, 4, 40, 92, 352, 724]
for n in range(1, 11):
assert count_queens_fast(n) == expected[n - 1]
for n in range(1, 9):
a, sa = solve(QueensNaive(n), limit_solutions=10**9)
b, sb = solve(QueensBitmask(n), limit_solutions=10**9)
assert len(a) == len(b) == expected[n - 1] and a == b and sa.nodes == sb.nodes
assert all(valid_queens(s) for s in a)
_, s8 = solve(QueensBitmask(8), limit_solutions=10**9)
assert (s8.solutions, s8.nodes) == (92, 2057)
sol, s8first = solve(QueensBitmask(8))
assert sol[0] == (0, 4, 7, 5, 2, 6, 1, 3) and s8first.nodes == 114
print(f"8-queens: {s8.solutions} solutions in {s8.nodes} nodes; first {sol[0]} after {s8first.nodes} nodes")
# Part 3: Sudoku, three solvers
res = benchmark_sudoku()
assert res["wikipedia", "naive"] == res["wikipedia", "bitmask"] == 4632
assert res["wikipedia", "mrv"] == 52
assert res["norvig-easy", "bitmask"] == 929 and res["norvig-easy", "mrv"] == 50
assert res["norvig-hard", "bitmask"] is None and res["norvig-hard", "mrv"] == 3723
assert res["inkala-2012", "naive"] == res["inkala-2012", "bitmask"] == 2068781
assert res["inkala-2012", "mrv"] == 24881
assert res["wiki-anti-brute", "mrv"] == 93952
try:
SudokuBitmask("55" + "." * 79)
raise AssertionError("contradiction not detected")
except ValueError:
pass
out, st = solve(SudokuBitmask("." * 81, mrv=True))
assert len(out) == 1 and valid_sudoku(out[0], "." * 81)
print(f"empty grid: first solution after {st.nodes} nodes")
# Part 4: greedy vs DP
for coins, amt in (([1, 5, 10, 25], 63), ([1, 3, 4], 6), ([1, 3, 6, 12, 24, 30], 48)):
print(f"coins {coins} amount {amt}: greedy {greedy_coins(coins, amt)}, optimal {dp_coins(coins, amt)}")
assert greedy_coins([1, 3, 4], 6) == 3 and dp_coins([1, 3, 4], 6) == 2
assert greedy_coins([1, 3, 6, 12, 24, 30], 48) == 3 and dp_coins([1, 3, 6, 12, 24, 30], 48) == 2
assert smallest_counterexample([1, 5, 10, 25]) is None
assert smallest_counterexample([1, 2, 5, 10, 20, 50, 100, 200]) is None
assert smallest_counterexample([1, 3, 4]) == 6
assert smallest_counterexample([1, 3, 6, 12, 24, 30]) == 48
assert smallest_counterexample([1, 7, 10]) == 14
# Part 5: randomized restarts
det = {n: solve(QueensBitmask(n), node_budget=BUDGET)[1].nodes for n in (20, 22, 28, 30)}
assert queens_with_restarts(3, 0)[0] is None # unsolvable sizes terminate
assert det == {20: 199636, 22: 1737189, 28: BUDGET + 1, 30: BUDGET + 1}
for n in (20, 22, 28, 30, 40, 60):
totals = []
for seed in range(20):
sol, total, _ = queens_with_restarts(n, seed)
assert valid_queens(sol) and len(sol) == n
totals.append(total)
totals.sort()
shown = f"{det[n]:,}" if n in det and det[n] <= BUDGET else "> 3,000,000"
print(f"n={n}: deterministic {shown}; restarts over 20 seeds: median {totals[10]:,}, max {totals[-1]:,}")
print("all capstone tests passed")
if __name__ == "__main__":
main()
The output on the author's machine (seconds will differ on yours; nodes will not):
8-queens: 92 solutions in 2057 nodes; first (0, 4, 7, 5, 2, 6, 1, 3) after 114 nodes
puzzle givens naive nodes naive s bitmask nodes bitmask s mrv nodes mrv s
wikipedia 30 4,632 0.022 4,632 0.004 52 0.000
norvig-easy 32 929 0.004 929 0.001 50 0.000
norvig-hard 17 > 3,000,000 16.76 > 3,000,000 2.77 3,723 0.011
inkala-2012 21 2,068,781 13.789 2,068,781 7.743 24,881 0.280
wiki-anti-brute 17 > 3,000,000 37.99 > 3,000,000 5.67 93,952 0.534
empty grid: first solution after 82 nodes
coins [1, 5, 10, 25] amount 63: greedy 6, optimal 6
coins [1, 3, 4] amount 6: greedy 3, optimal 2
coins [1, 3, 6, 12, 24, 30] amount 48: greedy 3, optimal 2
n=20: deterministic 199,636; restarts over 20 seeds: median 141, max 851
n=22: deterministic 1,737,189; restarts over 20 seeds: median 257, max 1,335
n=28: deterministic > 3,000,000; restarts over 20 seeds: median 345, max 1,245
n=30: deterministic > 3,000,000; restarts over 20 seeds: median 257, max 1,805
n=40: deterministic > 3,000,000; restarts over 20 seeds: median 421, max 3,368
n=60: deterministic > 3,000,000; restarts over 20 seeds: median 726, max 10,949
all capstone tests passed
Notes for other languages
- Java. Make
Probleman interface whoseoptionsreturns anint[](already materialised). Masks areint; useInteger.bitCountfor MRV andInteger.numberOfTrailingZeros(m & -m)to turn the lowest bit into a digit. Recursion depth is at most 82, so the default stack is fine. Expect it to run many times faster than the Python reference; node counts stay identical. - C++. A template
search<P>(P&)avoids virtual calls and lets the compiler inlineapply/undo. Usestd::popcount(C++20) or__builtin_popcount, andstd::countr_zerofor the lowest set bit. Keep the 27 masks in astd::array<uint16_t, 27>. - TypeScript. Bitwise operators work on 32-bit integers, which is plenty for Sudoku masks and for N-Queens up to (the
d1/d2diagonal masks need bits, so for those use two numbers, aUint32ArrayorBigIntbeyond ). There is no built-in popcount; use the standard SWAR trickx - ((x >> 1) & 0x55555555)… or a 512-entry lookup table for 9-bit masks. Avoid generators in the hot loop; return arrays. - All languages. The node counts in the table are language-independent if you keep the same orders. The randomized part needs its own seeded generator; compare distributions, not exact numbers.
Benchmarks and what the numbers should look like
Fewer nodes versus cheaper nodes. The benchmark separates the two ways to speed up a search:
- Naive → bitmask keeps the tree and makes each node cheaper. On
inkala-2012both visit 2,068,781 nodes; the bitmask model takes about 2.2 s instead of 11.5 s in Python, a factor of about 5. That is a constant-factor win: worth having, but it cannot rescue a search that is exponentially too big. - Bitmask → MRV changes the tree. On the same puzzle MRV visits 24,881 nodes, 83 times fewer; on
norvig-hardit visits 3,723 nodes where the others exceed 3,000,000. With the full count measured separately, first-empty-cell search needs 142,738,236 nodes to provenorvig-hardunique (about 2.5 minutes for the Python bitmask model), so MRV's tree is about 38,000 times smaller. Each MRV node costs more (it scans every empty cell and popcounts it), and it is still dramatically faster.
Why first-empty-cell is so fragile. Its running time depends on where the puzzle's difficulty sits. norvig-hard has 17 givens and its first rows are nearly empty, so the search branches nine ways at the top and only finds out much later that most branches are dead. wiki-anti-brute was constructed for exactly this: its first row is empty and the solution's first row is 987654321, so trying digits in order from 1 is the worst possible choice. MRV does not care about the cell order, because it does not use it.
What to expect in your language. Node counts are fixed by the table; seconds scale by the language's constant factor. In a compiled language the MRV model should solve all five puzzles (about 123,000 nodes in total) well under a second. The world's fastest Sudoku solvers go further — dancing links (Knuth's Algorithm X), SIMD candidate updates, hidden-single propagation — and solve tens of thousands of hard puzzles per second, but the shape of the speed-up is the one you just measured: first shrink the tree, then shrink the node.
N-Queens. Expect the deterministic first-solution counts to jump around by factors of 100 between neighbouring , and the randomized-restart medians to grow slowly — a few hundred nodes at , under a thousand at in the reference runs. For very large (thousands), even restarts become slow, and the right tool is min-conflicts local search: place all queens, then repeatedly move a conflicted queen to its least-attacked square. Minton et al. (1992) reported solving the million-queens problem with it in minutes on early-1990s hardware. There is also an explicit construction for every (a closed-form pattern; Bernhardsson, 1991), which is the real answer if you only need one placement.
Stretch goals
- Hidden singles. Add a second propagation rule: if a digit has only one possible cell in some row, column or box, place it. Measure nodes on
wiki-anti-brutewith and without it. You will need to record propagated placements on a trail soundocan reverse all of them. - Least-constraining value. Order each cell's candidates by how few options they remove from its neighbours. This helps when you want one solution; it cannot help when you prove uniqueness, because the whole tree is searched anyway. Check that claim with your node counts.
- Dancing links. Reformulate Sudoku as exact cover (324 constraints, 729 candidate rows) and implement Knuth's Algorithm X with dancing links. Compare its node count to MRV — Algorithm X's "choose the column with the fewest 1s" is MRV generalised to constraints instead of cells.
- Count all N-Queens solutions to with the shifting-mask counter, using symmetry (only place the first queen in the left half, and double) to halve the work. Expected for : 2,279,184.
- Generate puzzles. Fill an empty grid with randomized MRV, then remove givens one at a time in random order, keeping a removal only if the puzzle still has exactly one solution (ask the engine for two). How few givens do you typically reach?
- Coin systems at scale. Implement Pearson's canonicity test and check it against the Kozen–Zaks brute force on random coin systems.
- Min-conflicts. Implement it for N-Queens and find a solution for .
Further reading
- Donald E. Knuth, The Art of Computer Programming, Volume 4B (2022), §7.2.2 "Backtrack programming" and §7.2.2.1 "Dancing links" — the definitive treatment of backtracking, including N-Queens and Sudoku.
- Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (2020), Chapter 6 "Constraint Satisfaction Problems" — MRV, forward checking, arc consistency, min-conflicts.
- Peter Norvig, Solving Every Sudoku Puzzle — constraint propagation plus search in a page of Python, and the source of two of our puzzles.
- R. M. Haralick and G. L. Elliott, "Increasing tree search efficiency for constraint satisfaction problems", Artificial Intelligence 14(3), 1980 — forward checking and the fail-first principle.
- C. P. Gomes, B. Selman and H. Kautz, "Boosting Combinatorial Search Through Randomization", AAAI 1998 — heavy-tailed run times and restarts.
- M. Luby, A. Sinclair and D. Zuckerman, "Optimal speedup of Las Vegas algorithms", Information Processing Letters 47(4), 1993.
- S. Minton, M. D. Johnston, A. B. Philips and P. Laird, "Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems", Artificial Intelligence 58, 1992.
- D. Kozen and S. Zaks, "Optimal bounds for the change-making problem", Theoretical Computer Science 123(2), 1994; D. Pearson, "A polynomial-time algorithm for the change-making problem", Operations Research Letters 33(3), 2005.
- G. McGuire, B. Tugemann and G. Civario, "There is no 16-clue Sudoku: solving the Sudoku minimum number of clues problem", arXiv:1201.0749 (2012).
Course navigation. Module overview: Algorithmic Paradigms. Lessons used here: Recursion & Backtracking, Bit Manipulation, Greedy Algorithms, Randomized Algorithms. Course: DSA: Zero to Mastery. Next: Module 6 · Dynamic Programming.