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)]
55pub struct ExactCoverBy3Sets {
56    /// Size of the universe (elements are 0..universe_size, must be divisible by 3).
57    universe_size: usize,
58    /// Collection of 3-element subsets, each represented as a sorted triple of elements.
59    subsets: Vec<[usize; 3]>,
60}
61
62#[derive(Debug, Deserialize, crate::CreateSpec)]
63struct ExactCoverBy3SetsCreateSpec {
64    universe_size: usize,
65    #[create(codec = "semicolon-separated")]
66    subsets: Vec<[usize; 3]>,
67}
68
69impl TryFrom<ExactCoverBy3SetsCreateSpec> for ExactCoverBy3Sets {
70    type Error = crate::registry::ConstructionError;
71    fn try_from(mut spec: ExactCoverBy3SetsCreateSpec) -> Result<Self, Self::Error> {
72        if !spec.universe_size.is_multiple_of(3) {
73            return Err("universe_size must be divisible by 3".into());
74        }
75        for (index, subset) in spec.subsets.iter_mut().enumerate() {
76            if subset[0] == subset[1] || subset[0] == subset[2] || subset[1] == subset[2] {
77                return Err(format!("subset {index} contains duplicate elements").into());
78            }
79            if let Some(&element) = subset
80                .iter()
81                .find(|&&element| element >= spec.universe_size)
82            {
83                return Err(
84                    format!("subset {index} contains out-of-range element {element}").into(),
85                );
86            }
87            subset.sort();
88        }
89        Ok(Self {
90            universe_size: spec.universe_size,
91            subsets: spec.subsets,
92        })
93    }
94}
95
96impl ExactCoverBy3Sets {
97    /// Create a new X3C problem.
98    ///
99    /// # Panics
100    ///
101    /// Panics if `universe_size` is not divisible by 3, or if any subset
102    /// contains duplicate elements or elements outside the universe.
103    pub fn new(universe_size: usize, subsets: Vec<[usize; 3]>) -> Self {
104        assert!(
105            universe_size.is_multiple_of(3),
106            "Universe size must be divisible by 3, got {}",
107            universe_size
108        );
109        let mut subsets = subsets;
110        for (i, subset) in subsets.iter_mut().enumerate() {
111            assert!(
112                subset[0] != subset[1] && subset[0] != subset[2] && subset[1] != subset[2],
113                "Subset {} contains duplicate elements: {:?}",
114                i,
115                subset
116            );
117            for &elem in subset.iter() {
118                assert!(
119                    elem < universe_size,
120                    "Subset {} contains element {} which is outside universe of size {}",
121                    i,
122                    elem,
123                    universe_size
124                );
125            }
126            subset.sort();
127        }
128        Self {
129            universe_size,
130            subsets,
131        }
132    }
133
134    /// Get the universe size.
135    pub fn universe_size(&self) -> usize {
136        self.universe_size
137    }
138
139    /// Get the number of subsets in the collection.
140    pub fn num_subsets(&self) -> usize {
141        self.subsets.len()
142    }
143
144    /// Get q = universe_size / 3, the number of subsets in any exact cover.
145    ///
146    /// `ExactCoverBy3Sets::new` enforces `universe_size % 3 == 0`, so this
147    /// division is always exact.
148    pub fn q(&self) -> usize {
149        self.universe_size / 3
150    }
151
152    /// Get the number of sets in the collection.
153    pub fn num_sets(&self) -> usize {
154        self.num_subsets()
155    }
156
157    /// Get the subsets.
158    pub fn subsets(&self) -> &[[usize; 3]] {
159        &self.subsets
160    }
161
162    /// Get the sets.
163    pub fn sets(&self) -> &[[usize; 3]] {
164        self.subsets()
165    }
166
167    /// Get a specific subset.
168    pub fn get_subset(&self, index: usize) -> Option<&[usize; 3]> {
169        self.subsets.get(index)
170    }
171
172    /// Check if a configuration is a valid exact cover.
173    ///
174    /// A valid exact cover selects exactly q = universe_size/3 subsets
175    /// that are pairwise disjoint and whose union equals the universe.
176    pub fn is_valid_solution(
177        &self,
178        config: &[bool],
179    ) -> Result<bool, crate::traits::EvaluationError> {
180        if config.len() != self.subsets.len() {
181            return Err(crate::traits::EvaluationError::InvalidConfiguration(
182                "subset-selection length does not match the instance".into(),
183            ));
184        }
185
186        let q = self.universe_size / 3;
187        if config.iter().filter(|&&selected| selected).count() != q {
188            return Ok(false);
189        }
190
191        let mut covered = HashSet::with_capacity(self.universe_size);
192        for (subset, &selected) in self.subsets.iter().zip(config) {
193            if selected {
194                for &element in subset {
195                    if !covered.insert(element) {
196                        return Ok(false);
197                    }
198                }
199            }
200        }
201        Ok(covered.len() == self.universe_size)
202    }
203
204    /// Get the elements covered by the selected subsets.
205    pub fn covered_elements(&self, config: &[bool]) -> HashSet<usize> {
206        let mut covered = HashSet::new();
207        for (i, &selected) in config.iter().enumerate() {
208            if selected {
209                if let Some(subset) = self.subsets.get(i) {
210                    covered.extend(subset.iter().copied());
211                }
212            }
213        }
214        covered
215    }
216}
217
218impl Problem for ExactCoverBy3Sets {
219    const NAME: &'static str = "ExactCoverBy3Sets";
220    type Solution = Vec<bool>;
221    type Value = crate::types::Or;
222
223    crate::problem_parameters![
224        ("num_sets", num_sets),
225        ("num_subsets", num_subsets),
226        ("universe_size", universe_size),
227    ];
228
229    fn evaluate(
230        &self,
231        config: &Self::Solution,
232    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
233        Ok(crate::types::Or(self.is_valid_solution(config)?))
234    }
235
236    fn variant() -> Vec<(&'static str, &'static str)> {
237        crate::variant_params![]
238    }
239}
240
241impl crate::solvers::BruteForceProblem for ExactCoverBy3Sets {
242    fn dimensions(&self) -> Vec<usize> {
243        vec![2; self.subsets.len()]
244    }
245}
246
247crate::declare_variants! {
248    default ExactCoverBy3Sets => "2^universe_size" create ExactCoverBy3SetsCreateSpec,
249}
250
251crate::register_brute_force! {
252    ExactCoverBy3Sets decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
253}
254
255#[cfg(feature = "example-db")]
256pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
257    vec![crate::example_db::specs::ModelExampleSpec {
258        id: "exact_cover_by_3_sets",
259        instance: Box::new(ExactCoverBy3Sets::new(
260            9,
261            vec![
262                [0, 1, 2],
263                [0, 2, 4],
264                [3, 4, 5],
265                [3, 5, 7],
266                [6, 7, 8],
267                [1, 4, 6],
268                [2, 5, 8],
269            ],
270        )),
271        optimal_config: serde_json::json!(vec![true, false, true, false, true, false, false]),
272        optimal_value: serde_json::json!(true),
273    }]
274}
275
276#[cfg(test)]
277#[path = "../../unit_tests/models/set/exact_cover_by_3_sets.rs"]
278mod tests;
problemreductions/models/set/exact_cover_by_3_sets.rs

problemreductions/models/set/
exact_cover_by_3_sets.rs
