csp_solver/constraint/
all_different_except.rs

1//! N-ary all-different constraint with a sentinel escape value.
2//!
3//! Parallel to [`AllDifferent`](super::all_different::AllDifferent) but permits
4//! arbitrarily many variables to share a single *sentinel* value — useful for
5//! modelling partial bipartite assignment, where a dedicated "unmatched" token
6//! may be selected by any number of sources simultaneously while every other
7//! (real) target must still be picked at most once.
8//!
9//! ```no_run
10//! use csp_solver::constraint::AllDifferentExcept;
11//! use csp_solver::domain::BitsetDomain;
12//! use csp_solver::Csp;
13//!
14//! // Four variables, each picking a target in 0..4. Value `0` is the
15//! // "unmatched" sentinel — any number of variables may land on it.
16//! let mut csp: Csp<BitsetDomain> = Csp::new();
17//! let vars = csp.add_variables(&BitsetDomain::range(4), 4);
18//! csp.add_constraint_enum(
19//!     csp_solver::constraint::ConstraintEnum::AllDifferentExcept(
20//!         AllDifferentExcept::new(vars, 0),
21//!     ),
22//! );
23//! csp.finalize();
24//! ```
25
26use crate::domain::Domain;
27use crate::variable::Variable;
28
29use super::traits::{Constraint, Revision, VarId};
30
31/// All-different over the scope, *except* that the configured `sentinel`
32/// value may be assigned to any number of variables.
33///
34/// Non-sentinel assignments must remain pairwise distinct.
35#[derive(Debug)]
36pub struct AllDifferentExcept<V: Clone + PartialEq + std::fmt::Debug> {
37    pub(crate) scope: Vec<VarId>,
38    pub(crate) sentinel: V,
39}
40
41impl<V: Clone + PartialEq + std::fmt::Debug> AllDifferentExcept<V> {
42    /// Create a new all-different-except constraint over `vars`, treating
43    /// `sentinel` as the escape value that may be reused without conflict.
44    pub fn new(vars: Vec<VarId>, sentinel: V) -> Self {
45        Self { scope: vars, sentinel }
46    }
47
48    pub(crate) fn check_impl(&self, assignment: &[Option<V>]) -> bool {
49        // Collect non-sentinel assigned values; sentinel assignments are
50        // elided entirely so they never participate in the pairwise test.
51        let assigned: Vec<&V> = self
52            .scope
53            .iter()
54            .filter_map(|&v| assignment[v as usize].as_ref())
55            .filter(|val| **val != self.sentinel)
56            .collect();
57        for i in 0..assigned.len() {
58            for j in (i + 1)..assigned.len() {
59                if assigned[i] == assigned[j] {
60                    return false;
61                }
62            }
63        }
64        true
65    }
66
67    /// Prune non-sentinel values from peer domains.
68    ///
69    /// For small scopes (< 4 variables), uses fast singleton removal:
70    /// a variable pinned to the sentinel does not forbid peers from
71    /// choosing the sentinel themselves, while non-sentinel singletons
72    /// behave exactly like [`AllDifferent`](super::all_different::AllDifferent).
73    ///
74    /// For larger scopes (≥ 4), delegates to Régin's GAC algorithm
75    /// ([`propagate_gac_alldiff_except`](crate::solver::gac_alldiff_except::propagate_gac_alldiff_except)),
76    /// which achieves generalized arc consistency by building a bipartite
77    /// matching graph over non-sentinel values and pruning values that
78    /// cannot participate in any maximum matching.
79    pub(crate) fn revise_impl<D>(&self, vars: &mut [Variable<D>], depth: usize) -> Revision
80    where
81        D: Domain<Value = V>,
82    {
83        // For larger scopes, GAC provides strictly stronger pruning than
84        // singleton removal — it detects Hall sets and matching failures
85        // that pairwise checks miss.
86        if self.scope.len() >= 4 {
87            return crate::solver::gac_alldiff_except::propagate_gac_alldiff_except(
88                &self.scope,
89                &self.sentinel,
90                vars,
91                depth,
92            );
93        }
94
95        // Small scope: singleton removal is fast and sufficient.
96        let mut changed = false;
97        let singletons: Vec<(VarId, D::Value)> = self
98            .scope
99            .iter()
100            .filter_map(|&v| vars[v as usize].domain.singleton_value().map(|val| (v, val)))
101            .filter(|(_, val)| *val != self.sentinel)
102            .collect();
103
104        for (sv, sval) in &singletons {
105            for &other in &self.scope {
106                if other == *sv { continue; }
107                if vars[other as usize].prune(sval, depth) { changed = true; }
108                if vars[other as usize].domain.is_empty() { return Revision::Unsatisfiable; }
109            }
110        }
111
112        if changed { Revision::Changed } else { Revision::Unchanged }
113    }
114}
115
116impl<D> Constraint<D> for AllDifferentExcept<D::Value>
117where
118    D: Domain,
119    D::Value: PartialEq,
120{
121    fn scope(&self) -> &[VarId] { &self.scope }
122    fn check(&self, assignment: &[Option<D::Value>]) -> bool { self.check_impl(assignment) }
123    fn revise(&self, vars: &mut [Variable<D>], depth: usize) -> Revision {
124        self.revise_impl(vars, depth)
125    }
126}
csp_solver/constraint/all_different_except.rs

csp_solver/constraint/
all_different_except.rs
