On this page

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:

  1. runs a generic depth-first backtracking engine over any problem that implements five methods,
  2. counts N-Queens solutions for and finds one solution for large ,
  3. solves Sudoku with three interchangeable models — naive, bitmask and bitmask + MRV — and proves each solution unique,
  4. benchmarks the three Sudoku models by search nodes and seconds,
  5. decides whether a coin system is safe for greedy change-making, and finds the smallest counterexample when it is not,
  6. 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 supplies choose() (the next variable, None when complete, or a dead-end signal), options(var) (values to try, in order), apply and undo (change the state and change it back), and snapshot() (copy a finished solution).
  • Metric. nodes = number of calls to search, 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_solutions solutions or after node_budget nodes, 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, . or 0 for 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).

NameGivensSource
wikipedia30The example puzzle in Wikipedia's Sudoku article
norvig-easy32Peter Norvig, Solving Every Sudoku Puzzle — grid1
norvig-hard17Peter Norvig, same essay — grid2
inkala-201221Arto Inkala's puzzle that the press called "the world's hardest Sudoku" in 2012
wiki-anti-brute17Wikipedia, 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 options is a lazy generator (Python yield, 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.
  • apply and undo must 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 an undo that does not quite reverse its apply. 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:

CoinsAmountGreedyOptimal (DP)
6325+25+10+1+1+1 = 6 coins6 coins
64+1+1 = 3 coins3+3 = 2 coins
4830+12+6 = 3 coins24+24 = 2 coins
1410+1+1+1+1 = 5 coins7+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:

  1. Randomize the value order: shuffle the free columns at every node.
  2. 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:

TestExpected
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 solutions92 solutions, 2,057 nodes
8-Queens, first solution after 114 nodes
wikipedia, two solutions requestedexactly one found; naive 4,632 nodes, bitmask 4,632, MRV 52
norvig-easynaive and bitmask 929, MRV 50
norvig-hardnaive and bitmask exceed 3,000,000; MRV 3,723
inkala-2012naive and bitmask 2,068,781; MRV 24,881
wiki-anti-brutenaive and bitmask exceed 3,000,000; MRV 93,952
Givens 55 in the first rowrejected as contradictory
Empty grid, MRV, first solutiona valid grid, 82 nodes
Greedy vs DP at 6: 3 vs 2; British set at 48: 3 vs 2
Smallest counterexampleUS: 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 seedsevery 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 Problem an interface whose options returns an int[] (already materialised). Masks are int; use Integer.bitCount for MRV and Integer.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 inline apply/undo. Use std::popcount (C++20) or __builtin_popcount, and std::countr_zero for the lowest set bit. Keep the 27 masks in a std::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/d2 diagonal masks need bits, so for those use two numbers, a Uint32Array or BigInt beyond ). There is no built-in popcount; use the standard SWAR trick x - ((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-2012 both 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-hard it 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 prove norvig-hard unique (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

  1. 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-brute with and without it. You will need to record propagated placements on a trail so undo can reverse all of them.
  2. 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.
  3. 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.
  4. 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.
  5. 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?
  6. Coin systems at scale. Implement Pearson's canonicity test and check it against the Kozen–Zaks brute force on random coin systems.
  7. 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.