csp_solver/solver/
propagate.rs

1//! Forward checking and AC-FC hybrid propagation.
2//!
3//! On a domain wipe-out these return `Some(constraint_id)` naming the
4//! constraint that emptied a domain — the "blame" signal consumed by
5//! conflict-history weighting (CHS / dom-wdeg). `None` means propagation
6//! completed without a wipe-out. Every pruned neighbor is still recorded on
7//! `trail` for O(touched) undo (the kernel's touched-VarId trail).
8
9use crate::SolveStats;
10use crate::adjacency::Adjacency;
11use crate::constraint::{ConstraintEnum, VarId};
12use crate::domain::Domain;
13use crate::solver::Trail;
14use crate::variable::Variable;
15
16/// Outcome of a propagation step: `Some(ci)` on wipe-out (constraint `ci` is
17/// to blame), `None` on success.
18pub type PropResult = Option<usize>;
19
20/// Forward checking using assign-check-unassign.
21///
22/// Reuses a value buffer across neighbors to avoid per-neighbor heap allocation.
23/// Every pruned neighbor is recorded on `trail` so backtrack undoes only what
24/// was touched. Returns the blame signal (see module docs).
25#[allow(clippy::too_many_arguments)]
26pub(crate) fn forward_check<D: Domain>(
27    var: VarId,
28    variables: &mut [Variable<D>],
29    constraints: &[ConstraintEnum<D>],
30    adjacency: &Adjacency,
31    assignment: &mut [Option<D::Value>],
32    stats: &mut SolveStats,
33    trail: &mut Trail,
34    depth: usize,
35) -> PropResult
36where
37    D::Value: PartialEq,
38{
39    let mut val_buf: Vec<D::Value> = Vec::new();
40
41    for &neighbor in adjacency.neighbors_of_var(var) {
42        if assignment[neighbor as usize].is_some() {
43            continue;
44        }
45
46        // Reuse buffer: clear + extend avoids reallocation after first neighbor.
47        val_buf.clear();
48        val_buf.extend(variables[neighbor as usize].domain.iter());
49
50        // Blame the constraint that pruned the value which emptied the domain.
51        let mut culprit: usize = 0;
52
53        for val in &val_buf {
54            assignment[neighbor as usize] = Some(val.clone());
55
56            let mut failing: Option<usize> = None;
57            for &ci in adjacency.constraints_for(neighbor) {
58                let ci = ci as usize;
59                let scope = constraints[ci].scope();
60                if scope.iter().all(|&v| assignment[v as usize].is_some())
61                    && !constraints[ci].check(assignment)
62                {
63                    failing = Some(ci);
64                    break;
65                }
66            }
67
68            assignment[neighbor as usize] = None;
69
70            if let Some(ci) = failing {
71                if variables[neighbor as usize].prune(val, depth) {
72                    trail.push(neighbor);
73                }
74                culprit = ci;
75                stats.propagations += 1;
76            }
77        }
78
79        if variables[neighbor as usize].domain.is_empty() {
80            return Some(culprit);
81        }
82    }
83
84    None
85}
86
87/// AC-FC hybrid: forward check + singleton propagation.
88#[allow(clippy::too_many_arguments)]
89pub(crate) fn ac_fc<D: Domain>(
90    var: VarId,
91    variables: &mut [Variable<D>],
92    constraints: &[ConstraintEnum<D>],
93    adjacency: &Adjacency,
94    assignment: &mut [Option<D::Value>],
95    stats: &mut SolveStats,
96    trail: &mut Trail,
97    depth: usize,
98) -> PropResult
99where
100    D::Value: PartialEq,
101{
102    if let Some(ci) = forward_check(
103        var,
104        variables,
105        constraints,
106        adjacency,
107        assignment,
108        stats,
109        trail,
110        depth,
111    ) {
112        return Some(ci);
113    }
114
115    let mut worklist: Vec<VarId> = Vec::new();
116    for &neighbor in adjacency.neighbors_of_var(var) {
117        if assignment[neighbor as usize].is_none()
118            && variables[neighbor as usize].domain.is_singleton()
119        {
120            worklist.push(neighbor);
121        }
122    }
123
124    let mut visited = vec![false; variables.len()];
125    visited[var as usize] = true;
126
127    while let Some(v) = worklist.pop() {
128        if visited[v as usize] {
129            continue;
130        }
131        visited[v as usize] = true;
132
133        let singleton_val = variables[v as usize].domain.singleton_value().unwrap();
134        assignment[v as usize] = Some(singleton_val);
135
136        if let Some(ci) = forward_check(
137            v,
138            variables,
139            constraints,
140            adjacency,
141            assignment,
142            stats,
143            trail,
144            depth,
145        ) {
146            assignment[v as usize] = None;
147            return Some(ci);
148        }
149
150        assignment[v as usize] = None;
151
152        for &neighbor in adjacency.neighbors_of_var(v) {
153            if assignment[neighbor as usize].is_none()
154                && !visited[neighbor as usize]
155                && variables[neighbor as usize].domain.is_singleton()
156            {
157                worklist.push(neighbor);
158            }
159        }
160    }
161
162    None
163}
csp_solver/solver/propagate.rs

csp_solver/solver/
propagate.rs
