Knuth's Algorithm X: Difference between revisions

Revision as of 19:43, 5 January 2006

Revision as of 19:46, 5 January 2006

Line 21:

Algorithm X functions as follows:

* Using any [[deterministic algorithm]], choose a column, c.

* ChooseNondeterministically 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.

Line 106:

Column 1 is removed.

The result is an empty matrix, so this is a solution. The remainingelements rowsrepresented (evenby thoughthe theyselected have 0 columns)rows are the solution subsetset.

[[Donald Knuth]] further suggested an implementation of this algorithm using circular [[Doubly linked list|doubly linked lists]], and named this DLX as the [[Dancing Links]], implementationor of Algorithm XDLX.

==External links==

* [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 26-page PDF version of theKnuth's paper] This paper is the authoratative source for Algorithm X and DLX.