Knuth's Algorithm X

Donald Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem represented by a matrix "A" consisting of 0s and 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:

:

Step 3—Rows "A" and "B" each have a 1 in column 1 and thus are selected (nondeterministically).

The algorithm moves to the first branch at level 1…

: Level 1: Select Row "A"

: Step 4—Row "A" is included in the partial solution.

: Step 5—Row "A" has a 1 in columns 1, 4, and 7:

::

: Step 1—The matrix is not empty, so the algorithm proceeds.

: Step 2—The lowest number of 1s in any column is zero and column 2 is the first column with zero 1s:

::

: Rows "D", "E", and "F" remain and columns 2, 3, 5, 6, and 7 remain:

::

:: Column 3 has a 1 in rows "D" and "E"; column 5 has a 1 in row "D"; and column 6 has a 1 in rows "D" and "E". Thus rows "D" and "E" are to be removed and columns 3, 5, and 6 are to be removed:

:::

::: Column 2 has a 1 in row "F"; and column 7 has a 1 in row "F". Thus row "F" is is to removed and columns 2 and 7 are to be removed:

::::

::: Step 1—The matrix is empty, thus this branch of the algorithm terminates successfully.

::: As rows "B", "D", and "F" are selected, the final solution is:

::::

::: In other words, the subcollection {"B", "D", "F"} is an exact cover, since every element is contained in exactly one of the sets "B" = {1, 4}, "D" = {3, 5, 6}, or "F" = {2, 7}.

::: There are no more selected rows at level 3, thus the algorithm moves to the next branch at level 2…

:: There are no more selected rows at level 2, thus the algorithm moves to the next branch at level 1…

: There are no more selected rows at level 1, thus the algorithm moves to the next branch at level 0…

There are no branches at level 0, thus the algorithm terminates.

In summary, the algorithm determines there is only one exact cover: $mathcal\{S\}^*$ = {"B", "D", "F"}.

Implementations

Dancing Links, commonly known as DLX, is the technique suggested by Knuth to efficiently implement his Algorithm X on a computer. Dancing Links implements the matrix using circular doubly-linked lists of the 1s in the matrix. There is a list of 1s for each row and each column. Each 1 in the matrix has a link to the next 1 above, below, to the left, and to the right of itself.

See also

* Exact cover
* Dancing Links

References

*citation
first = Donald E. | last = Knuth | authorlink = Donald Knuth
contribution = Dancing links
title = Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare
year = 2000
pages = 187–214
publisher = Palgrave
isbn = 9780333922309
editor1-first = Jim | editor1-last = Davies
editor2-first = Bill | editor2-last = Roscoe
editor3-first = Jim | editor3-last = Woodcock
id = arxiv | cs/0011047.