Expand description
Colored Exact Cover Solver
This is a Rust implementation of Exact Cover, with the addition of the ability to color secondary items. The algorithm is based on Donald Knuth’s Algorithm C, as described in The Art of Computer Programming, Volume 4B, under “Color-controlled covering”.
The solver takes:
- a set of primary items;
- a set of secondary items;
- a set of options, which are subsets of the primary and secondary items.
The solver’s job is to find a subset of the options that
- includes each primary item once and only once, and
- colors each secondary item consistently.
Options can contain secondary items with or without colors. If a secondary item has no color, then the solver will not use it more than once (so that it defines a “zero or one” constraint). If an option has a secondary item with a color, then the solver can use it with the same color as many times as it wants, but not uncolored or with a different color.
The solver can be used to solve many different kinds of problems:
- Sudoku-like puzzles
- Shape puzzles, such as “tile a 6x10 rectangle with the 12 pentominos”
- Word puzzles, such as “fill a 5x4 grid with words from a dictionary”
- Most Nikoli puzzles
- Graph coloring
- Scheduling
- Many more!
There are many examples in the examples directory.
Modules
- Builders for some common types of XCC problems.
Structs
- A builder for a matrix.
- Color of an item.
- Represents an item in the Dancing Links data structure that may or may not have a color assigned to it.
- ID of an item (column) in the matrix.
- A compiled specification of an exact cover problem with colored items.
- A solution to an exact cover problem.
- A solver for an exact cover problem with colored secondary items.
Enums
- A limit on the number of solutions to return. This is used by
Matrix::solve(). - The value returned from
DLX::solve_unique.