A backtracking program usually begins as a story about choices:

try a digit here
if it breaks a rule, undo it
try the next digit

That story is true, but it hides the useful accounting.

For many puzzles, the better representation is not “choose a variable, assign a value.” It is:

choose rows from a 0-1 matrix so every column is covered exactly once

This is the exact cover problem. A row is a possible move. A column is a constraint. A solution is a set of compatible rows whose 1s hit every constraint once and only once.

Knuth’s Algorithm X is the direct depth-first search for exact cover: choose an uncovered column, try each row containing a 1 in that column, delete the columns covered by that row, delete every row that conflicts with those columns, and recurse.1 If the matrix has no columns left, the selected rows are a solution. If the chosen column has no rows, the branch is dead.

The trick is that the puzzle now chooses what to branch on.

A Move Covers Four Facts

Use 4x4 Sudoku because the whole matrix is small enough to draw. The digits are 1 through 4, and each 2x2 box must contain every digit once.

An assignment like:

r2c3 = 1

is a row in the exact-cover matrix. It covers four columns:

C23      the cell at row 2, column 3 is filled
R2=1     row 2 contains digit 1
K3=1     column 3 contains digit 1
B2=1     box 2 contains digit 1

There are \(4 \times 4 \times 4 = 64\) possible assignments, so the matrix has 64 rows. There are also 64 constraints:

\[16\ \text{cell constraints} + 16\ \text{row-digit constraints} + 16\ \text{column-digit constraints} + 16\ \text{box-digit constraints}.\]

Every assignment row has exactly four 1s. The solution to a completed 4x4 Sudoku has 16 selected rows, and across those rows every one of the 64 columns is covered exactly once.

Clues are just preselected rows. If the puzzle says r1c1 = 1, choose that row before search begins. Every row that also touches C11, R1=1, K1=1, or B1=1 is now impossible.

That is the accounting advantage: a clue does not call four special-case Sudoku checks. It performs one exact-cover row selection.

The Narrowest Column Is The Local Question

Algorithm X works with any deterministic rule for choosing the next column, but some rules create much smaller search trees than others. Knuth’s paper discusses this directly: choose a column with the smallest number of remaining 1s, and the next nondeterministic branch has the fewest alternatives.2

That heuristic is not a proof that the global tree is minimal. It is a local branching-factor rule. In constraint-solver language, it is the “most constrained” column.

In the lab, compare:

smallest column: choose the uncovered constraint with fewest active rows
leftmost column: choose the first active constraint in fixed matrix order

On the included 4x4 instances, the smallest-column rule visits fewer recursive search nodes:

instance solutions smallest-column nodes leftmost-column nodes
six clues 2 19 25
diagonal clues 1 11 12
four corners 2 21 31
blank grid 288 2157 2753

These are toy numbers. They are still useful because the measurement is tied to the exact artifact below, and the two solvers enumerate the same completions. The node count is not a DLX pointer-update count; it is the number of recursive search calls made by this small JavaScript implementation after clue rows have been pre-covered.

The Browser Lab

The lab below builds the 64-by-64 exact-cover representation, applies the clue rows, runs Algorithm X, and checks its solution count against an independent Sudoku backtracker. The bars show active constraint columns; shorter bars are tighter columns. The trace ledger shows the column chosen and the assignment row being tried.

columns64
rows64
givens0
solutions0
nodes0
dead ends0
rows removed0
first gridvalid

A selected row removes every still-active row that shares any covered constraint. The conflicting-clues instance shows the same machinery failing before recursive search begins.

The lab copies arrays at each branch because clarity matters more than speed at 64 rows. Knuth’s DLX implementation does something sharper: it stores the sparse matrix in circular doubly linked lists, so covering a column and uncovering it during backtracking are local reversible pointer operations.3

The key observation predates Knuth’s paper. Hitotumatu and Noshita used reversible deletion in doubly linked lists for backtracking in 1979; Knuth credits that idea and generalizes it into the dancing-links implementation of Algorithm X.4

In an array-copying implementation, choosing a row means constructing a smaller matrix:

covered columns = columns where selected row has a 1
remaining rows  = rows that touch none of those columns

In DLX, the same logical operation is a series of unlink operations. Backtracking links the nodes back in the reverse order. The search tree is the same exact cover tree; the representation changes the cost of moving around inside it.

