Content deleted Content added
→External links: Replaced dead link to example code with a different (better) library. |
m Fixed citation |
||
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 arxiv | 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.
| |||