HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, dancing links (DLX) is a technique for adding and deleting a node from a circular
doubly linked list In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the se ...
. It is particularly useful for efficiently implementing backtracking algorithms, such as Knuth's Algorithm X for the exact cover problem. Algorithm X is a recursive,
nondeterministic Nondeterminism or nondeterministic may refer to: Computer science * Nondeterministic programming *Nondeterministic algorithm In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit diffe ...
, depth-first, backtracking
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
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 Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorics, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each co ...
. The name ''dancing links'', which was suggested by
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer ...
, 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, but it is his paper which has popularized it.


Implementation

As the remainder of this article discusses the details of an implementation technique for Algorithm X, the reader is strongly encouraged to read the Algorithm X article first.


Main ideas

The idea of DLX is based on the observation that in a circular
doubly linked list In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the se ...
of nodes, x.left.right ← x.right; x.right.left ← x.left; will remove node ''x'' from the list, while x.left.right ← x; x.right.left ← x; will restore ''xs position in the list, assuming that x.right and x.left have been left unmodified. This works regardless of the number of elements in the list, even if that number is 1. Knuth observed that a naive implementation of his Algorithm X would spend an inordinate amount of time searching for 1's. When selecting a column, the entire matrix had to be searched for 1's. When selecting a row, an entire column had to be searched for 1's. After selecting a row, that row and a number of columns had to be searched for 1's. To improve this search time from
complexity Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generally used to c ...
O(n) to O(1), Knuth implemented a sparse matrix where only 1's are stored. At all times, each node in the matrix will point to the adjacent nodes to the left and right (1's in the same row), above and below (1's in the same column), and the header for its column (described below). Each row and column in the matrix will consist of a circular doubly-linked list of nodes.


Header

Each column will have a special node known as the "column header," which will be included in the column list, and will form a special row ("control row") consisting of all the columns which still exist in the matrix. Finally, each column header may optionally track the number of nodes in its column, so that locating a column with the lowest number of nodes is of
complexity Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generally used to c ...
O(''n'') rather than O(''n''×''m'') where ''n'' is the number of columns and ''m'' is the number of rows. Selecting a column with a low node count is a heuristic which improves performance in some cases, but is not essential to the algorithm.


Exploring

In Algorithm X, rows and columns are regularly eliminated from and restored to the matrix. Eliminations are determined by selecting a column and a row in that column. If a selected column doesn't have any rows, the current matrix is unsolvable and must be backtracked. When an elimination occurs, all columns for which the selected row contains a 1 are removed, along with all rows (including the selected row) that contain a 1 in any of the removed columns. The columns are removed because they have been filled, and the rows are removed because they conflict with the selected row. To remove a single column, first remove the selected column's header. Next, for each row where the selected column contains a 1, traverse the row and remove it from other columns (this makes those rows inaccessible and is how conflicts are prevented). Repeat this column removal for each column where the selected row contains a 1. This order ensures that any removed node is removed exactly once and in a predictable order, so it can be backtracked appropriately. If the resulting matrix has no columns, then they have all been filled and the selected rows form the solution.


Backtracking

To backtrack, the above process must be reversed using the second algorithm stated above. One requirement of using that algorithm is that backtracking must be done as an exact reversal of eliminations. Knuth's paper gives a clear picture of these relationships and how the node removal and reinsertion works, and provides a slight relaxation of this limitation.


Optional constraints

It is also possible to solve one-cover problems in which a particular constraint is optional, but can be satisfied no more than once. Dancing Links accommodates these with primary columns which must be filled and secondary columns which are optional. This alters the algorithm's solution test from a matrix having no columns to a matrix having no primary columns and if the heuristic of minimum one's in a column is being used then it needs to be checked only within primary columns. Knuth discusses optional constraints as applied to the ''n'' queens problem. The chessboard diagonals represent optional constraints, as some diagonals may not be occupied. If a diagonal is occupied, it can be occupied only once.


See also

*
Sudoku solving algorithms A standard Sudoku contains 81 cells, in a 9×9 grid, and has 9 boxes, each box being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns. Each cell may contain a number from one to nine, and each number ...


References


External links

*
distributed Dancing Links
implementation as a Hadoop MapReduce example
Free Software implementation of an Exact Cover solver in C
- uses Algorithm X and Dancing Links. Includes examples for sudoku and logic grid puzzles.
DlxLib NuGet package
- a C# class library that implements DLX
dlxlib npm package
- a JavaScript library that implements DLX
dancing-links-c++
- a C++ library that implements DLX
go-dancing-links
- a GoLang library that implements DLX
Donald Knuth's original implementation of dancing links
written in CWEB. (See also hi
frontend for solving sudoku puzzles
)
Donald Knuth's 24th Annual Christmas Lecture: Dancing Links
{{Donald Knuth navbox Search algorithms Linked lists Donald Knuth Sudoku Articles containing video clips