csp_solver/constraint/
all_different.rs

1//! N-ary all-different constraint.
2
3use crate::domain::Domain;
4use crate::variable::Variable;
5
6use super::traits::{Constraint, Revision, VarId};
7
8#[derive(Debug)]
9pub struct AllDifferent {
10    pub(crate) scope: Vec<VarId>,
11}
12
13impl AllDifferent {
14    pub fn new(vars: Vec<VarId>) -> Self {
15        Self { scope: vars }
16    }
17
18    pub(crate) fn check_impl<V: PartialEq>(&self, assignment: &[Option<V>]) -> bool {
19        let assigned: Vec<&V> = self
20            .scope
21            .iter()
22            .filter_map(|&v| assignment[v as usize].as_ref())
23            .collect();
24        for i in 0..assigned.len() {
25            for j in (i + 1)..assigned.len() {
26                if assigned[i] == assigned[j] {
27                    return false;
28                }
29            }
30        }
31        true
32    }
33
34    /// Singleton removal: prune assigned values from peers.
35    ///
36    /// GAC (Régin's algorithm) is available separately via
37    /// `solver::gac_alldiff::propagate_gac_alldiff` for one-shot use.
38    pub(crate) fn revise_impl<D: Domain>(&self, vars: &mut [Variable<D>], depth: usize) -> Revision
39    where
40        D::Value: PartialEq,
41    {
42        let mut changed = false;
43        let singletons: Vec<(VarId, D::Value)> = self
44            .scope
45            .iter()
46            .filter_map(|&v| vars[v as usize].domain.singleton_value().map(|val| (v, val)))
47            .collect();
48
49        for (sv, sval) in &singletons {
50            for &other in &self.scope {
51                if other == *sv { continue; }
52                if vars[other as usize].prune(sval, depth) { changed = true; }
53                if vars[other as usize].domain.is_empty() { return Revision::Unsatisfiable; }
54            }
55        }
56
57        if changed { Revision::Changed } else { Revision::Unchanged }
58    }
59}
60
61impl<D: Domain> Constraint<D> for AllDifferent
62where
63    D::Value: PartialEq,
64{
65    fn scope(&self) -> &[VarId] { &self.scope }
66    fn check(&self, assignment: &[Option<D::Value>]) -> bool { self.check_impl(assignment) }
67    fn revise(&self, vars: &mut [Variable<D>], depth: usize) -> Revision { self.revise_impl(vars, depth) }
68}
csp_solver/constraint/all_different.rs

csp_solver/constraint/
all_different.rs
