File DancingLinks.h
↰ Parent directory (ADS/backtrack)
The exact cover by dancing links of Knuth (Algorithm 7.2.2.1X), beyond the book [see File Enumeration.h for the backtrack of chapter 16]: given the items and the options, each a set of items, find the sets of options that contain every primary item exactly once and every secondary item at most once.
Definition (ADS/backtrack/DancingLinks.h)
Detailed Description
The items and the options are on circular doubly linked lists, a node per item of an option; covering an item takes it off the list of the items and the options that contain it off the lists of their other items, and since a removed node keeps its own links, the uncovering puts it back by the two assignments :math:` L[ R[ x ] ] = x , R[ L[ x ] ] = x `, in the reverse order. The search branches on the item with the fewest options left (the MRV heuristic), which detects the dead ends early.
Many puzzles are exact covers: the n queens (the rows and columns primary, the diagonals secondary), the Sudoku (a cell, a row, a column and a box with each digit, 324 primary items), the pentominoes. The tests count the queens and solve the Sudoku of the backtrack chapter.
The contracts [see File Contract.h]: the items of an option are distinct and in [ 0 , n ), and one of them is primary (an option of secondary items alone would never be chosen); every solution visited is an exact cover, an audit; the links after the search are as before it, an audit. The operations are defined in DancingLinks.tpp.
Knuth, The Art of Computer Programming, vol. 4B, Addison-Wesley, 2022, section 7.2.2.1
Knuth, Dancing links, in Millennial Perspectives in Computer Science, Palgrave, 187-214, 2000, arXiv:cs/0011047
- Donato Meoli
Dipartimento di Informatica Universita’ di Pisa
by Donato Meoli
Includes
ADS/Contract.h(File Contract.h)ADS/backtrack/impl/DancingLinks.tppalgorithm(File AkraBazzi.h)cstddefutilityvector