20.07Intermediate4 topics18 min2 interactive animations

Exact cover introduction

Exact cover: formulating problems as choosing rows of a 0/1 matrix, Knuth's Algorithm X, the Dancing Links implementation and Sudoku as an exact cover problem.

Learning goals

State the exact cover problem and convert a puzzle into a matrix
Trace Algorithm X, including the fewest-candidates column choice
Explain how doubly linked lists make cover and uncover O(1) per cell
Count the rows and columns of the Sudoku exact cover matrix

Prerequisites

Backtracking methodSearch improvementsLinked lists

20.07.1

Exact cover formulation

Given a set of columns (the *universe*) and a collection of rows (each a subset of the columns), an **exact cover** is a set of rows in which every column appears in **exactly one** chosen row. It is the problem behind tilings, Sudoku, N-Queens variants and scheduling puzzles, and it is NP-complete in general.

To model a puzzle, make one column per *constraint* that must be satisfied exactly once, and one row per *possible move* listing the constraints it satisfies. Choosing a set of moves that satisfies every constraint exactly once solves the puzzle. In Knuth's small example the universe is {1,…,7} and the rows are A = {1,4,7}, B = {1,4}, C = {4,5,7}, D = {3,5,6}, E = {2,3,6,7}, F = {2,7}; the only exact cover is {B, D, F}.

Row	Columns covered
A	1, 4, 7
B	1, 4
C	4, 5, 7
D	3, 5, 6
E	2, 3, 6, 7
F	2, 7

Exact cover with Knuth's Algorithm X

Interactive · edit the input

grid · 7 × 8

01234567

Column with the fewest candidatesRow being triedChosen rowRemoved from the matrix

Setup

Choose some of the 6 subsets (rows) so that every column 1-7 is covered exactly once. Algorithm X always branches on the column with the fewest candidate rows.

Step 1 / 15

Java

1static void solve(Map<Integer, Set<String>> cols, Map<String, List<Integer>> rows, Deque<String> chosen, List<List<String>> out) {
2    if (cols.isEmpty()) { out.add(new ArrayList<>(chosen)); return; }                  // every column is covered exactly once
3    int c = Collections.min(cols.keySet(), Comparator.comparingInt(k -> cols.get(k).size()));   // the column with the fewest rows
4    for (String r : new ArrayList<>(cols.get(c))) {                                   // try each row that covers it
5        chosen.push(r);                                                               // choose row r
6        List<Set<String>> removed = select(cols, rows, r);                            // cover its columns, delete conflicting rows
7        solve(cols, rows, chosen, out);                                               // explore
8        deselect(cols, rows, r, removed);                                             // restore the matrix
9        chosen.pop();                                                                 // unchoose
10    }
11}

Live state

0 rows tried0 dead ends

chosen

[]

columns left

solutions

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L1	chosen=[] columns left=7 solutions=0	Choose some of the 6 subsets (rows) so that every column 1-7 is covered exactly once. Algorithm X always branches on the column with the fewest candidate rows.
2	L3	chosen=[] columns left=7 solutions=0	Column 1 has the fewest candidate rows (2: [A, B]). One of them must be chosen.
3	L6	chosen=[A] columns left=4 solutions=0	Choose row A: its columns [1, 4, 7] are now covered, so every row that shares one of them ([B, C, E, F]) is deleted.
4	L3	chosen=[A] columns left=4 solutions=0	Column 2 has the fewest candidate rows (0: none). Nothing covers it: dead end.
5	L8	chosen=[] columns left=7 solutions=0	Unchoose row A: restore its columns and the deleted rows.
6	L6	chosen=[B] columns left=5 solutions=0	Choose row B: its columns [1, 4] are now covered, so every row that shares one of them ([A, C]) is deleted.
7	L3	chosen=[B] columns left=5 solutions=0	Column 5 has the fewest candidate rows (1: [D]). One of them must be chosen.
8	L6	chosen=[B, D] columns left=2 solutions=0	Choose row D: its columns [3, 5, 6] are now covered, so every row that shares one of them ([E]) is deleted.
9	L3	chosen=[B, D] columns left=2 solutions=0	Column 2 has the fewest candidate rows (1: [F]). One of them must be chosen.
10	L6	chosen=[B, D, F] columns left=0 solutions=0	Choose row F: its columns [2, 7] are now covered, so every row that shares one of them (none) is deleted.
11	L2	chosen=[B, D, F] columns left=0 solutions=1	No column is left: the chosen rows [B, D, F] cover every column exactly once. Solution 1.
12	L8	chosen=[B, D] columns left=2 solutions=1	Unchoose row F: restore its columns and the deleted rows.
13	L8	chosen=[B] columns left=5 solutions=1	Unchoose row D: restore its columns and the deleted rows.
14	L8	chosen=[] columns left=7 solutions=1	Unchoose row B: restore its columns and the deleted rows.
15	L11	solutions=1 return=[[B, D, F]]	1 exact cover: [B, D, F].

20.07.2

Algorithm X

**Algorithm X** is plain backtracking on the matrix. If no column is left, the chosen rows are a solution. Otherwise pick the column with the **fewest rows** (a column with no rows is an immediate dead end), try each row that covers it, and for a chosen row delete every column it covers together with every other row that shares one of those columns, since those rows would cover a column twice. Recurse, then restore the matrix.

Step through the first preset: column 2 or 3 has the fewest candidates, rows are tried in turn, and each choice shrinks the matrix. “No exact cover” shows a matrix where every branch ends in a dead end, and “Several solutions” lists all of them. The cost depends entirely on how fast deleting and restoring is, which is what Dancing Links optimises.

Java

1static void algorithmX(Map<Integer, Set<String>> cols, Map<String, List<Integer>> rows, Deque<String> chosen, List<List<String>> out) {
2    if (cols.isEmpty()) { out.add(new ArrayList<>(chosen)); return; }                  // every column is covered exactly once
3    int c = Collections.min(cols.keySet(), Comparator.comparingInt((Integer k) -> cols.get(k).size()));   // the column with the fewest rows
4    for (String r : new ArrayList<>(cols.get(c))) {                                   // try each row that covers it
5        chosen.push(r);                                                               // choose row r
6        List<Set<String>> removed = select(cols, rows, r);                            // cover its columns, delete conflicting rows
7        algorithmX(cols, rows, chosen, out);                                          // explore
8        deselect(cols, rows, r, removed);                                             // restore the matrix
9        chosen.pop();                                                                 // unchoose
10    }
11}
12private static List<Set<String>> select(Map<Integer, Set<String>> cols, Map<String, List<Integer>> rows, String r) {
13    List<Set<String>> removed = new ArrayList<>();
14    for (int j : rows.get(r))
15        for (String i : cols.get(j))
16            for (int k : rows.get(i)) if (k != j) cols.get(k).remove(i);              // row i conflicts: drop it from the other columns
17    for (int j : rows.get(r)) removed.add(cols.remove(j));                            // remove the covered columns
18    return removed;
19}
20private static void deselect(Map<Integer, Set<String>> cols, Map<String, List<Integer>> rows, String r, List<Set<String>> removed) {
21    List<Integer> rc = rows.get(r);
22    for (int idx = rc.size() - 1; idx >= 0; idx--) {
23        int j = rc.get(idx);
24        cols.put(j, removed.remove(removed.size() - 1));                              // put the column back
25        for (String i : cols.get(j))
26            for (int k : rows.get(i)) if (k != j) cols.get(k).add(i);                 // restore the dropped rows
27    }
28}

Exact cover with Knuth's Algorithm X

Interactive · edit the input

grid · 7 × 8

01234567

Column with the fewest candidatesRow being triedChosen rowRemoved from the matrix

Setup

Choose some of the 6 subsets (rows) so that every column 1-7 is covered exactly once. Algorithm X always branches on the column with the fewest candidate rows.

Step 1 / 15

Java