That distinction matters. Algorithm X is the problem-level rule. Dancing links is the data structure that makes the rule cheap for sparse exact-cover instances.

Reproducibility Check

The browser file is also a CommonJS module. From the repository root:

node - <<'NODE'
const lab = require("./assets/js/exact-cover-lab.js");
const EXPECTED_TOTALS = {
  puzzleRows: 5,
  outcomeRows: 3,
  passed: 6,
  total: 6,
  passedChecks: 965,
  totalChecks: 965
};
const EXPECTED_MATRIX = {
  columns: 64,
  failedChecks: 0,
  passed: true,
  passedChecks: 66,
  rows: 64,
  rowWidth: 4,
  totalChecks: 66
};
const EXPECTED_OUTCOME_ROWS = [
  "contradiction:1 cases:0 solutions:maxMin=0:saved=0:1/1 passed:conflict",
  "multiple:3 cases:292 solutions:maxMin=2157:saved=612:3/3 passed:six, thin, blank",
  "unique:1 cases:1 solutions:maxMin=11:saved=1:1/1 passed:diagonal"
];
const EXPECTED_CASE_ROWS = [
  "six:six clues:2/2 solutions:min=19:first=25:saved=6:multiple:10/10:true:none",
  "diagonal:diagonal clues:1/1 solutions:min=11:first=12:saved=1:unique:7/7:true:none",
  "thin:four corners:2/2 solutions:min=21:first=31:saved=10:multiple:10/10:true:none",
  "blank:blank grid:288/288 solutions:min=2157:first=2753:saved=596:multiple:868/868:true:none",
  "conflict:conflicting clues:0/0 solutions:min=0:first=0:saved=0:contradiction:4/4:true:clue r1c2=1 conflicts with an earlier clue"
];

function sameJson(actual, expected) {
  return JSON.stringify(actual) === JSON.stringify(expected);
}

function rowDrifts(actualRows, expectedRows) {
  const drifts = [];
  const rows = Math.max(actualRows.length, expectedRows.length);
  for (let index = 0; index < rows; index += 1) {
    const actual = index < actualRows.length ? actualRows[index] : null;
    const expected = index < expectedRows.length ? expectedRows[index] : null;
    if (!sameJson(actual, expected)) {
      drifts.push({ index, actual, expected });
    }
  }
  return drifts;
}

const audit = lab.auditExactCover();
console.table([audit.matrix]);
console.table(audit.byOutcome);
const caseRowsForDisplay = audit.cases.map((row) => ({
  puzzle: row.label,
  solutions: row.exactSolutions,
  brute: row.bruteSolutions,
  minNodes: row.minNodes,
  firstNodes: row.firstNodes,
  saved: row.nodeSavings,
  outcome: row.outcome,
  passed: row.passed
}));
console.table(caseRowsForDisplay);
const auditShape = {
  puzzleRows: audit.cases.length,
  outcomeRows: audit.byOutcome.length,
  passed: audit.passed,
  total: audit.total,
  passedChecks: audit.passedChecks,
  totalChecks: audit.totalChecks
};
const matrixShape = {
  columns: audit.matrix.columns,
  failedChecks: audit.matrix.failedChecks.length,
  passed: audit.matrix.passed,
  passedChecks: audit.matrix.passedChecks,
  rows: audit.matrix.rows,
  rowWidth: audit.matrix.rowWidth,
  totalChecks: audit.matrix.totalChecks
};
const outcomeRows = audit.byOutcome.map((row) =>
  `${row.outcome}:${row.cases} cases:${row.exactSolutions} solutions:` +
  `maxMin=${row.maxMinNodes}:saved=${row.nodeSavings}:` +
  `${row.passed}/${row.cases} passed:${row.puzzles}`
);
const caseRows = audit.cases.map((row) =>
  `${row.puzzle}:${row.label}:${row.exactSolutions}/${row.bruteSolutions} solutions:` +
  `min=${row.minNodes}:first=${row.firstNodes}:saved=${row.nodeSavings}:` +
  `${row.outcome}:${row.passedChecks}/${row.totalChecks}:${row.passed}:` +
  `${row.contradiction || "none"}`
);
const outcomeRowDrifts = rowDrifts(outcomeRows, EXPECTED_OUTCOME_ROWS);
const caseRowDrifts = rowDrifts(caseRows, EXPECTED_CASE_ROWS);
const driftShape = {
  auditShape,
  matrixShape,
  outcomeRowDrifts,
  caseRowDrifts
};
const shapeErrors = [
  sameJson(auditShape, EXPECTED_TOTALS) ? null : "totals",
  sameJson(matrixShape, EXPECTED_MATRIX) ? null : "matrixShape",
  outcomeRowDrifts.length === 0 ? null : "outcomeRows",
  caseRowDrifts.length === 0 ? null : "caseRows"
].filter(Boolean);
if (shapeErrors.length) {
  throw new Error(
    `exact-cover audit shape drifted in ${shapeErrors.join(", ")}:\n` +
    JSON.stringify(driftShape, null, 2)
  );
}

