dancing_links/
lib.rs

1#![deny(missing_docs)]
2
3//! Implementation of [Dancing Links](https://en.wikipedia.org/wiki/Dancing_Links)
4//! and [Algorithm X](https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X) for solving
5//!  [exact cover](https://en.wikipedia.org/wiki/Exact_cover) problems.
6
7pub mod grid;
8pub mod latin_square;
9pub mod queens;
10pub(crate) mod solver;
11pub mod sudoku;
12pub(crate) mod util;
13
14pub use solver::Solver;
15
16/// An instance of an exact cover problem.
17pub trait ExactCover {
18    /// The type of values that are elements of a solution to the exact cover
19    /// problem.
20    type Possibility: core::fmt::Debug;
21
22    /// The type of value that are constraints on a given instance of an exact
23    /// cover problem.
24    type Constraint: core::fmt::Debug;
25
26    /// Return true if the given `Possibility` will satisfy the given
27    /// `Constraint`.
28    fn satisfies(&self, poss: &Self::Possibility, cons: &Self::Constraint) -> bool;
29
30    /// Return true if the given `Constraint` is optional.
31    fn is_optional(&self, cons: &Self::Constraint) -> bool;
32
33    /// Return a list of possibilities for this instance of the problem.
34    fn possibilities(&self) -> &[Self::Possibility];
35
36    /// Return a list of constraints that must be satisfied for this instance of
37    /// the problem.
38    fn constraints(&self) -> &[Self::Constraint];
39
40    /// Return an iterator over all solutions to this instance of the exact
41    /// cover problem.
42    fn solver(&self) -> Solver<Self>
43    where
44        Self: Sized,
45    {
46        Solver::new(self)
47    }
48}
dancing_links/lib.rs

dancing_links/
lib.rs
