exact_cover/lib.rs
1//! Asynchronous [exact cover] solver library using Knuth's [dancing links (DLX)] algorithm.
2//!
3//! [exact cover]: https://en.wikipedia.org/wiki/Exact_cover
4//! [dancing links (DLX)]: https://en.wikipedia.org/wiki/Dancing_Links
5//!
6//! ⚠️ This library is working in progress and the API is highly likely to be changed.
7//!
8//! # Concept
9//!
10//! Many puzzle-like problems, such as polyomino packing, Sudoku, N-queens problem, etc.
11//! can be modeled as exact cover problems. This library provides an efficient solver to
12//! the generic exact cover problem and its generalizations, so that you can model your own problem
13//! as an exact cover problem, solve it, and further anaylize the solutions by code.
14//!
15//! # Basic example
16//!
17//! ```
18//! use exact_cover::{Problem, Solver, SolverEvent};
19//!
20//! fn main() {
21//! let mut prob = Problem::default();
22//! prob.add_constraints(1..=3);
23//! prob.add_subset("A", vec![1, 2, 3]);
24//! prob.add_subset("B", vec![1]);
25//! prob.add_subset("C", vec![2]);
26//! prob.add_subset("D", vec![3]);
27//! prob.add_subset("E", vec![1, 2]);
28//! prob.add_subset("F", vec![2, 3]);
29//!
30//! let mut solver = Solver::new(prob);
31//! let mut solutions = vec![];
32//! solver.run();
33//!
34//! for event in solver {
35//! if let SolverEvent::SolutionFound(sol) = event {
36//! solutions.push(sol);
37//! }
38//! }
39//!
40//! println!("{:?}", solutions); // [["A"], ["B", "C", "D"], ["B", "F"], ["E", "D"]]
41//! }
42//! ```
43//!
44//! # Asynchronous API
45//!
46//! ⚠️ The feature is not available yet.
47//!
48//! Solving a complex exact cover problem takes a long time.
49//! Users don't want to wait for the solving process to end without knowing
50//! how far it has progressed or how much time is left.
51//! This library provides an asynchronous API and various features to help with this issue.
52//!
53//! - Thanks to the asynchronous API, your program doesn't have to wait for the solver
54//! until it finds the next solution.
55//! - You can fetch the estimated progress of the solving process, anytime you want.
56//! - When the search space is too large and the solving process is not going to end in centuries,
57//! you can abort the solver.
58//! - You can pause the solving process and save the solver state to resume later.
59
60pub mod vector;
61
62pub mod dlx;
63pub mod callback;
64
65pub mod problem;
66pub mod solver;
67
68pub mod problems;
69
70pub use problem::Problem;
71pub use solver::{Solver, SolverEvent};