exact_cover/
problem.rs

1//! Provides a generic problem type that defines constraints and subsets.
2//! 
3//! Every complex exact cover problem (such as polyomino packing or Sudoku) first generates
4//! this basic [`Problem`] instance before handing it to a solver.
5//! To see examples of more complex problems, see [`problems`](crate::problems) module.
6
7use std::hash::Hash;
8use indexmap::{IndexMap, IndexSet};
9
10/// Base trait for subset names and constraints.
11pub trait Value: Clone + Hash + Eq {}
12impl<T: Clone + Hash + Eq> Value for T {}
13
14/// An exact cover problem instance.
15/// 
16/// The subsets are identified with a name with a type `N`.
17/// The elements of the set are called constraints and have a type `C`.
18/// 
19/// # Order
20/// 
21/// The order of subsets and constraints is determined by the insertion order.
22/// It uses [`IndexMap`] and [`IndexSet`] internally to keep track of the order.
23/// 
24/// The subset order can affect the order of the solutions and
25/// the algorithm performance, but it would not be a significant effect
26/// as our algorithm uses the MRV heuristic.
27#[derive(Clone)]
28#[cfg_attr(test, derive(Debug))]
29pub struct Problem<N: Value, C: Value> { // TOOD: Constraint will be more complex type
30    constraints: IndexSet<C>,
31    subsets: IndexMap<N, Vec<C>>,
32}
33
34impl<N: Value, C: Value> Default for Problem<N, C> {
35    fn default() -> Self {
36        Problem {
37            constraints: Default::default(),
38            subsets: Default::default(),
39        }
40    }
41}
42
43impl<N: Value, C: Value> Problem<N, C> {
44    // TODO: hide IndexMap/IndexSet from API
45    /// Returns a reference to the subsets of the problem.
46    pub fn subsets(&self) -> &IndexMap<N, Vec<C>> { &self.subsets }
47    /// Returns a reference to the constraints of the problem.
48    pub fn constraints(&self) -> &IndexSet<C> { &self.constraints }
49
50    /// Adds a subset to the problem.
51    /// 
52    /// If the subset name already exists,
53    /// it updates the subset of that name with the given new subset.
54    pub fn add_subset(&mut self, name: N, subset: Vec<C>) {
55        self.subsets.insert(name, subset);
56    }
57    
58    /// Adds a constraint (set element) to the problem.
59    pub fn add_constraint(&mut self, constraint: C) {
60        self.constraints.insert(constraint);
61    }
62    
63    /// Adds several constraints to the problem.
64    pub fn add_constraints<I: IntoIterator<Item = C>>(&mut self, constraints: I) {
65        for constraint in constraints {
66            self.constraints.insert(constraint);
67        }
68    }
69}
70
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn problem_can_be_created() {
78        let mut prob = Problem::default();
79        prob.add_constraints(1..=7);
80        prob.add_subset("A", vec![3, 5, 6]);
81        prob.add_subset("B", vec![1, 4, 7]);
82        prob.add_subset("C", vec![2, 3, 6]);
83        prob.add_subset("D", vec![1, 4]);
84        prob.add_subset("E", vec![2, 7]);
85        prob.add_subset("F", vec![4, 5, 7]);
86    }
87}
exact_cover/problem.rs

exact_cover/
problem.rs
