Knuth's Algorithm X: Difference between revisions

Revision as of 12:58, 10 July 2006

Revision as of 13:07, 10 July 2006

Line 1:

[[Donald Knuth|Donald Knuth's]] '''Algorithm X''', first presented in November of 2000, is a [[recursive function|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.

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

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.

:<math>

\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}

</math>

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

Algorithm X functions as follows:

Line 40 ⟶ 26:

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

== Example ==

The example above is solved as follows, using 0 based notation:

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

:<math>

\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}

</math>

TheThis example aboveproblem 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.

Line 121:

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

==External linksReferences ==

* [http://www-cs-faculty.stanford.edu/~knuth/preprints.html Knuth's paper] (look for P159)

* [http://xxx.lanl.gov/PS_cache/cs/pdf/0011/0011047.pdf PDF version of Knuth's paper]