In computer science, dancing links is the technique suggested by Donald Knuth to efficiently implement his Algorithm X.[1] Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku.
The name dancing links stems from the way the algorithm works, as iterations of the algorithm cause the links to “dance” with partner links so as to resemble an “exquisitely choreographed dance.” Knuth credits Hiroshi Hitotsumatsu and Kōhei Noshita with having invented the idea in 1979,[2] but it is his paper which has popularized it.
“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 coverproblem.[1] Technically, Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm. While Algorithm X is generally useful as a succinct explanation of how theexact 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.[1]
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.
Algorithm X functions as follows:
-
- If the matrix A has no columns, the current partial solution is a valid solution; terminate successfully.
- Otherwise choose a column c (deterministically).
- Choose a row r such that Ar, c = 1 (nondeterministically).
- Include row r in the partial solution.
- For each column j such that Ar, j = 1,
- for each row i such that Ai, j = 1,
- delete row i from matrix A.
- delete column j from matrix A.
- for each row i such that Ai, j = 1,
- Repeat this algorithm recursively on the reduced matrix A.
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, Knuthsuggests that the column choosing algorithm select a column with the lowest number of 1s in it.