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::{FieldInfo, 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        module_path: module_path!(),
19        description: "Determine if a collection of 3-element subsets contains an exact cover",
20        fields: &[
21            FieldInfo { name: "universe_size", type_name: "usize", description: "Size of universe X (must be divisible by 3)" },
22            FieldInfo { name: "subsets", type_name: "Vec<[usize; 3]>", description: "Collection C of 3-element subsets of X" },
23        ],
24    }
25}
26
27/// Exact Cover by 3-Sets (X3C) problem.
28///
29/// Given a universe X = {0, 1, ..., 3q-1} and a collection C of 3-element
30/// subsets of X, determine if there exists a subcollection C' of exactly q
31/// subsets such that every element of X appears in exactly one member of C'.
32///
33/// This is a classical NP-complete problem (Karp, 1972), widely used as
34/// a source problem for NP-completeness reductions.
35///
36/// # Example
37///
38/// ```
39/// use problemreductions::models::set::ExactCoverBy3Sets;
40/// use problemreductions::{Problem, Solver, BruteForce};
41///
42/// // Universe: {0, 1, 2, 3, 4, 5} (q = 2)
43/// // Subsets: S0={0,1,2}, S1={3,4,5}, S2={0,3,4}
44/// let problem = ExactCoverBy3Sets::new(
45///     6,
46///     vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]],
47/// );
48///
49/// let solver = BruteForce::new();
50/// let solutions = solver.find_all_witnesses(&problem);
51///
52/// // S0 and S1 form an exact cover
53/// assert_eq!(solutions.len(), 1);
54/// assert!(problem.evaluate(&solutions[0]));
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct ExactCoverBy3Sets {
58    /// Size of the universe (elements are 0..universe_size, must be divisible by 3).
59    universe_size: usize,
60    /// Collection of 3-element subsets, each represented as a sorted triple of elements.
61    subsets: Vec<[usize; 3]>,
62}
63
64impl ExactCoverBy3Sets {
65    /// Create a new X3C problem.
66    ///
67    /// # Panics
68    ///
69    /// Panics if `universe_size` is not divisible by 3, or if any subset
70    /// contains duplicate elements or elements outside the universe.
71    pub fn new(universe_size: usize, subsets: Vec<[usize; 3]>) -> Self {
72        assert!(
73            universe_size.is_multiple_of(3),
74            "Universe size must be divisible by 3, got {}",
75            universe_size
76        );
77        let mut subsets = subsets;
78        for (i, subset) in subsets.iter_mut().enumerate() {
79            assert!(
80                subset[0] != subset[1] && subset[0] != subset[2] && subset[1] != subset[2],
81                "Subset {} contains duplicate elements: {:?}",
82                i,
83                subset
84            );
85            for &elem in subset.iter() {
86                assert!(
87                    elem < universe_size,
88                    "Subset {} contains element {} which is outside universe of size {}",
89                    i,
90                    elem,
91                    universe_size
92                );
93            }
94            subset.sort();
95        }
96        Self {
97            universe_size,
98            subsets,
99        }
100    }
101
102    /// Get the universe size.
103    pub fn universe_size(&self) -> usize {
104        self.universe_size
105    }
106
107    /// Get the number of subsets in the collection.
108    pub fn num_subsets(&self) -> usize {
109        self.subsets.len()
110    }
111
112    /// Get the number of sets in the collection.
113    pub fn num_sets(&self) -> usize {
114        self.num_subsets()
115    }
116
117    /// Get the subsets.
118    pub fn subsets(&self) -> &[[usize; 3]] {
119        &self.subsets
120    }
121
122    /// Get the sets.
123    pub fn sets(&self) -> &[[usize; 3]] {
124        self.subsets()
125    }
126
127    /// Get a specific subset.
128    pub fn get_subset(&self, index: usize) -> Option<&[usize; 3]> {
129        self.subsets.get(index)
130    }
131
132    /// Check if a configuration is a valid exact cover.
133    ///
134    /// A valid exact cover selects exactly q = universe_size/3 subsets
135    /// that are pairwise disjoint and whose union equals the universe.
136    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
137        self.evaluate(config).0
138    }
139
140    /// Get the elements covered by the selected subsets.
141    pub fn covered_elements(&self, config: &[usize]) -> HashSet<usize> {
142        let mut covered = HashSet::new();
143        for (i, &selected) in config.iter().enumerate() {
144            if selected == 1 {
145                if let Some(subset) = self.subsets.get(i) {
146                    covered.extend(subset.iter().copied());
147                }
148            }
149        }
150        covered
151    }
152}
153
154impl Problem for ExactCoverBy3Sets {
155    const NAME: &'static str = "ExactCoverBy3Sets";
156    type Value = crate::types::Or;
157
158    fn dims(&self) -> Vec<usize> {
159        vec![2; self.subsets.len()]
160    }
161
162    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
163        crate::types::Or({
164            if config.len() != self.subsets.len() || config.iter().any(|&value| value > 1) {
165                return crate::types::Or(false);
166            }
167
168            let q = self.universe_size / 3;
169
170            // Count selected subsets
171            let selected_count: usize = config.iter().filter(|&&v| v == 1).sum();
172            if selected_count != q {
173                return crate::types::Or(false);
174            }
175
176            // Check that selected subsets are pairwise disjoint and cover everything
177            let mut covered = HashSet::with_capacity(self.universe_size);
178            for (i, &selected) in config.iter().enumerate() {
179                if selected == 1 {
180                    if let Some(subset) = self.subsets.get(i) {
181                        for &elem in subset {
182                            if !covered.insert(elem) {
183                                // Element already covered -- not disjoint
184                                return crate::types::Or(false);
185                            }
186                        }
187                    }
188                }
189            }
190
191            // Check all elements are covered
192            covered.len() == self.universe_size
193        })
194    }
195
196    fn variant() -> Vec<(&'static str, &'static str)> {
197        crate::variant_params![]
198    }
199}
200
201crate::declare_variants! {
202    default ExactCoverBy3Sets => "2^universe_size",
203}
204
205#[cfg(feature = "example-db")]
206pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
207    vec![crate::example_db::specs::ModelExampleSpec {
208        id: "exact_cover_by_3_sets",
209        instance: Box::new(ExactCoverBy3Sets::new(
210            9,
211            vec![
212                [0, 1, 2],
213                [0, 2, 4],
214                [3, 4, 5],
215                [3, 5, 7],
216                [6, 7, 8],
217                [1, 4, 6],
218                [2, 5, 8],
219            ],
220        )),
221        optimal_config: vec![1, 0, 1, 0, 1, 0, 0],
222        optimal_value: serde_json::json!(true),
223    }]
224}
225
226#[cfg(test)]
227#[path = "../../unit_tests/models/set/exact_cover_by_3_sets.rs"]
228mod tests;
problemreductions/models/set/exact_cover_by_3_sets.rs

problemreductions/models/set/
exact_cover_by_3_sets.rs
