algoxcc 0.1.2

A solver for an exact cover with colors problem
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

//! The crate implements an algorithm for solving [exact cover] problems
//! using:
//! - [backtracking] and minimal remain values [heuristic] logic and
//! - an optimzed data structure called dancing cells based on sparse sets
//!
//! Define a [Problem] and use function [solve] to find solution(s) for the generalized problem with both primary
//! items and secondary items with colors, and for the standard problem
//! with only primary items.
//!
//! See usage examples for function [solve].
//!
//! [exact cover]: https://en.wikipedia.org/wiki/Exact_cover
//! [backtracking]: https://en.wikipedia.org/wiki/Backtracking
//! [heuristic]: https://en.wikipedia.org/wiki/Heuristic_(computer_science)
//!

pub use solver::DancingCells;
pub use solver::Solutions;
pub use solver::option::*;
pub use solver::param_error::ParamError;
pub use solver::problem::*;

mod solver;

/// Function solve looks for [Solutions] (exact covers)
///
/// In a [Problem] made of primary and secondary
/// items and options (based on [Option]) with
/// primary items and secondary items
/// with optional color and returns a list of found solutions,
/// where each solution is a list of option labels
///
/// The solution set of options will cover all primary items
/// exactly once and all secondary options covered will have
/// the same color in options
///
/// The method will return all or first found solution
/// depending on input value get_all
///
/// Function solve also handle exact cover with only primary options
/// using empty secondary items input in problem and options.
///
/// ## Return
///
/// The function first validate the input problem. Possible errors:
/// - The input problem have no primary items!
/// - Unknown primary item in option
/// - Unknown secondary item in option
/// - Primary not found in options
///
/// ## Example exact cover with colors
///
/// ```
/// use algoxcc::{Option, Problem, solve};
///
/// let result = Problem::new(
///     &vec!["p", "q", "r"],
///     &vec!["x", "y"],
///     &vec![
///         Option::new_validated(
///             "p q x y:A",
///             &vec!["p", "q"],
///             &vec![("x", ""), ("y", "A")],
///         ),
///         Option::new_validated(
///             "p r x:A y",
///             &vec!["p", "r"],
///             &vec![("x", "A"), ("y", "")],
///         ),
///         Option::new_validated( "p x:B", &vec!["p"], &vec![("x", "B")]),
///         Option::new_validated( "q x:A", &vec!["q"], &vec![("x", "A")]),
///         Option::new_validated("r y:B", &vec!["r"], &vec![("y", "B")]),
///     ]);
/// assert!(result.is_ok());
/// let problem = result.unwrap();
///
/// let result = solve(&problem, true);
/// assert!(result.is_ok());
/// let solutions = result.unwrap();
///
/// assert_eq!(1, solutions.count(), "Expect to find 1 solution");
/// let first = solutions.first().unwrap();
/// assert_eq!(2, first.len(), "Expect 2 options in solution");
/// assert!(first.contains(&"q x:A".to_string()));
/// assert!(first.contains(&"p r x:A y".to_string()));
/// ```
///
/// ## Example exact cover with only primary options
///
/// ```
/// use algoxcc::{Option, Problem, solve};
///
/// let problem = Problem::new_validated(
///     &vec!["a", "b", "c", "d"],
///     &vec![],
///     &vec![
///         Option::new_validated("o1", &vec!["b"], &vec![]),
///         Option::new_validated("o2", &vec!["a"], &vec![]),
///         Option::new_validated("o3", &vec!["b", "c"], &vec![]),
///         Option::new_validated("o4", &vec!["a", "c", "d"], &vec![]),
///     ]
/// );
///
/// let result = solve(&problem, true);
/// assert!(result.is_ok());
/// let solutions = result.unwrap();
///
/// assert_eq!(1, solutions.count(), "Expect to find 1 solution");
/// let first = solutions.first().unwrap();
/// assert_eq!(2, first.len(), "Expect 2 options in solution");
/// assert_eq!("o1", first[0], "First option is o1");
/// assert_eq!("o4", first[1], "Second option is o4");
///
/// ```
pub fn solve(problem: &Problem, get_all: bool) -> Result<Solutions, ParamError> {
    let mut dc = DancingCells::new(&problem)?;
    if get_all {
        return Ok(dc.solve_all());
    }
    Ok(dc.solve_first())
}