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.
17    Mrv,
18}
19
20/// Select the next unassigned variable from the stack according to the ordering heuristic.
21///
22/// Returns the index into `stack` of the chosen variable, or `None` if empty.
23pub fn select_variable<D: Domain>(
24    stack: &[VarId],
25    variables: &[Variable<D>],
26    ordering: Ordering,
27    constraint_weights: &[f64],
28    var_constraint_ids: &[Vec<usize>],
29) -> Option<usize> {
30    if stack.is_empty() {
31        return None;
32    }
33
34    match ordering {
35        Ordering::Chronological => Some(stack.len() - 1),
36
37        Ordering::FailFirst => {
38            let mut best_idx = 0;
39            let mut best_size = usize::MAX;
40            for (i, &var) in stack.iter().enumerate() {
41                let sz = variables[var as usize].domain.size();
42                if sz < best_size {
43                    best_size = sz;
44                    best_idx = i;
45                }
46            }
47            Some(best_idx)
48        }
49
50        // Mrv branches on `dom / Σ weights`; the weights are frozen at 1.0.
51        Ordering::Mrv => {
52            let mut best_idx = 0;
53            let mut best_score = f64::MAX;
54            for (i, &var) in stack.iter().enumerate() {
55                let dom_size = variables[var as usize].domain.size() as f64;
56                let wdeg: f64 = var_constraint_ids[var as usize]
57                    .iter()
58                    .map(|&cid| constraint_weights[cid])
59                    .sum();
60                let score = dom_size / wdeg.max(1e-9);
61                if score < best_score {
62                    best_score = score;
63                    best_idx = i;
64                }
65            }
66            Some(best_idx)
67        }
68    }
69}
csp_solver/ordering.rs

csp_solver/
ordering.rs
