exact-covers

This crate provides implementations of D. E. Knuth and C. Solnon's algorithms for solving the exact cover problem with color controls.

Suppose we're given a collection $\mathcal{O}$ of options, each of which is a set of items; the exact cover problem is to find a subcollection $\mathcal{O}^\star\subseteq\mathcal{O}$ of options such that each item occurs in exactly one of $\mathcal{O}^\star$'s options. Knuth proposed a method that achieves this goal in the paper "Dancing Links", arXiv:cs/0011047 cs.DS (2000), whose title refers to a clever yet simple technique for deleting and restoring the nodes of a doubly linked list. His backtracking scheme, called Algorithm X, employs this "waltzing" of links to visit all exact covers with options $\mathcal{O}$ in a recursive, depth-first manner. [For further information, see Section 7.2.2.1 of The Art of Computer Programming 4B (2022), Part 2, 65–70.]

A slight modification of Algorithm X solves the considerably more general problem in which items fall into one of two categories: primary and secondary. Now the task is to find a subcollection $\mathcal{O}^\star\subseteq\mathcal{O}$ of options that cover every primary item exactly once, while covering every secondary item at most once. The exact covering with colors (XCC) problem arises if we go further and assign a color to the secondary items of each option. Then we say two options are compatible if their secondary items have matching colors, and we define a solution as a collection $\mathcal{O}^\star\subseteq\mathcal{O}$ of mutually compatible options that cover every primary item exactly once. (In contrast to the uncolored case, a secondary item can occur in more than one of $\mathcal{O}^\star$'s options provided that their colors are compatible.)

Fortunately the dancing links technique is also well suited to XCC problems. Knuth proved this when he introduced Algorithm C in Section 7.2.2.1 of TAOCP 4B, part 2, pages 87–91; his new procedure extends Algorithm X to colors. In 2020, C. Solnon suggested using the sparse-set data structure of P. Briggs and L. Torczon [ACM Letters on Programming Languages and Systems 2 (1993), 59–69] to store the database of currently active options and the list of items that need to be covered. Knuth prepared an implementation of this approach, called the "dancing cells" method, using the conventions of Algorithm C. Numerous benchmark tests for these two XCC solvers appear in Section 7.2.2.3 of TAOCP 4C (June 25, 2024), Pre-Fascicle 7A (preliminary draft), pages 64–65. To summarize the results of these experiments: there is no clear winner, and we don't yet know a rule for determining which method is best for a particular instance of XCC.

This crate is a library of subroutines for color-controlled covering of $N_1\ge0$ primary items and $N_2\ge0$ secondary items in the Rust programming language. The following structures are its most important pieces:

• DlSolver finds all solutions to an XCC problem. It implements a slightly modified form of Knuth's Algorithm 7.2.2.1C.
• DcSolver adheres to the same input and output conventions as the previous structure, but it uses the dancing cells technique.

Both implementations support option simplification via the removal of blocking and forcing. [For a discussion of these preprocessing operations, see Knuth, TAOCP 4B (2022), Part 2, 108–111.]

Also, the examples directory contains an instructive set of programs that apply these algorithms to a variety of problems:

• langford_pairs.rs finds all Langford pairings of $2n$ numbers.
• polycube_packing.rs computes the number of ways to arrange 25 Y pentacubes in a $5\times5\times5$ cuboid.
• domino_chessboard.rs finds all ways to pack 32 dominoes into a chessboard.

License

MIT © Hugo Sanz González