1static void solve(Map<Integer, Set<String>> cols, Map<String, List<Integer>> rows, Deque<String> chosen, List<List<String>> out) {
2    if (cols.isEmpty()) { out.add(new ArrayList<>(chosen)); return; }                  // every column is covered exactly once
3    int c = Collections.min(cols.keySet(), Comparator.comparingInt(k -> cols.get(k).size()));   // the column with the fewest rows
4    for (String r : new ArrayList<>(cols.get(c))) {                                   // try each row that covers it
5        chosen.push(r);                                                               // choose row r
6        List<Set<String>> removed = select(cols, rows, r);                            // cover its columns, delete conflicting rows
7        solve(cols, rows, chosen, out);                                               // explore
8        deselect(cols, rows, r, removed);                                             // restore the matrix
9        chosen.pop();                                                                 // unchoose
10    }
11}

Live state

0 rows tried0 dead ends

chosen

[]

columns left

solutions

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L1	chosen=[] columns left=7 solutions=0	Choose some of the 6 subsets (rows) so that every column 1-7 is covered exactly once. Algorithm X always branches on the column with the fewest candidate rows.
2	L3	chosen=[] columns left=7 solutions=0	Column 1 has the fewest candidate rows (2: [A, B]). One of them must be chosen.
3	L6	chosen=[A] columns left=4 solutions=0	Choose row A: its columns [1, 4, 7] are now covered, so every row that shares one of them ([B, C, E, F]) is deleted.
4	L3	chosen=[A] columns left=4 solutions=0	Column 2 has the fewest candidate rows (0: none). Nothing covers it: dead end.
5	L8	chosen=[] columns left=7 solutions=0	Unchoose row A: restore its columns and the deleted rows.
6	L6	chosen=[B] columns left=5 solutions=0	Choose row B: its columns [1, 4] are now covered, so every row that shares one of them ([A, C]) is deleted.
7	L3	chosen=[B] columns left=5 solutions=0	Column 5 has the fewest candidate rows (1: [D]). One of them must be chosen.
8	L6	chosen=[B, D] columns left=2 solutions=0	Choose row D: its columns [3, 5, 6] are now covered, so every row that shares one of them ([E]) is deleted.
9	L3	chosen=[B, D] columns left=2 solutions=0	Column 2 has the fewest candidate rows (1: [F]). One of them must be chosen.
10	L6	chosen=[B, D, F] columns left=0 solutions=0	Choose row F: its columns [2, 7] are now covered, so every row that shares one of them (none) is deleted.
11	L2	chosen=[B, D, F] columns left=0 solutions=1	No column is left: the chosen rows [B, D, F] cover every column exactly once. Solution 1.
12	L8	chosen=[B, D] columns left=2 solutions=1	Unchoose row F: restore its columns and the deleted rows.
13	L8	chosen=[B] columns left=5 solutions=1	Unchoose row D: restore its columns and the deleted rows.
14	L8	chosen=[] columns left=7 solutions=1	Unchoose row B: restore its columns and the deleted rows.
15	L11	solutions=1 return=[[B, D, F]]	1 exact cover: [B, D, F].

20.07.3

Dancing Links overview

Algorithm X deletes and restores rows and columns constantly. **Dancing Links (DLX)** stores the 0/1 matrix as a grid of nodes in which every node sits in two circular doubly linked lists, one across its row and one down its column, plus a header row of columns. Removing a node from a doubly linked list is x.left.right = x.right; x.right.left = x.left, and — the trick — the removed node still remembers its neighbours, so it can be re-inserted by the exact reverse: x.left.right = x; x.right.left = x. Undo is therefore O(1) per node with no copying.

cover(c) unlinks column header c and, for every row in column c, unlinks the other cells of that row from their columns. uncover(c) relinks them in the reverse order. The search loop is then a few lines. The class below solves exact cover and returns every solution as a list of row indices; it was checked against brute force on random matrices.

Java

