problemreductions/models/set/
exact_cover_by_3_sets.rs

1//! Exact Cover by 3-Sets (X3C) problem implementation.
2//!
3//! Given a universe X with |X| = 3q elements and a collection C of 3-element
4//! subsets of X, determine if C contains an exact cover -- a subcollection of
5//! q disjoint triples covering every element exactly once.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10use std::collections::HashSet;
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "ExactCoverBy3Sets",
15        display_name: "Exact Cover by 3-Sets",
16        aliases: &["X3C"],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Set,
19        module_path: module_path!(),
20        description: "Determine if a collection of 3-element subsets contains an exact cover",
21        fields: ExactCoverBy3SetsCreateSpec::FIELDS,
22    }
23}
24
25/// Exact Cover by 3-Sets (X3C) problem.
26///
27/// Given a universe X = {0, 1, ..., 3q-1} and a collection C of 3-element
28/// subsets of X, determine if there exists a subcollection C' of exactly q
29/// subsets such that every element of X appears in exactly one member of C'.
30///
31/// This is a classical NP-complete problem (Karp, 1972), widely used as
32/// a source problem for NP-completeness reductions.
33///
34/// # Example
35///
36/// ```
37/// use problemreductions::models::set::ExactCoverBy3Sets;
38/// use problemreductions::{Problem, BruteForce};
39///
40/// // Universe: {0, 1, 2, 3, 4, 5} (q = 2)
41/// // Subsets: S0={0,1,2}, S1={3,4,5}, S2={0,3,4}
42/// let problem = ExactCoverBy3Sets::new(
43///     6,
44///     vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]],
45/// );
46///
47/// let solver = BruteForce::new();
48/// let solutions = solver.find_all_witnesses(&problem).unwrap();
49///
50/// // S0 and S1 form an exact cover
51/// assert_eq!(solutions.len(), 1);
52/// assert!(problem.evaluate(&solutions[0]).unwrap());
53/// ```
54#[derive(Debug, Clone, Serialize, Deserialize)]
55#[serde(try_from = "ExactCoverBy3SetsCreateSpec")]
56pub struct ExactCoverBy3Sets {
57    /// Size of the universe (elements are 0..universe_size, must be divisible by 3).
58    universe_size: usize,
59    /// Collection of 3-element subsets, each represented as a sorted triple of elements.
60    subsets: Vec<[usize; 3]>,
61}
62
63#[derive(Debug, Deserialize, crate::CreateSpec)]
64struct ExactCoverBy3SetsCreateSpec {
65    universe_size: usize,
66    #[create(codec = "semicolon-separated")]
67    subsets: Vec<[usize; 3]>,
68}
69
70impl TryFrom<ExactCoverBy3SetsCreateSpec> for ExactCoverBy3Sets {
71    type Error = crate::registry::ConstructionError;
72
73    fn try_from(spec: ExactCoverBy3SetsCreateSpec) -> Result<Self, Self::Error> {
74        Self::try_new(spec.universe_size, spec.subsets)
75    }
76}
77
78impl ExactCoverBy3Sets {
79    /// Create a new X3C problem.
80    ///
81    /// # Panics
82    ///
83    /// Panics if `universe_size` is not divisible by 3, or if any subset
84    /// contains duplicate elements or elements outside the universe.
85    pub fn new(universe_size: usize, subsets: Vec<[usize; 3]>) -> Self {
86        Self::try_new(universe_size, subsets).unwrap_or_else(|error| panic!("{error}"))
87    }
88
89    fn try_new(
90        universe_size: usize,
91        mut subsets: Vec<[usize; 3]>,
92    ) -> Result<Self, crate::registry::ConstructionError> {
93        if !universe_size.is_multiple_of(3) {
94            return Err(
95                format!("Universe size must be divisible by 3, got {universe_size}").into(),
96            );
97        }
98        for (index, subset) in subsets.iter_mut().enumerate() {
99            if subset[0] == subset[1] || subset[0] == subset[2] || subset[1] == subset[2] {
100                return Err(format!("subset {index} contains duplicate elements").into());
101            }
102            if let Some(&element) = subset.iter().find(|&&element| element >= universe_size) {
103                return Err(
104                    format!("Subset {index} contains element {element} which is outside universe of size {universe_size}").into(),
105                );
106            }
107            subset.sort();
108        }
109        Ok(Self {
110            universe_size,
111            subsets,
112        })
113    }
114
115    /// Get the universe size.
116    pub fn universe_size(&self) -> usize {
117        self.universe_size
118    }
119
120    /// Get the number of subsets in the collection.
121    pub fn num_subsets(&self) -> usize {
122        self.subsets.len()
123    }
124
125    /// Get q = universe_size / 3, the number of subsets in any exact cover.
126    ///
127    /// `ExactCoverBy3Sets::new` enforces `universe_size % 3 == 0`, so this
128    /// division is always exact.
129    pub fn q(&self) -> usize {
130        self.universe_size / 3
131    }
132
133    /// Get the number of sets in the collection.
134    pub fn num_sets(&self) -> usize {
135        self.num_subsets()
136    }
137
138    /// Get the subsets.
139    pub fn subsets(&self) -> &[[usize; 3]] {
140        &self.subsets
141    }
142
143    /// Get the sets.
144    pub fn sets(&self) -> &[[usize; 3]] {
145        self.subsets()
146    }
147
148    /// Get a specific subset.
149    pub fn get_subset(&self, index: usize) -> Option<&[usize; 3]> {
150        self.subsets.get(index)
151    }
152
153    /// Check if a configuration is a valid exact cover.
154    ///
155    /// A valid exact cover selects exactly q = universe_size/3 subsets
156    /// that are pairwise disjoint and whose union equals the universe.
157    pub fn is_valid_solution(
158        &self,
159        config: &[bool],
160    ) -> Result<bool, crate::traits::EvaluationError> {
161        if config.len() != self.subsets.len() {
162            return Err(crate::traits::EvaluationError::InvalidConfiguration(
163                "subset-selection length does not match the instance".into(),
164            ));
165        }
166
167        let q = self.universe_size / 3;
168        if config.iter().filter(|&&selected| selected).count() != q {
169            return Ok(false);
170        }
171
172        let mut covered = HashSet::with_capacity(self.universe_size);
173        for (subset, &selected) in self.subsets.iter().zip(config) {
174            if selected {
175                for &element in subset {
176                    if !covered.insert(element) {
177                        return Ok(false);
178                    }
179                }
180            }
181        }
182        Ok(covered.len() == self.universe_size)
183    }
184
185    /// Get the elements covered by the selected subsets.
186    pub fn covered_elements(&self, config: &[bool]) -> HashSet<usize> {
187        let mut covered = HashSet::new();
188        for (i, &selected) in config.iter().enumerate() {
189            if selected {
190                if let Some(subset) = self.subsets.get(i) {
191                    covered.extend(subset.iter().copied());
192                }
193            }
194        }
195        covered
196    }
197}
198
199impl Problem for ExactCoverBy3Sets {
200    const NAME: &'static str = "ExactCoverBy3Sets";
201    type Solution = Vec<bool>;
202    type Value = crate::types::Or;
203
204    crate::problem_parameters![
205        ("num_subsets", num_subsets),
206        ("universe_size", universe_size),
207    ];
208
209    fn evaluate(
210        &self,
211        config: &Self::Solution,
212    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
213        Ok(crate::types::Or(self.is_valid_solution(config)?))
214    }
215
216    fn variant() -> Vec<(&'static str, &'static str)> {
217        crate::variant_params![]
218    }
219}
220
221impl crate::solvers::BruteForceProblem for ExactCoverBy3Sets {
222    fn dimensions(&self) -> Vec<usize> {
223        vec![2; self.subsets.len()]
224    }
225}
226
227crate::declare_variants! {
228    default ExactCoverBy3Sets => "2^universe_size" create ExactCoverBy3SetsCreateSpec,
229}
230
231crate::register_brute_force! {
232    ExactCoverBy3Sets decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
233}
234
235#[cfg(feature = "example-db")]
236pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
237    vec![crate::example_db::specs::ModelExampleSpec {
238        id: "exact_cover_by_3_sets",
239        instance: Box::new(ExactCoverBy3Sets::new(
240            9,
241            vec![
242                [0, 1, 2],
243                [0, 2, 4],
244                [3, 4, 5],
245                [3, 5, 7],
246                [6, 7, 8],
247                [1, 4, 6],
248                [2, 5, 8],
249            ],
250        )),
251        optimal_config: serde_json::json!(vec![true, false, true, false, true, false, false]),
252        optimal_value: serde_json::json!(true),
253    }]
254}
255
256#[cfg(test)]
257#[path = "../../unit_tests/models/set/exact_cover_by_3_sets.rs"]
258mod tests;
problemreductions/models/set/exact_cover_by_3_sets.rs

problemreductions/models/set/
exact_cover_by_3_sets.rs
