algoxcc/
lib.rs

1//! The crate implements an algorithm for solving [exact cover] problems
2//! using:
3//! - [backtracking] and minimal remain values [heuristic] logic and
4//! - an optimzed data structure called dancing cells based on sparse sets
5//!
6//! Define a [Problem] and use function [solve] to find solution(s) for the generalized problem with both primary
7//! items and secondary items with colors, and for the standard problem
8//! with only primary items.
9//!
10//! See usage examples for function [solve].
11//!
12//! [exact cover]: https://en.wikipedia.org/wiki/Exact_cover
13//! [backtracking]: https://en.wikipedia.org/wiki/Backtracking
14//! [heuristic]: https://en.wikipedia.org/wiki/Heuristic_(computer_science)
15//!
16
17pub use solver::DancingCells;
18pub use solver::Solutions;
19pub use solver::option::*;
20pub use solver::param_error::ParamError;
21pub use solver::problem::*;
22
23mod solver;
24
25/// Function solve looks for [Solutions] (exact covers)
26///
27/// In a [Problem] made of primary and secondary
28/// items and options (based on [Option]) with
29/// primary items and secondary items
30/// with optional color and returns a list of found solutions,
31/// where each solution is a list of option labels
32///
33/// The solution set of options will cover all primary items
34/// exactly once and all secondary options covered will have
35/// the same color in options
36///
37/// The method will return all or first found solution
38/// depending on input value get_all
39///
40/// Function solve also handle exact cover with only primary options
41/// using empty secondary items input in problem and options.
42///
43/// ## Return
44///
45/// The function first validate the input problem. Possible errors:
46/// - The input problem have no primary items!
47/// - Unknown primary item in option
48/// - Unknown secondary item in option
49/// - Primary not found in options
50///
51/// ## Example exact cover with colors
52///
53/// ```
54/// use algoxcc::{Option, Problem, solve};
55///
56/// let result = Problem::new(
57///     &vec!["p", "q", "r"],
58///     &vec!["x", "y"],
59///     &vec![
60///         Option::new_validated(
61///             "p q x y:A",
62///             &vec!["p", "q"],
63///             &vec![("x", ""), ("y", "A")],
64///         ),
65///         Option::new_validated(
66///             "p r x:A y",
67///             &vec!["p", "r"],
68///             &vec![("x", "A"), ("y", "")],
69///         ),
70///         Option::new_validated( "p x:B", &vec!["p"], &vec![("x", "B")]),
71///         Option::new_validated( "q x:A", &vec!["q"], &vec![("x", "A")]),
72///         Option::new_validated("r y:B", &vec!["r"], &vec![("y", "B")]),
73///     ]);
74/// assert!(result.is_ok());
75/// let problem = result.unwrap();
76///
77/// let result = solve(&problem, true);
78/// assert!(result.is_ok());
79/// let solutions = result.unwrap();
80///
81/// assert_eq!(1, solutions.count(), "Expect to find 1 solution");
82/// let first = solutions.first().unwrap();
83/// assert_eq!(2, first.len(), "Expect 2 options in solution");
84/// assert!(first.contains(&"q x:A".to_string()));
85/// assert!(first.contains(&"p r x:A y".to_string()));
86/// ```
87///
88/// ## Example exact cover with only primary options
89///
90/// ```
91/// use algoxcc::{Option, Problem, solve};
92///
93/// let problem = Problem::new_validated(
94///     &vec!["a", "b", "c", "d"],
95///     &vec![],
96///     &vec![
97///         Option::new_validated("o1", &vec!["b"], &vec![]),
98///         Option::new_validated("o2", &vec!["a"], &vec![]),
99///         Option::new_validated("o3", &vec!["b", "c"], &vec![]),
100///         Option::new_validated("o4", &vec!["a", "c", "d"], &vec![]),
101///     ]
102/// );
103///
104/// let result = solve(&problem, true);
105/// assert!(result.is_ok());
106/// let solutions = result.unwrap();
107///
108/// assert_eq!(1, solutions.count(), "Expect to find 1 solution");
109/// let first = solutions.first().unwrap();
110/// assert_eq!(2, first.len(), "Expect 2 options in solution");
111/// assert_eq!("o1", first[0], "First option is o1");
112/// assert_eq!("o4", first[1], "Second option is o4");
113///
114/// ```
115pub fn solve(problem: &Problem, get_all: bool) -> Result<Solutions, ParamError> {
116    let mut dc = DancingCells::new(&problem)?;
117    if get_all {
118        return Ok(dc.solve_all());
119    }
120    Ok(dc.solve_first())
121}
algoxcc/lib.rs

algoxcc/
lib.rs
