Knuth's Algorithm X

Donald Knuth's "Algorithm X", first presented in November of 2000, is a recursive, nondeterministic, depth first brute force algorithm which 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.

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

• Using any deterministic algorithm, choose a column, c.
• Choose any row, r, which has a 1 in column c, and add that row to the solution set.
• Remove any unselected rows which have a 1 in any column which r has a 1 in.
• Remove from the matrix any columns for which row r has a 1.
• 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:

${\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 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 remaining rows (even though they have 0 columns) are the solution subset.

Donald Knuth further suggested an implementation of this algorithm using doubly linked lists, and named this DLX as the Dancing Links implementation of Algorithm X.

External links

• 26-page PDF version of the paper This paper is the authoratative source for Algorithm X and DLX.