csp_solver/
ordering.rs

1//! Variable ordering heuristics.
2
3use crate::constraint::VarId;
4use crate::domain::Domain;
5use crate::variable::Variable;
6
7/// Variable ordering strategy for search.
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum Ordering {
10    /// Chronological: pick variables in the order they appear on the stack.
11    Chronological,
12    /// Fail-first (MRV): pick the variable with the smallest domain.
13    FailFirst,
14    /// Mrv: pick the variable minimizing `domain-size / Σ constraint-weights`.
15    /// The weights are frozen at 1.0 (no dom/wdeg bumping is wired to the
16    /// kernel), so this is a static heuristic; `Chs` shares the same scan with
17    /// dynamically evolving weights.
18    Mrv,
19    /// CHS (Conflict-History Search): same `dom / Σ weights` scan as `Mrv`,
20    /// but the weights are updated dynamically by an exponential recency-weighted
21    /// average on each conflict (see [`crate::solver::heuristic`]).
22    Chs,
23}
24
25/// Select the next unassigned variable from the stack according to the ordering heuristic.
26///
27/// Returns the index into `stack` of the chosen variable, or `None` if empty.
28pub fn select_variable<D: Domain>(
29    stack: &[VarId],
30    variables: &[Variable<D>],
31    ordering: Ordering,
32    constraint_weights: &[f64],
33    var_constraint_ids: &[Vec<usize>],
34) -> Option<usize> {
35    if stack.is_empty() {
36        return None;
37    }
38
39    match ordering {
40        Ordering::Chronological => Some(stack.len() - 1),
41
42        Ordering::FailFirst => {
43            let mut best_idx = 0;
44            let mut best_size = usize::MAX;
45            for (i, &var) in stack.iter().enumerate() {
46                let sz = variables[var as usize].domain.size();
47                if sz < best_size {
48                    best_size = sz;
49                    best_idx = i;
50                }
51            }
52            Some(best_idx)
53        }
54
55        // CHS and Mrv share the `dom / Σ weights` branching rule; they
56        // differ only in *how* `constraint_weights` evolves (static 1.0 for
57        // Mrv, ERWA-updated for CHS — see `solver::heuristic`).
58        Ordering::Mrv | Ordering::Chs => {
59            let mut best_idx = 0;
60            let mut best_score = f64::MAX;
61            for (i, &var) in stack.iter().enumerate() {
62                let dom_size = variables[var as usize].domain.size() as f64;
63                let wdeg: f64 = var_constraint_ids[var as usize]
64                    .iter()
65                    .map(|&cid| constraint_weights[cid])
66                    .sum();
67                let score = dom_size / wdeg.max(1e-9);
68                if score < best_score {
69                    best_score = score;
70                    best_idx = i;
71                }
72            }
73            Some(best_idx)
74        }
75    }
76}
csp_solver/ordering.rs

csp_solver/
ordering.rs
