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:

1. Using any deterministic algorithm, choose a column, c.
2. Nondeterministically choose any row, r, which has a 1 in column c, and add that row to the solution set.
3. Remove any unselected rows which have a 1 in any column which r has a 1 in.
4. Remove from the matrix any columns for which row r has a 1.
5. Repeat the algorithm on this reduced matrix.

When the matrix is empty, you have a solution. 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 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