csp_solver/
solver.rs

1//! Solver dispatch: AC-3 propagation, forward checking, and the unified
2//! monomorphized search kernel.
3
4pub mod ac3;
5pub(crate) mod adjacency;
6pub mod gac;
7pub mod monotonic;
8pub mod optimize;
9pub mod propagate;
10pub mod search;
11
12use crate::constraint::VarId;
13use crate::domain::Domain;
14use crate::variable::Variable;
15
16/// Solution type: a vector of values indexed by variable ID.
17pub type Solution<D> = Vec<<D as Domain>::Value>;
18
19/// Global undo trail of *touched* variables, owned by the search.
20///
21/// Replaces the per-`Variable` `pruned` restore-sweep: on backtrack the old
22/// search re-probed **every** variable (`for v in variables { v.restore(depth) }`,
23/// O(num_vars) per node). Here every prune records the affected `VarId`, so undo
24/// visits only the variables actually touched at that depth — O(removed).
25///
26/// The trail records *only* which variable changed; each `Variable` keeps its
27/// own depth-keyed `pruned` log, so restore semantics are unchanged. Double
28/// recording a variable is harmless: the first `restore(depth)` pops all of that
29/// depth's entries, later repeats are O(1) no-ops.
30#[derive(Default)]
31pub(crate) struct Trail {
32    touched: Vec<VarId>,
33}
34
35impl Trail {
36    /// Snapshot the trail length. Undo restores back to this checkpoint.
37    #[inline]
38    pub(crate) fn checkpoint(&self) -> usize {
39        self.touched.len()
40    }
41
42    /// Record that `var` was touched (a value pruned) at the current depth.
43    #[inline]
44    pub(crate) fn push(&mut self, var: VarId) {
45        self.touched.push(var);
46    }
47
48    /// Restore every variable touched since `mark`, undoing prunes at `depth`.
49    #[inline]
50    pub(crate) fn undo_to<D: Domain>(
51        &mut self,
52        mark: usize,
53        depth: usize,
54        variables: &mut [Variable<D>],
55    ) {
56        while self.touched.len() > mark {
57            let var = self.touched.pop().unwrap();
58            variables[var as usize].restore(depth);
59        }
60    }
61}
csp_solver/solver.rs

csp_solver/
solver.rs