1final class Dlx {
2    private static class Node { Node l, r, u, d; Column c; int row; }
3    private static final class Column extends Node { int size; Column() { c = this; } }
4
5    private final Column head = new Column();
6    private final List<Integer> chosen = new ArrayList<>();
7    final List<List<Integer>> solutions = new ArrayList<>();
8
9    Dlx(int nCols, int[][] rows) {                              // rows[i] = the columns (0-based) that row i covers
10        head.l = head.r = head;
11        Column[] cols = new Column[nCols];
12        for (int j = 0; j < nCols; j++) {
13            Column col = new Column(); cols[j] = col;
14            col.u = col.d = col;
15            col.l = head.l; col.r = head; head.l.r = col; head.l = col;     // append the header to the header row
16        }
17        for (int i = 0; i < rows.length; i++) {
18            Node first = null;
19            for (int j : rows[i]) {
20                Node n = new Node(); n.row = i; n.c = cols[j];
21                n.u = cols[j].u; n.d = cols[j]; cols[j].u.d = n; cols[j].u = n; cols[j].size++;   // bottom of column j
22                if (first == null) { first = n; n.l = n.r = n; }
23                else { n.l = first.l; n.r = first; first.l.r = n; first.l = n; }                  // end of the row's circle
24            }
25        }
26    }
27
28    void solve() { search(); }
29
30    private void search() {
31        if (head.r == head) { solutions.add(new ArrayList<>(chosen)); return; }      // no column left: exact cover
32        Column c = (Column) head.r;
33        for (Node k = c.r; k != head; k = k.r) if (((Column) k).size < c.size) c = (Column) k;   // fewest rows
34        cover(c);
35        for (Node r = c.d; r != c; r = r.d) {
36            chosen.add(r.row);                                  // choose row r
37            for (Node j = r.r; j != r; j = j.r) cover(j.c);     // cover the other columns of r
38            search();
39            for (Node j = r.l; j != r; j = j.l) uncover(j.c);   // undo in the opposite order
40            chosen.remove(chosen.size() - 1);
41        }
42        uncover(c);
43    }
44
45    private static void cover(Column c) {
46        c.r.l = c.l; c.l.r = c.r;                               // unlink the column header
47        for (Node i = c.d; i != c; i = i.d)
48            for (Node j = i.r; j != i; j = j.r) { j.d.u = j.u; j.u.d = j.d; j.c.size--; }   // unlink the rows that use this column
49    }
50    private static void uncover(Column c) {
51        for (Node i = c.u; i != c; i = i.u)
52            for (Node j = i.l; j != i; j = j.l) { j.c.size++; j.d.u = j; j.u.d = j; }       // relink in reverse order
53        c.r.l = c; c.l.r = c;
54    }
55}

20.07.4

Sudoku exact cover

Sudoku as exact cover has **324 columns**, the four kinds of constraint, 81 each: every cell holds exactly one digit, every row contains each digit once, every column contains each digit once, every 3×3 box contains each digit once. It has **729 rows**: one for every (row, column, digit) placement, 9 × 9 × 9. Each row covers exactly four columns, one of each kind. A given digit is a row that must be chosen up front.

Choosing 81 rows that cover all 324 columns exactly once is exactly a filled, valid grid. Algorithm X picks the column with the fewest rows, which is the most constrained cell or digit placement, so it automatically does what the constraint-propagation lesson described by hand. Ordinary Sudoku puzzles are solved almost instantly this way.

Constraint family	Columns	Meaning
Cell (r, c) has a digit	81	index r·9 + c
Row r has digit d	81	index 81 + r·9 + (d−1)
Column c has digit d	81	index 162 + c·9 + (d−1)
Box b has digit d	81	index 243 + b·9 + (d−1)
Total	324	each of the 729 placements covers 4 of them

Java

1static int[] sudokuColumns(int r, int c, int d) {                // d is 1..9; returns the four columns this placement covers
2    int box = r / 3 * 3 + c / 3;
3    return new int[]{
4        r * 9 + c,                  // cell (r, c) is filled
5        81 + r * 9 + (d - 1),       // row r contains d
6        162 + c * 9 + (d - 1),      // column c contains d
7        243 + box * 9 + (d - 1)     // box contains d
8    };
9}

Practice ladder

Now try it yourself

Easy

Write the exact cover matrix for tiling a 2x2 board with dominoes
Why must a column with no rows end the branch?

Medium

Sudoku Solver (as exact cover)
Tiling a 2xN board with dominoes: count solutions

Advanced

Pentomino tiling
Implement Dancing Links and test it on N-Queens as an exact cover

Key takeaways

Exact cover: choose rows so that every column is covered exactly once.
Algorithm X branches on the column with the fewest candidate rows.
Dancing Links makes cover and uncover O(1) per cell by relinking doubly linked lists; Sudoku is a 729 × 324 matrix.