const failedOutcomeGroups = audit.byOutcome.filter(
  (row) => row.passed !== row.cases
);
const failedCases = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
if (!audit.ok || !audit.matrix.passed || failedOutcomeGroups.length ||
    failedCases.length || audit.passed !== audit.total ||
    audit.passedChecks !== audit.totalChecks) {
  throw new Error(JSON.stringify({
    failures: audit.failures,
    issues: audit.issues.slice(0, 10),
    matrix: audit.matrix,
    failedOutcomeGroups,
    failedCases,
    auditShape
  }, null, 2));
}
console.log(`${audit.passed}/${audit.total} audit groups and ` +
  `${audit.passedChecks}/${audit.totalChecks} checks passed`);
NODE

The current sweep passed 6/6 audit groups and 965/965 named checks:

  • the exact-cover matrix has 64 assignment rows and 64 constraint columns;
  • every assignment row covers four unique constraints;
  • Algorithm X and an independent Sudoku backtracker return the same solution count on every included instance;
  • the tightest-column heuristic explores no more nodes than the first-column rule on these deterministic cases;
  • each exact-cover solution covers every matrix column once;
  • each decoded grid is a valid 4x4 Sudoku grid; and
  • each decoded grid respects the original clues.

The implementation is small enough to inspect: assets/js/exact-cover-lab.js.

What The Toy Leaves Out

This is not a competitive Sudoku solver. It is a microscope slide.

A production DLX implementation would avoid copying row and column arrays, would count pointer updates, and would expose primary versus secondary columns. Secondary columns are useful for constraints that may be used at most once but do not have to be covered. Knuth uses that distinction in examples such as N queens, where some diagonal constraints are optional.5

The 4x4 Sudoku instances also make the smallest-column heuristic look unreasonably well-behaved. On larger exact-cover problems, it can still face an exponential tree. The heuristic reduces the local branching factor; it does not remove NP-completeness from exact cover.

Still, the representation earns its keep. Once a puzzle becomes rows and columns, “is this move legal?” is no longer a custom predicate scattered through the solver. It is a set intersection:

if a candidate row touches a covered column, it is gone
if an uncovered column has no rows, this branch is impossible
if no columns remain, the selected rows are the certificate

That is the quiet power of exact cover. The puzzle stops being a nest of special cases and becomes an accounting system for conflict.

  1. Donald E. Knuth, “Dancing links”, submitted to arXiv on November 15, 2000; journal reference Millennial Perspectives in Computer Science, 187-214. The paper defines the exact-cover matrix view and Algorithm X. ↩

  2. Knuth, “Dancing links”, Section “Solving an exact cover problem.” The algorithm permits any deterministic column choice, but Knuth discusses choosing columns with few remaining 1s as an important ordering heuristic. ↩

  3. Knuth, “Dancing links”, opening sections. The paper explains reversible deletion and restoration in doubly linked lists, then uses those operations to implement Algorithm X as DLX. ↩

  4. Hirosi Hitotumatu and Kohei Noshita, “A Technique for Implementing Backtrack Algorithms and its Application”, Information Processing Letters 8(4):174-175, 1979. DBLP also lists the record here. ↩

  5. Knuth, “Dancing links”, concluding discussion and N queens examples. The distinction between primary and secondary columns lets DLX express constraints that are optional but still mutually exclusive when used. ↩