csp_solver/solver/
propagate.rs

1//! Forward checking and AC-FC hybrid propagation.
2
3use crate::adjacency::Adjacency;
4use crate::constraint::{ConstraintEnum, VarId};
5use crate::domain::Domain;
6use crate::variable::Variable;
7use crate::SolveStats;
8
9/// Forward checking using assign-check-unassign.
10///
11/// Reuses a value buffer across neighbors to avoid per-neighbor heap allocation.
12pub fn forward_check<D: Domain>(
13    var: VarId,
14    variables: &mut [Variable<D>],
15    constraints: &[ConstraintEnum<D>],
16    adjacency: &Adjacency,
17    assignment: &mut [Option<D::Value>],
18    stats: &mut SolveStats,
19    depth: usize,
20) -> bool
21where
22    D::Value: PartialEq,
23{
24    let mut val_buf: Vec<D::Value> = Vec::new();
25
26    for &neighbor in adjacency.neighbors_of_var(var) {
27        if assignment[neighbor as usize].is_some() {
28            continue;
29        }
30
31        // Reuse buffer: clear + extend avoids reallocation after first neighbor.
32        val_buf.clear();
33        val_buf.extend(variables[neighbor as usize].domain.iter());
34
35        for val in &val_buf {
36            assignment[neighbor as usize] = Some(val.clone());
37
38            let mut valid = true;
39            for &ci in adjacency.constraints_for(neighbor) {
40                let ci = ci as usize;
41                let scope = constraints[ci].scope();
42                if scope.iter().all(|&v| assignment[v as usize].is_some())
43                    && !constraints[ci].check(assignment)
44                {
45                    valid = false;
46                    break;
47                }
48            }
49
50            assignment[neighbor as usize] = None;
51
52            if !valid {
53                variables[neighbor as usize].prune(val, depth);
54                stats.propagations += 1;
55            }
56        }
57
58        if variables[neighbor as usize].domain.is_empty() {
59            return true;
60        }
61    }
62
63    false
64}
65
66/// AC-FC hybrid: forward check + singleton propagation.
67pub fn ac_fc<D: Domain>(
68    var: VarId,
69    variables: &mut [Variable<D>],
70    constraints: &[ConstraintEnum<D>],
71    adjacency: &Adjacency,
72    assignment: &mut [Option<D::Value>],
73    stats: &mut SolveStats,
74    depth: usize,
75) -> bool
76where
77    D::Value: PartialEq,
78{
79    if forward_check(var, variables, constraints, adjacency, assignment, stats, depth) {
80        return true;
81    }
82
83    let mut worklist: Vec<VarId> = Vec::new();
84    for &neighbor in adjacency.neighbors_of_var(var) {
85        if assignment[neighbor as usize].is_none()
86            && variables[neighbor as usize].domain.is_singleton()
87        {
88            worklist.push(neighbor);
89        }
90    }
91
92    let mut visited = vec![false; variables.len()];
93    visited[var as usize] = true;
94
95    while let Some(v) = worklist.pop() {
96        if visited[v as usize] {
97            continue;
98        }
99        visited[v as usize] = true;
100
101        let singleton_val = variables[v as usize].domain.singleton_value().unwrap();
102        assignment[v as usize] = Some(singleton_val);
103
104        if forward_check(v, variables, constraints, adjacency, assignment, stats, depth) {
105            assignment[v as usize] = None;
106            return true;
107        }
108
109        assignment[v as usize] = None;
110
111        for &neighbor in adjacency.neighbors_of_var(v) {
112            if assignment[neighbor as usize].is_none()
113                && !visited[neighbor as usize]
114                && variables[neighbor as usize].domain.is_singleton()
115            {
116                worklist.push(neighbor);
117            }
118        }
119    }
120
121    false
122}
csp_solver/solver/propagate.rs

csp_solver/solver/
propagate.rs
