csp_solver/solver/
mod.rs

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

csp_solver/solver/
mod.rs
