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.

For example, the following matrix represents an exact cover problem in which the goal is to choose a subset of the rows so that the digit 1 appears in each column exactly once.

${\displaystyle {\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}}}$

The goal is to iteratively partition each row from their initial subset (unselected) into the selected or rejected subsets.

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 Ar, c = 1 (nondeterministically). Include row r in the partial solution. For each column j such that Ar, j = 1, delete column j from matrix A; for each row i such that Ai, j = 1, delete row i from matrix A. Repeat this algorithm recursively on the reduced matrix A.

To reduce the number of iterations, Knuth suggests that the column choosing algorithm select a column with the lowest number of 1s in it.

The example above 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:

${\displaystyle {\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:

${\displaystyle {\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:

${\displaystyle {\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:

${\displaystyle {\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:

${\displaystyle {\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.

External links

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