csp-solver 0.1.0

Generic constraint satisfaction problem solver with backtracking, AC-3 constraint propagation, and ordering heuristics.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

//! Binary not-equal constraint: `x != y`.

use crate::domain::Domain;
use crate::variable::Variable;

use super::traits::{Constraint, Revision, VarId};

#[derive(Debug)]
pub struct NotEqual {
    pub(crate) scope: [VarId; 2],
}

impl NotEqual {
    pub fn new(x: VarId, y: VarId) -> Self {
        Self { scope: [x, y] }
    }

    pub(crate) fn check_impl<V: PartialEq>(&self, assignment: &[Option<V>]) -> bool {
        let xi = self.scope[0] as usize;
        let xj = self.scope[1] as usize;
        match (&assignment[xi], &assignment[xj]) {
            (Some(a), Some(b)) => a != b,
            _ => true,
        }
    }

    pub(crate) fn revise_impl<D: Domain>(&self, vars: &mut [Variable<D>], depth: usize) -> Revision
    where
        D::Value: PartialEq,
    {
        let xi = self.scope[0] as usize;
        let xj = self.scope[1] as usize;
        let mut changed = false;

        if let Some(v) = vars[xi].domain.singleton_value()
            && vars[xj].prune(&v, depth)
        {
            changed = true;
        }
        if let Some(v) = vars[xj].domain.singleton_value()
            && vars[xi].prune(&v, depth)
        {
            changed = true;
        }

        if vars[xi].domain.is_empty() || vars[xj].domain.is_empty() {
            return Revision::Unsatisfiable;
        }

        if changed { Revision::Changed } else { Revision::Unchanged }
    }
}

impl<D: Domain> Constraint<D> for NotEqual
where
    D::Value: PartialEq,
{
    fn scope(&self) -> &[VarId] { &self.scope }
    fn check(&self, assignment: &[Option<D::Value>]) -> bool { self.check_impl(assignment) }
    fn revise(&self, vars: &mut [Variable<D>], depth: usize) -> Revision { self.revise_impl(vars, depth) }
}