### 4 releases

0.2.1 | Jul 15, 2024 |
---|---|

0.2.0 | Jul 15, 2024 |

0.1.1 | Jan 25, 2024 |

0.1.0 | Jan 25, 2024 |

#**552** in Data structures

**126** downloads per month

**MIT**license

72KB

798 lines

# 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:

finds all solutions to an XCC problem. It implements a slightly modified form of Knuth's Algorithm 7.2.2.1C.`DlSolver`

adheres to the same input and output conventions as the previous structure, but it uses the dancing cells technique.`DcSolver`

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

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

finds all Langford pairings of $2n$ numbers.`langford_pairs.rs`

computes the number of ways to arrange 25 Y pentacubes in a $5\times5\times5$ cuboid.`polycube_packing.rs`

finds all ways to pack 32 dominoes into a chessboard.`domino_chessboard.rs`