csp_solver/
config.rs

1//! Solver configuration vocabulary and the [`Csp<D>`] problem container.
2//!
3//! The pruning / propagation / optimization enums, the [`SolveConfig`] bundle
4//! (+ its `Default`), the [`SolveStats`] counters, and the `Csp<D>` struct
5//! definition. The builder surface lives in [`crate::csp`]; the search
6//! dispatch in [`crate::csp::solve`].
7//!
8//! Tests: `tests/solver.rs` (config matrix across every pruning × ordering).
9
10use crate::cancel::CancelToken;
11use crate::constraint::ConstraintEnum;
12use crate::domain::Domain;
13use crate::ordering::Ordering;
14use crate::solver::adjacency::Adjacency;
15use crate::variable::Variable;
16
17/// Pruning strategy for backtracking search.
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum Pruning {
20    /// No pruning — pure backtracking.
21    None,
22    /// Forward checking: prune neighbors of the assigned variable.
23    ForwardChecking,
24    /// MAC: Maintaining Arc Consistency (AC-3 after each assignment).
25    Ac3,
26    /// Hybrid: forward checking + singleton propagation.
27    AcFc,
28}
29
30/// Propagation strategy for `propagate_with()`.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum PropagationStrategy {
33    /// Auto-select: AC-3 if finalize() was called, sweep otherwise.
34    Auto,
35    /// AC-3 worklist with adjacency graph. Requires finalize().
36    Ac3,
37    /// Fixed-point sweep over all constraints. No adjacency needed.
38    Sweep,
39}
40
41/// Optimization mode for the solver.
42#[derive(Debug, Clone, Copy, PartialEq, Eq)]
43pub enum OptimizationMode {
44    /// Find any feasible solution (existing behavior).
45    Feasibility,
46    /// Find the solution minimizing total cost (domain costs + soft penalties).
47    MinimizeCost,
48    /// Find the solution maximizing total cost.
49    MaximizeCost,
50}
51
52/// Solve configuration, isomorphic to Python's CSP constructor arguments.
53#[derive(Debug, Clone)]
54pub struct SolveConfig {
55    pub pruning: Pruning,
56    pub ordering: Ordering,
57    /// Cap on solutions returned. `1` is a satisfiability probe.
58    ///
59    /// On a problem with more than one solution, *which* first solution comes
60    /// back under `Pruning::Ac3` is trajectory-dependent — different
61    /// pruning/ordering combinations may return different valid members of the
62    /// solution set. Each is a genuine member (see `kernel-soundness-closure.md`
63    /// §7.2), but callers must not depend on the specific choice. Only
64    /// enumerate-all (`usize::MAX`) has a defined, pruning-invariant set.
65    pub max_solutions: usize,
66    /// Optimization mode. Defaults to `Feasibility` (pure constraint satisfaction).
67    pub optimization_mode: OptimizationMode,
68    /// Maximum number of search nodes (backtrack / branch-and-bound
69    /// recursions) before the solver aborts early and returns whatever
70    /// solutions it has found so far. `None` disables the budget.
71    ///
72    /// Defaults to `Some(1_000_000)` so an unbounded pathological
73    /// search cannot hang a caller. When the budget is hit,
74    /// [`SolveStats::budget_exceeded`] is set to `true` on the
75    /// returning `Csp::stats()`. Callers that care about optimality
76    /// should branch on this flag and either accept the best-so-far
77    /// solution or fall back to a trivial per-variable pick.
78    pub node_budget: Option<u64>,
79    /// Cooperative cancellation flag, checked at the same cadence as
80    /// `node_budget`. `None` (the default) means the search cannot be
81    /// cancelled externally. Set this to a [`CancelToken`] clone and keep
82    /// another clone on the calling side to request an early stop — e.g.
83    /// from Python, released via `Python::allow_threads`, when an
84    /// `asyncio.wait_for` timeout elapses. See [`SolveStats::cancelled`].
85    pub cancel: Option<CancelToken>,
86}
87
88impl Default for SolveConfig {
89    /// Ac3 + FailFirst (Pass-2 D6, ratified; ships in 0.2.0): the production
90    /// posture every measured surface converged on. Coordination-gated with
91    /// bbnf-lang's two live `finalize()+solve_optimized()` consumers via the
92    /// enforced-compile sync gate (`sync-csp-solver-vendor.sh --verify`).
93    fn default() -> Self {
94        Self {
95            pruning: Pruning::Ac3,
96            ordering: Ordering::FailFirst,
97            max_solutions: 1,
98            optimization_mode: OptimizationMode::Feasibility,
99            node_budget: Some(1_000_000),
100            cancel: None,
101        }
102    }
103}
104
105/// Solver statistics.
106#[derive(Debug, Clone, Default)]
107pub struct SolveStats {
108    pub backtracks: u64,
109    pub nodes_explored: u64,
110    pub propagations: u64,
111    /// Set to `true` when the last search hit its
112    /// [`SolveConfig::node_budget`] and aborted early.
113    /// Solutions returned alongside this flag are best-so-far, not
114    /// necessarily optimal.
115    pub budget_exceeded: bool,
116    /// Set to `true` when the last search was stopped early via
117    /// [`SolveConfig::cancel`] rather than hitting `node_budget`.
118    /// Distinct from `budget_exceeded`: this is an externally requested
119    /// stop, not a self-imposed cap.
120    pub cancelled: bool,
121}
122
123/// The main CSP solver struct.
124///
125/// Generic over the domain type `D`. Build a problem by adding variables and
126/// constraints, call `finalize()` to build the adjacency graph, then `solve()`.
127///
128/// The builder methods (`add_*`, `finalize`) live in [`crate::csp`]; the
129/// solve/propagate dispatch in [`crate::csp::solve`].
130pub struct Csp<D: Domain> {
131    pub variables: Vec<Variable<D>>,
132    pub(crate) constraints: Vec<ConstraintEnum<D>>,
133    pub(crate) adjacency: Option<Adjacency>,
134    pub(crate) stats: SolveStats,
135    /// Per-constraint weights for the Mrv weighted-degree scan.
136    pub(crate) constraint_weights: Vec<f64>,
137    /// For each variable, the indices of constraints involving it.
138    pub(crate) var_constraint_ids: Vec<Vec<usize>>,
139}
csp_solver/config.rs

csp_solver/
config.rs
