File FastExactCover.h

↰ Parent directory (ADS/backtrack)

The engineered exact cover with colors, beyond the book [see File DancingLinks.h for Algorithm 7.2.2.1X written as the text describes it]: the exact covering with colors (XCC, Algorithm 7.2.2.1C of Knuth) on sparse sets instead of linked lists, the “dancing cells” of Knuth’s program SSXCC after the design of Solnon.

Definition (ADS/backtrack/FastExactCover.h)

Detailed Description

The problem: items, primary or secondary, and options, each a set of items where a secondary item may carry a color; a solution is a set of options that contains each primary item exactly once and gives each secondary item at most one color (several options may share a secondary item if they give it the same color, and an uncolored secondary item is at most once). Without colors this is the exact cover of File DancingLinks.h, with the same solutions, visited in another order.

The structure: the nodes of the options are one array of records { item , loc , color } of 16 bytes, the nodes of an option consecutive and followed by a spacer whose item is minus the size of the option, so that the other nodes of an option are walked by the index alone. Each item x has a segment of an array set, where its active options are the first size( x ) entries, each node knowing its place loc in the segment of its item: a sparse set of Briggs and Torczon, where an option leaves the set of x by a swap with the last active one and a decrement of size( x ), in O( 1 ). The active items are a sparse set too, the array of the items with the place pos( x ) of each.

The search, at each level: the active primary item x with the least size( x ) (the MRV rule, ties to the least index) is taken out, its options are hidden from the other items, and the sizes of all the active items are pushed on a stack; then each option of x in turn takes its other items out and hides their incompatible options (all of them for a primary or uncolored item, those of another color for a colored one), and the search goes one level deeper. Going back costs no undo of the swaps: the sizes on the stack are written back, and the sets are again those of the level, in another order, so that a level costs O( active ) to save and restore instead of an update per link. Hiding an option checks the size of each primary item it leaves: a size 0 abandons the choice at once, before going deeper, and a size 1 makes the item a forced move, taken at the next level without saving the sizes (its only option needs no return). The time is O( 1 ) per update of a set; the worst case stays exponential, as the problem is NP-complete.

The contracts [see File Contract.h]: the items of an option are distinct, in [ 0 , primary + secondary ), one at least primary, and a color, if given, is not negative and only on a secondary item; every solution visited is a solution, an audit. The operations are defined in FastExactCover.tpp.

    1. Knuth, The Art of Computer Programming, vol. 4B, Addison-Wesley, 2022, section 7.2.2.1 (Algorithms X and C)

    1. Knuth, SSXCC, the program of the exact covering with colors on sparse sets, 2023, https://cs.stanford.edu/~knuth/programs.html

  1. Briggs, L. Torczon, An efficient representation for sparse sets, ACM Letters on Programming Languages and Systems 2(1-4), 59-69, 1993, doi:10.1145/176454.176484

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes