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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

//! ConstraintEnum: devirtualized dispatch for hot-path constraints.

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

use super::all_different::AllDifferent;
use super::all_different_except::AllDifferentExcept;
use super::lambda::LambdaConstraint;
use super::not_equal::NotEqual;
use super::soft::SoftLambdaConstraint;
use super::traits::{Constraint, Revision, VarId};

/// Enum-dispatched constraint storage. Avoids vtable indirection for built-in types.
pub enum ConstraintEnum<D: Domain> {
    NotEqual(NotEqual),
    AllDifferent(AllDifferent),
    AllDifferentExcept(AllDifferentExcept<D::Value>),
    Lambda(LambdaConstraint<D>),
    Soft(SoftLambdaConstraint<D>),
    Custom(Box<dyn Constraint<D>>),
}

impl<D: Domain> std::fmt::Debug for ConstraintEnum<D> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::NotEqual(c) => c.fmt(f),
            Self::AllDifferent(c) => c.fmt(f),
            Self::AllDifferentExcept(c) => c.fmt(f),
            Self::Lambda(c) => c.fmt(f),
            Self::Soft(c) => c.fmt(f),
            Self::Custom(c) => c.fmt(f),
        }
    }
}

impl<D: Domain> ConstraintEnum<D>
where
    D::Value: PartialEq,
{
    #[inline]
    pub fn scope(&self) -> &[VarId] {
        match self {
            Self::NotEqual(c) => &c.scope,
            Self::AllDifferent(c) => &c.scope,
            Self::AllDifferentExcept(c) => &c.scope,
            Self::Lambda(c) => &c.scope,
            Self::Soft(c) => &c.scope,
            Self::Custom(c) => c.scope(),
        }
    }

    #[inline]
    pub fn check(&self, assignment: &[Option<D::Value>]) -> bool {
        match self {
            Self::NotEqual(c) => c.check_impl(assignment),
            Self::AllDifferent(c) => c.check_impl(assignment),
            Self::AllDifferentExcept(c) => c.check_impl(assignment),
            Self::Lambda(c) => (c.checker)(assignment),
            Self::Soft(_) => true, // soft constraints never reject
            Self::Custom(c) => c.check(assignment),
        }
    }

    #[inline]
    pub fn revise(&self, vars: &mut [Variable<D>], depth: usize) -> Revision {
        match self {
            Self::NotEqual(c) => c.revise_impl(vars, depth),
            Self::AllDifferent(c) => c.revise_impl(vars, depth),
            Self::AllDifferentExcept(c) => c.revise_impl(vars, depth),
            Self::Lambda(c) => <LambdaConstraint<D> as Constraint<D>>::revise(c, vars, depth),
            Self::Soft(_) => Revision::Unchanged, // soft constraints don't prune
            Self::Custom(c) => c.revise(vars, depth),
        }
    }

    /// For soft constraints, compute the penalty if the underlying predicate
    /// is violated. Returns 0.0 for hard constraints or satisfied soft constraints.
    #[inline]
    pub fn soft_penalty(&self, assignment: &[Option<D::Value>]) -> f64 {
        match self {
            Self::Soft(c) => {
                if c.is_satisfied(assignment) {
                    0.0
                } else {
                    c.penalty
                }
            }
            _ => 0.0,
        }
    }
}