csp-solver 0.1.0

Generic constraint satisfaction problem solver with backtracking, AC-3 constraint propagation, and ordering heuristics.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

//! CSP variable with domain tracking and pruned-value undo log.

use crate::domain::Domain;

/// A CSP variable holding its current domain and an undo log for backtracking.
#[derive(Debug, Clone)]
pub struct Variable<D: Domain> {
    /// Current (working) domain -- mutated during search.
    pub domain: D,
    /// Original domain -- used for full reset.
    original_domain: D,
    /// Undo log: `(depth, removed_value)` pairs. During backtracking, all entries
    /// at the given depth are restored into the domain.
    pruned: Vec<(usize, D::Value)>,
}

impl<D: Domain> Variable<D> {
    /// Create a new variable with the given initial domain.
    pub fn new(domain: D) -> Self {
        Self {
            original_domain: domain.clone(),
            domain,
            pruned: Vec::new(),
        }
    }

    /// Record that `val` was pruned at `depth`, and remove it from the domain.
    /// Returns `true` if the value was actually present and removed.
    pub fn prune(&mut self, val: &D::Value, depth: usize) -> bool {
        if self.domain.remove(val) {
            self.pruned.push((depth, val.clone()));
            true
        } else {
            false
        }
    }

    /// Restore all values pruned at the given `depth`.
    pub fn restore(&mut self, depth: usize) {
        while let Some(&(d, _)) = self.pruned.last() {
            if d == depth {
                let (_, val) = self.pruned.pop().unwrap();
                self.domain.add(&val);
            } else {
                break;
            }
        }
    }

    /// Reset to the original domain, clearing the undo log.
    pub fn reset(&mut self) {
        self.domain = self.original_domain.clone();
        self.pruned.clear();
    }

    /// Replace the current domain entirely (used during initial propagation).
    pub fn set_domain(&mut self, domain: D) {
        self.domain = domain;
    }

    /// Restrict domain to a single value, recording all other removals at `depth`.
    /// This is the fast path for backtracking assignment — avoids collecting
    /// domain values into a Vec just to prune them.
    pub fn restrict_to(&mut self, val: &D::Value, depth: usize) {
        // Snapshot current values, then prune non-matching.
        // For BitsetDomain (u128), values() is just bit iteration — cheap.
        // The undo log records each removal for restore(depth).
        let vals: Vec<_> = self.domain.iter().collect();
        for v in &vals {
            if v != val {
                self.domain.remove(v);
                self.pruned.push((depth, v.clone()));
            }
        }
    }
}