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

csp_solver/
ordering.rs
