Dancing links

By Donald Ervin Knuth. 2000

331 citations recorded by the source corpus.

The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes. The first trick is to implement each assumption of the search with reversible local operations on doubly linked lists. By this trick, every step of the search affects the data incrementally. The second trick is to add a ghost square that represents the identity of each polyomino. Thus puts the rule that each polyomino be used once on the same footing as the rule that each square be covered once. The coding simplifies to a more abstract form which is equivalent to 0-1 integer programming. More significantly for the total computation time, the search can naturally switch between placing a fixed polyomino or covering a fixed square at different stages, according to a combined heuristic. Finally the author reports excellent performance for his algorithm for some familiar puzzles. These include tiling a hexagon by 19 hexiamonds and the N queens problem for N up to 18.

Subfields: Experimental and Cognitive Psychology

View Paper: https://www.semanticscholar.org/paper/4c3c7863b2b895aec46f1e1cb8be2e44e8990b58

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Experimental and Cognitive Psychology

Citations in the corpus

Solving MAXSAT by Solving a Sequence of Simpler SAT Instances (2011, methodology): “We utilized a dancing links representation of the hitting set problem [9], and at each node branched on whether or not a clause was to be included or excluded from the hitting set.”
EXISTENCE OF $q$ -ANALOGS OF STEINER SYSTEMS (2013, methodology): “Given the corresponding Kramer–Mesner matrix M A with 105 rows and 30 705 columns, we reformulate the search for S as an instance of the exact cover problem, which we solve using the dancing links algorithm of Knuth [ 32 ].”
Recurrent Relational Networks (2017, background): “For example, 9-by-9 Sudokus can be solved in a fraction of a second with constraint propagation and search [Norvig, 2006] or with dancing links [Knuth, 2000].”
Minion: A Fast Scalable Constraint Solver (2006, background): “Many techniques can reduce the amount of memory changed on backtracking, e.g. dancing links [17], but we have not found one that repays even low time overheads.”
Subarray Partition in Array Antenna Based on the Algorithm X (2013, methodology): “In [15], Knuth described the algorithm X based on the incidence matrix representation of the exact cover problem.”