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

csp_solver/solver/
propagate.rs
