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 the denominator is a static per-variable weighted degree,
17    /// precomputed once by [`precompute_var_wdeg`] rather than re-summed at every
18    /// node.
19    Mrv,
20}
21
22/// Precompute each variable's frozen weighted degree — Σ of its incident
23/// constraint weights — the denominator of the [`Ordering::Mrv`] score.
24///
25/// The weights are frozen at 1.0 (no dom/wdeg bumping is wired), so this sum is
26/// invariant across the entire search; computing it once here replaces the
27/// per-node re-sum the [`Ordering::Mrv`] branch used to run for every stacked
28/// variable at every node (P2-solver-backend MRV). Returns an **empty** vec for
29/// the orderings that never consult wdeg (`Chronological` / `FailFirst` pay
30/// nothing — not one add). The sum walks `var_constraint_ids[v]` in the same
31/// order the per-node loop did, so each `var_wdeg[v]` is bit-identical to the
32/// value the old code produced and the Mrv trajectory is unchanged.
33///
34/// **Frozen-weight invariant.** If a later tranche wires dom/wdeg bumping (the
35/// reason the kernel still threads `constraint_weights` as `&mut`), it must
36/// recompute — or incrementally patch — the affected `var_wdeg` entries on each
37/// weight change, or the score denominator goes stale.
38pub fn precompute_var_wdeg(
39    ordering: Ordering,
40    constraint_weights: &[f64],
41    var_constraint_ids: &[Vec<usize>],
42) -> Vec<f64> {
43    if ordering != Ordering::Mrv {
44        return Vec::new();
45    }
46    var_constraint_ids
47        .iter()
48        .map(|cids| cids.iter().map(|&cid| constraint_weights[cid]).sum())
49        .collect()
50}
51
52/// Select the next unassigned variable from the stack according to the ordering heuristic.
53///
54/// Returns the index into `stack` of the chosen variable, or `None` if empty.
55/// `var_wdeg` is the [`precompute_var_wdeg`] output — consulted only by
56/// [`Ordering::Mrv`], and empty for the orderings that ignore it.
57pub fn select_variable<D: Domain>(
58    stack: &[VarId],
59    variables: &[Variable<D>],
60    ordering: Ordering,
61    var_wdeg: &[f64],
62) -> Option<usize> {
63    if stack.is_empty() {
64        return None;
65    }
66
67    match ordering {
68        Ordering::Chronological => Some(stack.len() - 1),
69
70        Ordering::FailFirst => {
71            let mut best_idx = 0;
72            let mut best_size = usize::MAX;
73            for (i, &var) in stack.iter().enumerate() {
74                let sz = variables[var as usize].domain.size();
75                if sz < best_size {
76                    best_size = sz;
77                    best_idx = i;
78                }
79            }
80            Some(best_idx)
81        }
82
83        // Mrv branches on `dom / wdeg`; `wdeg` is the precomputed frozen sum.
84        Ordering::Mrv => {
85            let mut best_idx = 0;
86            let mut best_score = f64::MAX;
87            for (i, &var) in stack.iter().enumerate() {
88                let dom_size = variables[var as usize].domain.size() as f64;
89                let wdeg = var_wdeg[var as usize];
90                let score = dom_size / wdeg.max(1e-9);
91                if score < best_score {
92                    best_score = score;
93                    best_idx = i;
94                }
95            }
96            Some(best_idx)
97        }
98    }
99}
csp_solver/ordering.rs

csp_solver/
ordering.rs
