exact-covers

Let $I$ be a set of items. Given a collection $\mathcal{O}$ of subsets of $I$, an exact cover of $I$ is a subcollection $\mathcal{O}^\star$ of $\mathcal{O}$ such that each item in $I$ appears in exactly one option in $\mathcal{O}^\star$. The goal of an exact cover problem is to find one such subset of options $\mathcal{O}^\star$.

D. E. Knuth proposed a method for solving the exact cover problem in the paper Dancing Links, whose title refers to a clever yet simple technique technique for deleting and restoring the nodes of a doubly linked list. His backtracking algorithm, called Algorithm X, employs this "waltzing" of links to visit all exact covers of $I$ 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, Volume 4B, Part 2 (Addison-Wesley, 2022).

A slight modification to this procedure solves the considerably more general problem in which items fall into one of two categories: primary items, which must be covered by exactly one option in $\mathcal{O}^\star$, and secondary items, which can be in at most one option of $\mathcal{O}^\star$. This crate contains various implementations of Knuth's exact cover solvers and their data structures in the Rust programming language:

• ExactCovers finds all exact coverings of $I$ with options in $\mathcal{O}$ under the assumption that every option contains at least one primary item.
• ColoredExactCovers will solve the exact cover problem with color constraints.

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\times 5\times 5$ cuboid. R. Honsberger's book Mathematical Gems II (1976), Chapter 8, provides a good introduction to the techniques for solving polycube packing puzzles.

License

MIT © Hugo Sanz González