# exact-covers

[![Crates.io](https://img.shields.io/crates/v/exact-covers)](https://crates.io/crates/exact-covers)
[![docs.rs](https://img.shields.io/docsrs/exact-covers)](https://docs.rs/exact-covers)
[![Build status](https://github.com/hsanzg/exact-covers/actions/workflows/test.yml/badge.svg)](https://github.com/hsanzg/exact-covers/actions/)

<!-- The following section is autogenerated by the cargo-sync-readme utility;
     to modify its contents, update the crate documentation in the `src/lib.rs`
     file and run the `cargo sync-readme` command. -->

<!-- cargo-sync-readme start -->

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][dl] [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)][taocp4b],
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**][taocp4b], 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)][sparsesets],
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)][taocp4c], 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)][taocp4b], 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.

[dl]: https://arxiv.org/pdf/cs/0011047.pdf
[taocp4b]: https://www-cs-faculty.stanford.edu/~knuth/taocp.html#vol4
[taocp4c]: https://cs.stanford.edu/~knuth/fasc7a.ps.gz
[sparsesets]: https://dl.acm.org/doi/pdf/10.1145/176454.176484
[`examples`]: https://github.com/hsanzg/exact-covers/tree/main/examples
[`langford_pairs.rs`]: https://github.com/hsanzg/exact-covers/blob/main/examples/langford_pairs.rs
[Langford pairings]: https://en.wikipedia.org/wiki/Langford_pairing
[`polycube_packing.rs`]: https://github.com/hsanzg/exact-covers/blob/main/examples/polycube_packing.rs
[Y pentacubes]: https://en.wikipedia.org/wiki/Polycube
[`domino_chessboard.rs`]: https://github.com/hsanzg/exact-covers/blob/main/examples/domino_chessboard.rs

<!-- cargo-sync-readme end -->

## License

[MIT](LICENSE) &copy; [Hugo Sanz González](https://hgsg.me)

[`Problem`]: https://docs.rs/exact-covers/latest/exact-covers/struct.Problem.html
[`DlSolver`]: https://docs.rs/exact-covers/latest/exact-covers/struct.DlSolver.html
[`DcSolver`]: https://docs.rs/exact-covers/latest/exact-covers/struct.DcSolver.html