Knuth's Algorithm X

Donald Knuth's Algorithm X, first presented in November of 2000, is a recursive, nondeterministic, depth-first, brute-force algorithm that finds all solutions to the exact cover problem represented by a matrix A consisting of 0s amd 1s. The goal is to select a subset of the rows so that the digit 1 appears in each column exactly once.

Algorithm X functions as follows:

If the matrix A is empty, the problem is solved; terminate successfully.
Otherwise choose a column c (deterministically).
Choose a row r such that A_{r, c} = 1 (nondeterministically).
Include row r in the partial solution.
For each column j such that A_{r, j} = 1,
delete column j from matrix A;

for each row i such that A_{i, j} = 1,
delete row i from matrix A.
Repeat this algorithm recursively on the reduced matrix A.

The nondeterministic choice of r means that the algorithm essentially clones itself into independent subalgorithms; each subalgorithm inherits the current matrix A, but reduces it with respect to a different row r. If column c is entirely zero, there are no subalgorithms and the process terminates unsuccessfully.

The subalgorithms form a search tree in a natural way, with the original problem at the root and with level k containing each subalgorithm that corresponds to k chosen rows. Backtracking is the process of traversing the tree in preorder, depth first.

Any systematic rule for choosing column c in this procedure will find all solutions, but some rules work much better than others. To reduce the number of iterations, Knuth suggests that the column choosing algorithm select a column with the lowest number of 1s in it.

Example

For example, consider the exact cover problem represented by the matrix:

{\begin{bmatrix}1&0&0&1&0&0&1\\1&0&0&1&0&0&0\\0&0&0&1&1&0&1\\0&0&1&0&1&1&0\\0&1&1&0&0&1&1\\0&1&0&0&0&0&1\end{bmatrix}}

This problem is solved as follows, using 0 based notation: The lowest number of 1s in any column is 2, and column 0 is the first column with two 1s, so column 0 is selected. Row 0 is selected as the first row with a 1 on column 0. Row 1 has a 1 in column 0, so is removed. Row 2 has a 1 in column 3, so is removed. Row 4 has a 1 in column 6, so is removed. Row 5 has a 1 in column 6, so is removed. Column 0 is removed. Column 3 is removed. Column 6 is removed.

Iterative result:

{\begin{bmatrix}0&0&0&0\\0&1&1&1\end{bmatrix}}

Column 0 has no 1s, so this potential solution is rejected, and we backtrack. The previously selected row, 0, can now safely be removed from consideration of this submatrix. Result:

{\begin{bmatrix}1&0&0&1&0&0&0\\0&0&0&1&1&0&1\\0&0&1&0&1&1&0\\0&1&1&0&0&1&1\\0&1&0&0&0&0&1\end{bmatrix}}

The lowest number of 1s in any column is 1, and column 0 is the first column with one 1, so column 0 is selected. Row 0 is selected as the first row with a 1 on column 0. Row 1 has a 1 in column 3, so it is removed. Column 0 is removed. Column 3 is removed.

Iterative result:

{\begin{bmatrix}0&0&0&0&0\\0&1&1&1&0\\1&1&0&1&1\\1&0&0&0&1\end{bmatrix}}

Each column has one or more 1s, so we continue. The lowest number of 1s in any column is 1, and column 2 is the first column with one 1, so column 2 is selected. Row 1 is selected as the first row with a 1 on column 2. Row 2 has a 1 in column 1, so is removed. Column 1 is removed. Column 2 is removed. Column 3 is removed.

Iterative result:

{\begin{bmatrix}0&0\\0&0\\1&1\end{bmatrix}}

Each column has one or more 1s, so we continue. The lowest number of 1s in any column is 1, and column 0 is the first column with one 1, so column 0 is selected. Row 2 is selected as the first row with a 1 on column 0. Column 0 is removed. Column 1 is removed.

The result is an empty matrix, so this is a solution. The elements represented by the selected rows are the solution set:

{\begin{bmatrix}1&0&0&1&0&0&0\\0&0&1&0&1&1&0\\0&1&0&0&0&0&1\end{bmatrix}}

Donald Knuth further suggested an implementation of this algorithm using circular doubly linked lists, and named this Dancing Links, or DLX.

References

Knuth's paper (look for P159)
PDF version of Knuth's paper