Lab 04 — Algorithm X & Dancing Links (Exact Cover)

Goal

Implement Knuth’s Algorithm X for the exact cover problem and use it to solve Sudoku by reduction to a 729-row × 324-column matrix — the standard architecture of every serious constraint-puzzle solver.

Background

Exact cover: given a 0/1 matrix, choose a subset of rows so that every column contains exactly one 1 among the chosen rows.

Many puzzles reduce to it: Sudoku, pentomino tiling, n-queens. NP-complete in general, but instances arising from puzzles solve near-instantly with the right search.

Algorithm X (Knuth, 2000): depth-first search — pick an unsatisfied column, try each row that covers it, remove (“cover”) all conflicting rows/columns, recurse, restore on backtrack.

Dancing Links (DLX): the implementation trick. Represent the matrix as circular doubly-linked lists (one node per 1, column headers, a root). Unlinking a node is two pointer writes; relinking is the same two writes reversed — x.left.right = x; x.right.left = x — so backtracking restores state in O(1) per node with no copying. Knuth’s paper is titled after the pointers “dancing” back.

Column choice matters: always branch on the column with the fewest 1s (minimum remaining values). This collapses the branching factor and is the difference between microseconds and hours.

Interview Context

Standard FAANG: Sudoku Solver (LC 37) and N-Queens (LC 51/52) are asked; plain backtracking is the expected answer — DLX is the “strong senior” flex, not a requirement
OR / scheduling / constraint-solver teams: core background
Game/puzzle companies: directly relevant
ICPC: occasional exact-cover disguises
Knuth literacy signal: TAOCP 4B fascicle 5 is entirely about this

When to Skip This Topic

Skip if any of these are true:

You can’t write plain recursive backtracking with undo cleanly (Phase 2 Lab 08 first)
Your target roles have no solver/OR/puzzle component — LC 37 is passable with ordinary backtracking + bitmasks

Learn Algorithm X in its dict-of-sets form regardless if you have 2 hours: it’s 30 lines and permanently upgrades how you think about backtracking-with-undo.

Problem Statement

Sudoku Solver (LC 37), the solver-grade version.

Solve a 9×9 Sudoku. Encode it as exact cover:

Rows of the matrix = candidate placements (r, c, d) — 9×9×9 = 729
Columns = constraints, 4 families × 81 = 324:
1. cell (r, c) is filled
2. row r contains digit d
3. column c contains digit d
4. box b contains digit d

A solution = 81 rows covering all 324 columns exactly once.

Constraints

Standard 9×9 with ≥ 17 givens (uniqueness threshold); solver must also detect unsolvable/multi-solution grids
Time: hardest 9×9 instances in ≤ 100 ms
Generalize: same code must take 16×16 Sudoku or pentomino tilings by changing only the matrix construction

Clarifying Questions

Is the input guaranteed solvable and unique? (LC: yes. Solver-grade: detect both failure and second solutions.)
Just one solution or enumerate all? (Algorithm X naturally enumerates; ask.)
Board size fixed at 9×9? (Design the reduction generically; n² × n² boards change constants only.)
Output format — mutate the grid or return placements? (Either; placements fall out of the chosen rows.)

Examples

Tiny exact cover, columns {1..7}, rows:

A = {1,4,7}   B = {1,4}     C = {4,5,7}
D = {3,5,6}   E = {2,3,6,7} F = {2,7}

Branch on column 1 (2 rows): try A → covers {1,4,7}, kills C, B, E, F(7)… dead end on column 2; backtrack, try B → covers {1,4}, then D covers {3,5,6}, F covers {2,7}. Solution: {B, D, F}.

Sudoku column indexing for placement (r, c, d), all 0-based:

cell:  81·0 + 9r + c
row:   81·1 + 9r + d
col:   81·2 + 9c + d
box:   81·3 + 9(3⌊r/3⌋ + ⌊c/3⌋) + d

Brute Force

Cell-by-cell backtracking, re-scanning row/column/box validity at each step. Passes LC 37, but on hard instances (e.g. grids designed against naive orderings) explores orders of magnitude more nodes than MRV-guided exact cover.

