Knuth's Algorithm X: Difference between revisions

Revision as of 22:36, 8 November 2010

Revision as of 18:38, 17 April 2011

Line 358:

== Implementations ==

[[Dancing Links]], commonly known as DLX, is the technique suggested by [[Donald Knuth|Knuth]] to efficiently implement his Algorithm X on a computer. Dancing Links implements the matrix using circular [[doubly linked list|doubly-linked list]]s 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 ==