csp_solver/constraint/
traits.rs

1//! Core constraint trait and supporting types.
2
3use std::fmt::Debug;
4
5use crate::domain::Domain;
6use crate::variable::Variable;
7
8/// Unique variable identifier (index into the variable array).
9pub type VarId = u32;
10
11/// Result of running `revise` on a constraint.
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum Revision {
14    Unchanged,
15    Changed,
16    Unsatisfiable,
17}
18
19/// A constraint over one or more CSP variables.
20pub trait Constraint<D: Domain>: Debug {
21    /// The variables this constraint involves (its "scope").
22    fn scope(&self) -> &[VarId];
23
24    /// Check whether a full or partial assignment satisfies this constraint.
25    fn check(&self, assignment: &[Option<D::Value>]) -> bool;
26
27    /// AC-3 style revision: prune unsupported values from domains.
28    fn revise(&self, vars: &mut [Variable<D>], depth: usize) -> Revision {
29        let scope = self.scope();
30        if scope.len() != 2 {
31            return Revision::Unchanged;
32        }
33
34        let xi = scope[0] as usize;
35        let xj = scope[1] as usize;
36        let mut changed = false;
37
38        let mut assignment: Vec<Option<D::Value>> = vec![None; vars.len()];
39
40        let vals_i = vars[xi].domain.values();
41        let vals_j = vars[xj].domain.values();
42
43        for vi in &vals_i {
44            let mut supported = false;
45            assignment[xi] = Some(vi.clone());
46            for vj in &vals_j {
47                assignment[xj] = Some(vj.clone());
48                if self.check(&assignment) {
49                    supported = true;
50                    break;
51                }
52            }
53            if !supported {
54                vars[xi].prune(vi, depth);
55                changed = true;
56            }
57        }
58        assignment[xi] = None;
59        assignment[xj] = None;
60
61        if vars[xi].domain.is_empty() {
62            return Revision::Unsatisfiable;
63        }
64
65        let vals_j = vars[xj].domain.values();
66        let vals_i = vars[xi].domain.values();
67
68        for vj in &vals_j {
69            let mut supported = false;
70            assignment[xj] = Some(vj.clone());
71            for vi in &vals_i {
72                assignment[xi] = Some(vi.clone());
73                if self.check(&assignment) {
74                    supported = true;
75                    break;
76                }
77            }
78            if !supported {
79                vars[xj].prune(vj, depth);
80                changed = true;
81            }
82        }
83
84        if vars[xj].domain.is_empty() {
85            return Revision::Unsatisfiable;
86        }
87
88        if changed { Revision::Changed } else { Revision::Unchanged }
89    }
90}
91
92/// A constraint with a penalty for violation.
93///
94/// Hard constraints prune domains; soft constraints contribute cost to the
95/// objective when violated. During optimization, the solver accumulates
96/// penalties from violated soft constraints alongside domain costs.
97pub trait SoftConstraint<D: Domain>: Constraint<D> {
98    /// Penalty added to the objective when this constraint is violated.
99    fn penalty(&self) -> f64;
100}
csp_solver/constraint/traits.rs

csp_solver/constraint/
traits.rs