Brute Force Complexity

Time: O(9^(empty cells)) worst case, heavily instance-dependent
Space: O(81) recursion

Optimization Path

Reify all four constraint families as columns — validity checking disappears; it is the matrix.
Algorithm X with MRV column selection — always branch where fewest candidates remain.
Dict-of-sets representation (X: column → set of rows; Y: row → column list) — same asymptotics as pointer DLX, 3× shorter to write.
Pointer-based DLX with real dancing links when performance matters (pentominoes, 16×16, enumeration).
Givens are handled by selecting their rows first — same code path as search choices.

Final Expected Approach

Dict-of-sets Algorithm X (interview-writable) + Sudoku reduction:

def solve_exact_cover(X, Y, solution):
    if not X:
        yield list(solution)
        return
    col = min(X, key=lambda c: len(X[c]))
    for row in list(X[col]):
        solution.append(row)
        removed = select(X, Y, row)
        yield from solve_exact_cover(X, Y, solution)
        deselect(X, Y, row, removed)
        solution.pop()

def select(X, Y, row):
    removed = []
    for col in Y[row]:
        for other_row in X[col]:
            for other_col in Y[other_row]:
                if other_col != col:
                    X[other_col].discard(other_row)
        removed.append(X.pop(col))
    return removed

def deselect(X, Y, row, removed):
    for col in reversed(Y[row]):
        X[col] = removed.pop()
        for other_row in X[col]:
            for other_col in Y[other_row]:
                if other_col != col:
                    X[other_col].add(other_row)

