csp_solver/
csp.rs

1//! CSP builder surface — variable / constraint construction and `finalize()`.
2//!
3//! The [`Csp<D>`] container and its configuration vocabulary are defined in
4//! [`crate::config`]; the solve / propagate dispatch in [`solve`].
5//!
6//! Tests: `tests/solver.rs` (builder + solve correctness, every `add_*` path).
7
8pub mod solve;
9
10use crate::config::{Csp, SolveStats};
11use crate::constraint::{
12    self, AllDifferent, CageProduct, CageSum, Constraint, ConstraintEnum, NotEqual, VarId,
13};
14use crate::domain::Domain;
15use crate::domain::bitset::BitsetDomain;
16use crate::solver::adjacency::Adjacency;
17use crate::variable::Variable;
18
19impl<D: Domain> Csp<D> {
20    /// Create a new empty CSP.
21    pub fn new() -> Self {
22        Self {
23            variables: Vec::new(),
24            constraints: Vec::new(),
25            adjacency: None,
26            stats: SolveStats::default(),
27            constraint_weights: Vec::new(),
28            var_constraint_ids: Vec::new(),
29        }
30    }
31
32    /// Add a variable with the given domain. Returns its VarId.
33    pub fn add_variable(&mut self, domain: D) -> VarId {
34        let id = self.variables.len() as VarId;
35        self.variables.push(Variable::new(domain));
36        id
37    }
38
39    /// Add multiple variables sharing the same domain. Returns their VarIds.
40    pub fn add_variables(&mut self, domain: &D, count: usize) -> Vec<VarId> {
41        (0..count)
42            .map(|_| self.add_variable(domain.clone()))
43            .collect()
44    }
45
46    /// Add a custom constraint (wrapped in the `Custom` enum variant).
47    pub fn add_constraint(&mut self, c: impl Constraint<D> + 'static) {
48        self.constraints.push(ConstraintEnum::Custom(Box::new(c)));
49    }
50
51    /// Add a pre-typed constraint enum directly (avoids boxing for built-in types).
52    pub fn add_constraint_enum(&mut self, c: ConstraintEnum<D>) {
53        self.constraints.push(c);
54    }
55
56    /// Add a not-equal constraint (devirtualized fast path).
57    pub fn add_not_equal(&mut self, x: VarId, y: VarId) {
58        self.constraints
59            .push(ConstraintEnum::NotEqual(NotEqual::new(x, y)));
60    }
61
62    /// Add an all-different constraint (devirtualized fast path).
63    pub fn add_all_different(&mut self, vars: Vec<VarId>) {
64        self.constraints
65            .push(ConstraintEnum::AllDifferent(AllDifferent::new(vars)));
66    }
67
68    /// Fix a variable to a specific value.
69    pub fn add_equals(&mut self, var: VarId, value: D::Value)
70    where
71        D: 'static,
72        D::Value: Send + Sync,
73    {
74        self.add_constraint(constraint::LambdaConstraint::new(
75            vec![var],
76            move |assignment| match &assignment[var as usize] {
77                Some(v) => *v == value,
78                None => true,
79            },
80            format!("equals({var})"),
81        ));
82    }
83
84    /// Constrain x < y (for Ord-comparable values).
85    pub fn add_less_than(&mut self, x: VarId, y: VarId)
86    where
87        D: 'static,
88        D::Value: PartialOrd + Send + Sync,
89    {
90        self.add_constraint(constraint::LambdaConstraint::new(
91            vec![x, y],
92            move |assignment| match (&assignment[x as usize], &assignment[y as usize]) {
93                (Some(a), Some(b)) => a < b,
94                _ => true,
95            },
96            format!("less_than({x},{y})"),
97        ));
98    }
99
100    /// Constrain x > y (for Ord-comparable values).
101    pub fn add_greater_than(&mut self, x: VarId, y: VarId)
102    where
103        D: 'static,
104        D::Value: PartialOrd + Send + Sync,
105    {
106        self.add_constraint(constraint::LambdaConstraint::new(
107            vec![x, y],
108            move |assignment| match (&assignment[x as usize], &assignment[y as usize]) {
109                (Some(a), Some(b)) => a > b,
110                _ => true,
111            },
112            format!("greater_than({x},{y})"),
113        ));
114    }
115
116    /// Build the adjacency graph. Must be called after all variables and
117    /// constraints have been added, before calling `solve()`.
118    pub fn finalize(&mut self)
119    where
120        D::Value: PartialEq + 'static,
121    {
122        let num_vars = self.variables.len();
123        self.adjacency = Some(Adjacency::build(num_vars, &self.constraints));
124
125        self.constraint_weights = vec![1.0; self.constraints.len()];
126        self.var_constraint_ids = vec![Vec::new(); num_vars];
127        for (ci, c) in self.constraints.iter().enumerate() {
128            for &v in c.scope() {
129                self.var_constraint_ids[v as usize].push(ci);
130            }
131        }
132    }
133}
134
135/// Cage-constraint builders — the n-ary arithmetic family (Killer / KenKen).
136///
137/// Homed on the concrete [`BitsetDomain`] (values are `u32`): cages are integer
138/// arithmetic over the production domain, not a general-domain notion, so they
139/// live here rather than on the generic `impl<D: Domain>` above. Both register
140/// as devirtualized [`ConstraintEnum`] variants, so `revise` dispatches to the
141/// cage's bounds-propagation `revise_impl` (clearing the n-ary-lambda wall) —
142/// not the default `revise`'s `_ => Unchanged`.
143impl Csp<BitsetDomain> {
144    /// Add an n-ary cage-sum: the cells in `scope` must sum to `target`.
145    /// Serves Killer cages and `+` KenKen cages.
146    pub fn add_cage_sum(&mut self, scope: Vec<VarId>, target: u32) {
147        self.constraints
148            .push(ConstraintEnum::CageSum(CageSum::new(scope, target)));
149    }
150
151    /// Add an n-ary cage-product: the cells in `scope` must multiply to
152    /// `target`. Serves `×` KenKen cages.
153    pub fn add_cage_product(&mut self, scope: Vec<VarId>, target: u32) {
154        self.constraints
155            .push(ConstraintEnum::CageProduct(CageProduct::new(scope, target)));
156    }
157}
csp_solver/csp.rs

csp_solver/
csp.rs
