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: 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. 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 = {A, B, C, D, E, F}, where: A = {1, 4, 7}; B = {1, 4}; C = {4, 5, 7}; D = {3, 5, 6}; E = {2, 3, 6, 7}; and F = {2, 7}. This problem is represented by the matrix: {| class="wikitable" ! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 |- ! A | 1 || 0 || 0 || 1 || 0 || 0 || 1 |- ! B | 1 || 0 || 0 || 1 || 0 || 0 || 0 |- ! C | 0 || 0 || 0 || 1 || 1 || 0 || 1 |- ! D | 0 || 0 || 1 || 0 || 1 || 1 || 0 |- ! E | 0 || 1 || 1 || 0 || 0 || 1 || 1 |- ! F | 0 || 1 || 0 || 0 || 0 ||