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::adjacency::Adjacency;
11use crate::cancel::CancelToken;
12use crate::constraint::ConstraintEnum;
13use crate::domain::Domain;
14use crate::ordering::Ordering;
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    pub max_solutions: usize,
58    /// Enable Luby restarts with phase saving and (if `Ordering::Chs`) dynamic
59    /// conflict-history weighting. Opt-in; production sudoku stays `Ac3 + Mrv`.
60    /// The restart *driver* is not yet wired onto the unified kernel (see the
61    /// pass-3 composition report — chs backtrack.rs re-authoring is deferred);
62    /// today this flag is accepted but inert.
63    pub restarts: bool,
64    /// Optimization mode. Defaults to `Feasibility` (pure constraint satisfaction).
65    pub optimization_mode: OptimizationMode,
66    /// Maximum number of search nodes (backtrack / branch-and-bound
67    /// recursions) before the solver aborts early and returns whatever
68    /// solutions it has found so far. `None` disables the budget.
69    ///
70    /// Defaults to `Some(1_000_000)` so an unbounded pathological
71    /// search cannot hang a caller. When the budget is hit,
72    /// [`SolveStats::budget_exceeded`] is set to `true` on the
73    /// returning `Csp::stats()`. Callers that care about optimality
74    /// should branch on this flag and either accept the best-so-far
75    /// solution or fall back to a trivial per-variable pick.
76    pub node_budget: Option<u64>,
77    /// Cooperative cancellation flag, checked at the same cadence as
78    /// `node_budget`. `None` (the default) means the search cannot be
79    /// cancelled externally. Set this to a [`CancelToken`] clone and keep
80    /// another clone on the calling side to request an early stop — e.g.
81    /// from Python, released via `Python::allow_threads`, when an
82    /// `asyncio.wait_for` timeout elapses. See [`SolveStats::cancelled`].
83    pub cancel: Option<CancelToken>,
84}
85
86impl Default for SolveConfig {
87    /// Ac3 + FailFirst (Pass-2 D6, ratified; ships in 0.2.0): the production
88    /// posture every measured surface converged on. Coordination-gated with
89    /// bbnf-lang's two live `finalize()+solve_optimized()` consumers via the
90    /// enforced-compile sync gate (`sync-csp-solver-vendor.sh --verify`).
91    fn default() -> Self {
92        Self {
93            pruning: Pruning::Ac3,
94            ordering: Ordering::FailFirst,
95            max_solutions: 1,
96            restarts: false,
97            optimization_mode: OptimizationMode::Feasibility,
98            node_budget: Some(1_000_000),
99            cancel: None,
100        }
101    }
102}
103
104/// Solver statistics.
105#[derive(Debug, Clone, Default)]
106pub struct SolveStats {
107    pub backtracks: u64,
108    pub nodes_explored: u64,
109    pub propagations: u64,
110    /// Set to `true` when the last search hit its
111    /// [`SolveConfig::node_budget`] and aborted early.
112    /// Solutions returned alongside this flag are best-so-far, not
113    /// necessarily optimal.
114    pub budget_exceeded: bool,
115    /// Set to `true` when the last search was stopped early via
116    /// [`SolveConfig::cancel`] rather than hitting `node_budget`.
117    /// Distinct from `budget_exceeded`: this is an externally requested
118    /// stop, not a self-imposed cap.
119    pub cancelled: bool,
120}
121
122/// The main CSP solver struct.
123///
124/// Generic over the domain type `D`. Build a problem by adding variables and
125/// constraints, call `finalize()` to build the adjacency graph, then `solve()`.
126///
127/// The builder methods (`add_*`, `finalize`) live in [`crate::csp`]; the
128/// solve/propagate dispatch in [`crate::csp::solve`].
129pub struct Csp<D: Domain> {
130    pub variables: Vec<Variable<D>>,
131    pub(crate) constraints: Vec<ConstraintEnum<D>>,
132    pub(crate) adjacency: Option<Adjacency>,
133    pub(crate) stats: SolveStats,
134    /// Per-constraint weights for the Mrv / Chs weighted-degree scan.
135    pub(crate) constraint_weights: Vec<f64>,
136    /// For each variable, the indices of constraints involving it.
137    pub(crate) var_constraint_ids: Vec<Vec<usize>>,
138}
csp_solver/config.rs

csp_solver/
config.rs