def sudoku_matrix():
    Y = {}
    for r in range(9):
        for c in range(9):
            for d in range(9):
                b = 3 * (r // 3) + c // 3
                Y[(r, c, d)] = [
                    ("cell", r, c), ("row", r, d),
                    ("col", c, d), ("box", b, d)]
    X = {}
    for row, cols in Y.items():
        for col in cols:
            X.setdefault(col, set()).add(row)
    return X, Y

def solve_sudoku(grid):
    X, Y = sudoku_matrix()
    partial = []
    for r in range(9):
        for c in range(9):
            if grid[r][c]:
                select(X, Y, (r, c, grid[r][c] - 1))
    for sol in solve_exact_cover(X, Y, partial):
        for (r, c, d) in sol:
            grid[r][c] = d + 1
        return grid
    return None

The pointer DLX version replaces sets with column-header nodes and up/down/left/right links; cover(col) unlinks the column header and every row intersecting it; uncover relinks in exact reverse order.

Data Structures

Dict version: X column → set of active rows; Y row → static column list; undo stack of removed sets
DLX version: node {L, R, U, D, column}; column headers with live size counters; circular root list of uncovered columns

Correctness Argument

Invariant: at every node of the search tree, (X, Y) represents exactly the sub-matrix of rows/columns compatible with the current partial solution.
Branching on one column and trying each of its rows is exhaustive: any exact cover must cover that column by exactly one row, so the row choices partition the solution space — no solution is missed, none is double-counted.
deselect undoes select by replaying it in exact reverse order, restoring the invariant — the same argument makes DLX’s O(1) relink sound (a node’s left/right neighbors are untouched while it is unlinked).
Sudoku ⇔ exact cover: a set of 81 placements covers all 324 columns exactly once iff every cell is filled once and every row/column/box contains each digit once — the definition of a solved grid.

Complexity

Worst case: exponential (exact cover is NP-complete)
In practice: MRV drives hard 9×9 Sudokus to hundreds–thousands of nodes, < 10 ms in Python; DLX-in-C solves millions of grids/minute
Space: O(number of 1s) = O(729 × 4) for Sudoku — trivial

Implementation Requirements

MRV column choice (min by live size) — non-negotiable; naive first-column order is exponentially worse
deselect must iterate columns in reverse of select
Givens applied through select, and their removed lists retained if the board must be restorable
Detect contradiction early: a live column with zero rows fails the min-branch immediately (empty iteration) — that’s the pruning, don’t special-case around it
For enumeration: keep yielding; for uniqueness checking: stop after finding 2

Tests

The 7-column hand example above → exactly {B, D, F}
LC 37 sample grid → known solution
Empty grid → yields a valid solved grid (any)
17-given minimal puzzle (hardest class) → solved ≤ 100 ms
Unsolvable grid (two 5s in a row among givens) → select raises / search yields nothing; handle both
Multi-solution grid → enumeration yields ≥ 2
Property test: for random solved grids with k cells removed, solver output is a valid completion

Follow-up Questions

Why does choosing the smallest column matter so much? → Search-tree size is the product of branching factors along paths; branching on a 1-row column is a forced move (factor 1). MRV takes forced moves first, so contradictions surface at depth 1 instead of depth 40.
How do dancing links achieve O(1) undo? → An unlinked node keeps its own L/R/U/D pointers; neighbors never point at it while it’s out, so x.L.R = x; x.R.L = x restores it. Valid only if relinks happen in exact LIFO order — which backtracking guarantees.
N-queens as exact cover? → Ranks and files are ordinary columns; diagonals become secondary columns — constraints that may be covered at most once rather than exactly once. DLX handles them by giving secondary columns no presence in the root header list.
Pentomino / polyomino tiling? → Columns = 60 board cells + 12 piece names; rows = every placement of every piece (~1500). Knuth’s original showcase; enumerates all 65 distinct 6×10 tilings in milliseconds.
How does this compare to a SAT solver? → Encode exact cover as CNF and modern CDCL solvers are competitive or better on hard instances (they learn clauses; DLX doesn’t). DLX wins on enumeration density and memory locality. Real solver teams benchmark both.
Sudoku uniqueness checking? → Run enumeration, stop at the second solution. Puzzle generators do this in an inner loop — another reason enumeration-native Algorithm X beats first-solution backtracking here.

Product Extension

Puzzle generators (dedup + uniqueness checks in newspapers’ Sudoku pipelines)
Crew/exam scheduling and set-partitioning formulations in OR (exact cover is set partitioning)
PCB drilling / cutting-stock layout tools
TAOCP Volume 4B: DLX is the backbone of Knuth’s entire combinatorial-search treatment

Language/Runtime Follow-ups

Python: dict-of-sets version shown is the right call; pointer DLX in Python loses to it on constant factors.
C/C++: pointer DLX with nodes in a flat arena array (indices, not pointers) — cache behavior dominates.
Java: object-node DLX is idiomatic and fast enough; watch GC pressure when enumerating millions of solutions.
JavaScript: typed-array arena DLX for performance; dict version for clarity.

Common Bugs

Deselect order not reversed: state restored incorrectly; symptoms appear many nodes later as phantom missing rows — the classic nightmare bug of this algorithm.
Iterating X[col] while select mutates it: must snapshot (list(X[col])) in the branch loop.
Box index formula wrong: 3*(r//3) + c//3, not r//3 + 3*(c//3) — transposed boxes still solve some grids, poisoning tests.
Givens conflicting with each other: applying select for an invalid given raises KeyError mid-setup; validate or catch and report unsolvable.
Digit off-by-one: grid digits 1–9 vs matrix digits 0–8 at both boundaries.
Secondary columns treated as primary (n-queens): demanding diagonals be covered exactly once makes most boards “unsolvable”.

Debugging Strategy

After select+deselect of any row on a fresh matrix, deep-compare X against a pristine copy — catches ordering bugs immediately
Assert Σ|X[col]| invariant restored after every backtrack in debug mode
Solve the 7-column hand example with verbose tracing; diff against the worked trace
Cross-check Sudoku solutions with an independent validator (row/col/box sums and sets)
Count search nodes; hard-but-valid 9×9 should be ≤ ~10^4 nodes — a wrong reduction shows up as millions

Mastery Criteria

Write the dict-of-sets Algorithm X from memory in ≤ 25 min
Derive the 4-family Sudoku reduction (324 columns, index formulas) on a whiteboard in ≤ 10 min
Explain the O(1) unlink/relink argument and its LIFO precondition in ≤ 3 min
Know primary vs secondary columns and the n-queens use
Solve LC 37 with this machinery end-to-end in ≤ 45 min

LeetCode Interview — Extreme Coding