Knuth's Algorithm X

Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the dancing links technique.

The exact cover problem is represented in Algorithm X by a matrix A consisting of 0s and 1s. The goal is to select a subset of the rows such that the digit 1 appears in each column exactly once.

Algorithm X works as follows:

# If the matrix A has no columns, the current partial solution is a valid solution; terminate successfully.

1. Otherwise choose a column c (deterministically).
2. Choose a row r such that A_{r, c} = 1 (nondeterministically).
3. Include row r in the partial solution.
4. For each column j such that A_{r, j} = 1,

   for each row i such that A_{i, j} = 1,

   delete row i from matrix A.

   delete column j from matrix A.

5. Repeat this algorithm recursively on the reduced matrix A.

The nondeterministic choice of r means that the algorithm recurses over 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 smallest number of 1s in it.