Knuth's Algorithm X: Difference between revisions

Revision as of 06:05, 28 March 2015

Revision as of 07:16, 10 September 2015

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.

Line 27:

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 ==

For example, consider the exact cover problem specified by the universe ''U'' = {1, 2, 3, 4, 5, 6, 7} and the collection of sets <math>\mathcal{S}</math> = {''A'', ''B'', ''C'', ''D'', ''E'', ''F''}, where:

:* ''A'' = {1, 4, 7};

Line 359:

In summary, the algorithm determines there is only one exact cover: <math>\mathcal{S}^*</math> = {''B'', ''D'', ''F''}.

== Implementations ==

[[Donald Knuth]]'s main purpose in describing Algorithm X was to demonstrate the utility of [[Dancing Links]]. Knuth showed that Algorithm X can be implemented efficiently on a computer using [[Dancing Links]] in a process Knuth calls ''"DLX"''. DLX uses the matrix representation of the [[exact cover]] problem, implemented as [[doubly linked list]]s of the 1s of the matrix: each 1 element has a link to the next 1 above, below, to the left, and to the right of itself. (Technically, because the lists are circular, this forms a torus). Because exact cover problems tend to be sparse, this representation is usually much more efficient in both size and processing time required. DLX then uses [[Dancing Links]] to quickly select permutations of rows as possible solutions and to efficiently backtrack (undo) mistaken guesses.<ref name="knuth" />

== See also ==

* [[Exact cover]]

* [[Dancing Links]]

==References==

{{reflistReflist}}

*{{citation

| first = Donald E. | last = Knuth | authorlink = Donald Knuth

Line 382:

==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.

* [http://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.

{{Donald Knuth navbox}}