"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. Technically, Algorithm X is a recursive, 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. The exact cover problem is represented in Algorithm X using a matrix Aconsisting 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. Algorithm X functions as follows: The nondeterministic choice of r means that the algorithm essentially clones itself into independent subalgorithms; each subalgorithm inherits the current matrix A, but reduces it with respect to a different row r. If column c is entirely zero, there are no subalgorithms and the process terminates unsuccessfully. The subalgorithms form a search tree in a natural way, with the original problem at the root and with level k containing each subalgorithm that corresponds to k chosen rows. Backtracking is the process of traversing the tree in preorder, depth first. Any systematic rule for choosing column c in this procedure will find all solutions, but some rules work much better than others. To reduce the number of iterations, 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 universeU = and the collection of sets =, where: This problem is represented by the matrix: Algorithm X with Knuth's suggested heuristic for selecting columns solves this problem as follows: Level 0 Step 1—The matrix is not empty, so the algorithm proceeds. Step 2—The lowest number of 1s in any column is two. Column 1 is the first column with two 1s and thus is selected : Step 3—Rows A and B each have a 1 in column 1 and thus are selected. The algorithm moves to the first branch at level 1… There are no branches at level 0, thus the algorithm terminates. In summary, the algorithm determines there is only one exact cover: =.
Implementations
'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 lists 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.. 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 mistaken guesses.
