Knuth's Algorithm X: Difference between revisions

Revision as of 07:23, 20 November 2015

Revision as of 15:00, 10 September 2016

Line 1:

'''"Algorithm X"''' is the name [[Donald Knuth]] used in his paper "Dancing Links" to refer to "the most obvious trial-and-error approach" for finding all solutions to the [[exact cover]] problem.<ref name="knuth" /> Technically, Algorithm X is a [[Recursion (computer science)|recursive]], [[Nondeterministic algorithm|nondeterministic]], [[depth-first]], [[backtracking]] [[algorithm]]. While Algorithm X is generally useful as a succinct explanation of how the [[exact cover]] problem may be solved, Knuth's intent in presenting it was merely to demonstrate the utility of the [[dancing links]] technique via an efficient implementation he called DLX.<ref name="knuth">{{cite arxivarXiv | author = [[Donald Knuth|Knuth, Donald]] | title = Dancing links | year = 2000 | eprint = cs/0011047 }}</ref>

The [[exact cover]] problem is represented in Algorithm X using 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.

Line 383:

==External links==

*[https://github.com/blynn/dlx Free Software implementation of Algorithm X in C] - uses the Dancing Links optimization. Includes examples for using the library to solve sudoku and logic grid puzzles.

*[httphttps://github.com/mlepage/polycube-solver Polycube solver] Program (with Lua source code) to fill boxes with polycubes using [[Algorithm X]].

*[http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz Knuth's Paper describing the Dancing Links optimization] - Gzip'd postscript file.