Skip to main content

Walkthrough — Module 09: Backtracking and Dancing Links

Read this AFTER a stage is green — it explains how the reference solution is built and why.

Stage 1: Basic backtrack: n queens​

The reference is a faithful transcription of Algorithm 7.2.2B into a single recursive backtrack_queens(row, n, a, count, visit). The invariant that makes it correct: whenever we are at row, the prefix a[0..row] is a legal partial placement — no two of those queens attack. That invariant is maintained by only ever descending (the B4 "advance") through a column that queens_ok accepts, and it is what lets the base case row == n unconditionally count a solution. The clever economy is that B5 "backtrack" is implicit: because a[row] is overwritten on the next loop iteration and never read above row, there is nothing to undo — the array itself is the reversible state, which is the cheapest possible "try and take back."

The idiom worth stealing is the visit: &mut impl FnMut(&[usize]) closure: one recursion powers both count_queens_solutions (visit does nothing, we just increment count) and first_queens_solution (visit captures the first a it sees). A naive version would write the search twice or build the full solution list even when only one is wanted. The subtle correctness point is the diagonal test written as (row - r) == (col.max(c) - col.min(c)): using max/min on usize columns avoids underflow that (col - c).abs() would invite, and comparing row-distance to column-distance is exactly the "same diagonal" condition without ever materializing diagonal indices.

Stage 2: Backtracking with bitwise state​

count_queens_bitwise explores the identical tree as stage 1 but replaces the per-row column loop and the queens_ok scan with register arithmetic. The invariant is carried in three u32 masks passed down the recursion: cols is the set of occupied columns, diag_down the set of columns hit by an active r+c diagonal as seen from the current row, and diag_up likewise for r−c. The key insight encoded in the shifts is that the diagonals are stored relative to the current row, so descending one row re-aligns them: (diag_down | bit) << 1 and (diag_up | bit) >> 1. That relative encoding is why free = all & !(cols | diag_down | diag_up) reads off the legal columns for this row in one instruction, and why the termination test is simply cols == all.

The idiom to steal is the low-bit isolation bit = free & free.wrapping_neg() followed by free ^= bit, which enumerates a set's members one at a time with no conditional branch per candidate column — the "ruler function" trick. Compared with the array backtracker this beats it by turning each node's O(n) legality check into O(1) work, which is what pushes n = 13 and 14 into reach. The bug it quietly avoids is direction confusion: swapping the two shift directions still type-checks and still runs, but silently produces wrong counts; the reference pins this down by asserting agreement with stage 1 for n ≤ 12 before trusting the larger cases.

ExactCover is Algorithm 7.2.2.1X built on six parallel Vec<usize> arrays (left, right, up, down, col, plus size and node_option) rather than pointer structs — the index-arena style the conventions prefer, and the faithful analogue of Knuth's MIX links. Node 0 is the root h; nodes 1..=num_items are column headers in a circular horizontal list; new seeds each column empty with up[i] = down[i] = i. add_option grows the arrays by one node per item, splicing each node into the bottom of its column (last = up[c] … up[c] = node) so options keep their insertion order, and threading the option's nodes into a small circular horizontal row. The correctness invariant is the dancing-links couplet: cover(c) unlinks with right[left[x]] = right[x]; left[right[x]] = left[x] and never touches x's own left/right/up/down, so the node retains the addresses needed to heal itself.

The structural discipline that makes it provably reversible is order symmetry: cover walks options down from down[c] and their cells right from right[i], decrementing size[col[j]]; uncover walks up from up[c] and left from left[i], re-incrementing size and relinking — the exact LIFO reverse. search does the same at the option level: it covers col[j] rightward before recursing and uncovers leftward after, so every mutation is undone last-in-first-out and the mesh is restored bit-for-bit (the test solves the same instance twice and demands the identical answer). The idiom worth stealing is choose_column's MRV rule — one linear pass over the active header list picking minimum size, with the immediate dead-end check if self.size[c] == 0 { return; } that prunes an item no remaining option can cover. search takes a limit, so solve_first (limit 1) and solve_all (limit usize::MAX) share one engine; naive exact-cover code that copies-and-restores the matrix instead of dancing pays O(matrix) per node where DLX pays O(nodes touched).

Stage 4: Sudoku as an exact-cover problem​

solve_sudoku is pure reduction — it adds zero solving logic and reuses the stage-3 engine unchanged, which is the lesson's whole thesis. It allocates ExactCover::new(324) and lays the 324 items out in four contiguous blocks so each placement (r, c, d) maps to exactly four items by fixed formulas: cell = 9*r+c, row = 81+9*r+(d-1), col = 162+9*c+(d-1), box = 243+9*b+(d-1) with b = (r/3)*3 + c/3. The correctness of the reduction rests on a bijection: a set of options covering all 324 items exactly once is precisely a grid where every cell holds one digit and every row/column/box holds each digit once. Givens are enforced structurally, not by extra constraints — a clued cell offers only its single forced option (vec![given]), an empty cell offers all nine (1..=9), so an inconsistent puzzle simply has no cover and solve_first returns None.

The idiom worth stealing is the parallel side table option_rcd: Vec<(usize, usize, usize)> pushed in lock-step with add_option: because add_option returns options in call order and search reports solutions as option indices, decoding is just option_rcd[opt] — no need to store metadata inside the DLX structure. It beats a bespoke Sudoku backtracker by inheriting DLX's MRV branching for free, which is what solves the puzzle in microseconds, and it avoids the classic bug of forgetting that an already-complete grid is a valid input: each filled cell contributes exactly one option, the cover is forced, and the reference confirms solve_sudoku(&solution) == Some(solution).