xcc/lib.rs
1#![warn(clippy::pedantic)]
2#![warn(missing_docs)]
3//! Colored Exact Cover Solver
4//!
5//! This is a Rust implementation of Exact Cover, with the addition of the
6//! ability to color secondary items. The algorithm is based on Donald Knuth's
7//! Algorithm C, as described in _The Art of Computer Programming_, Volume 4B,
8//! under "Color-controlled covering".
9//!
10//! The solver takes:
11//! * a set of _primary items_;
12//! * a set of _secondary items_;
13//! * a set of _options_, which are subsets of the primary and secondary items.
14//!
15//! The solver's job is to find a subset of the options that
16//! * includes each primary item once and only once, and
17//! * colors each secondary item consistently.
18//!
19//! Options can contain secondary items with or without colors. If a secondary
20//! item has no color, then the solver will not use it more than once (so that
21//! it defines a "zero or one" constraint). If an option has a secondary item
22//! with a color, then the solver can use it _with the same color_ as many times
23//! as it wants, but not uncolored or with a different color.
24//!
25//! The solver can be used to solve many different kinds of problems:
26//! - Sudoku-like puzzles
27//! - Shape puzzles, such as "tile a 6x10 rectangle with the 12 pentominos"
28//! - Word puzzles, such as "fill a 5x4 grid with words from a dictionary"
29//! - Most Nikoli puzzles
30//! - Graph coloring
31//! - Scheduling
32//! - Many more!
33//!
34//! There are many examples in the `examples` directory.
35//!
36
37mod builder;
38mod matrix;
39pub mod samples;
40mod solver;
41mod types;
42mod unique;
43
44pub use self::builder::Builder;
45pub use self::matrix::Matrix;
46pub use self::solver::Solution;
47pub use self::solver::{Limit, Solver};
48pub use self::types::ColoredItem;
49pub use self::types::{Color, ItemId};
50pub use self::unique::Unique;