rust_constraint/
core.rs

1use std::{collections::HashMap, fmt::Display};
2
3// Problem
4pub struct Problem<T = String>
5where
6    T: Clone,
7{
8    varaibles: Vec<Variable<T>>,
9    constraints: Vec<Constraint<T>>,
10    solver: Solver,
11}
12
13#[derive(Debug)]
14pub struct Solution<T>(HashMap<String, T>);
15
16impl<T> Solution<T> {
17    pub fn get_map(&self) -> &HashMap<String, T> {
18        return &self.0;
19    }
20}
21
22impl<T: Display> std::fmt::Display for Solution<T> {
23    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
24        let pairs = self
25            .0
26            .iter()
27            .map(|(k, v)| format!("{k}: {v}"))
28            .collect::<Vec<String>>();
29        write!(f, "{{{}}}", pairs.join(", "))
30    }
31}
32
33impl<T: Clone> Problem<T> {
34    pub fn new() -> Problem<T> {
35        Problem {
36            varaibles: vec![],
37            constraints: vec![],
38            solver: Solver::default(),
39        }
40    }
41
42    pub fn solver(mut self, solver: Solver) -> Self {
43        self.set_solver(solver);
44        self
45    }
46
47    pub fn set_solver(&mut self, solver: Solver) {
48        self.solver = solver
49    }
50
51    pub fn variables<V: Into<String>>(mut self, var_names: Vec<V>, domains: Vec<T>) -> Self {
52        self.add_variables(var_names, domains);
53        self
54    }
55
56    pub fn add_variables<V: Into<String>>(&mut self, var_names: Vec<V>, domains: Vec<T>) {
57        for var_name in var_names {
58            self.add_variable(var_name.into(), domains.clone())
59        }
60    }
61
62    pub fn variable<V: Into<String>>(mut self, var_name: V, domains: Vec<T>) -> Self {
63        self.add_variable(var_name, domains);
64        self
65    }
66
67    pub fn add_variable<V: Into<String>>(&mut self, var_name: V, domains: Vec<T>) {
68        self.varaibles.push(Variable::new(var_name.into(), domains));
69    }
70
71    pub fn constraint(mut self, constraint: Constraint<T>) -> Self {
72        self.add_constraint(constraint);
73        self
74    }
75
76    pub fn add_constraint(&mut self, constraint: Constraint<T>) {
77        self.constraints.push(constraint);
78    }
79
80    pub fn constraint_unary<N: Into<String>>(mut self, var_name: N, test: fn(&T) -> bool) -> Self {
81        self.add_constraint_unary(var_name, test);
82        self
83    }
84
85    pub fn add_constraint_unary<N: Into<String>>(&mut self, var_name: N, test: fn(&T) -> bool) {
86        self.add_constraint(Constraint::Unary(var_name.into(), test));
87    }
88
89    pub fn constraint_binary<N: Into<String>>(
90        mut self,
91        var_a: N,
92        var_b: N,
93        test: fn(&T, &T) -> bool,
94    ) -> Self {
95        self.add_constraint_binary(var_a, var_b, test);
96        self
97    }
98
99    pub fn add_constraint_binary<N: Into<String>>(
100        &mut self,
101        var_a: N,
102        var_b: N,
103        test: fn(&T, &T) -> bool,
104    ) {
105        self.add_constraint(Constraint::Binary(var_a.into(), var_b.into(), test))
106    }
107
108    pub fn get_solutions(&self) -> Vec<Solution<T>> {
109        match self.solver {
110            Solver::RecursiveBacktracking => basic_recursive_backtracking(self),
111        }
112    }
113}
114
115// Variable
116
117#[derive(Clone)]
118pub struct Variable<T: Clone = String> {
119    name: String,
120    domains: Vec<T>,
121}
122
123impl<T: Clone> Variable<T> {
124    pub fn new(name: String, domains: Vec<T>) -> Self {
125        Self { name, domains }
126    }
127
128    pub fn name(&self) -> &str {
129        &self.name
130    }
131
132    pub fn domains(&self) -> &Vec<T> {
133        &self.domains
134    }
135}
136
137impl From<(String, Vec<String>)> for Variable {
138    fn from(value: (String, Vec<String>)) -> Self {
139        Variable::new(value.0, value.1)
140    }
141}
142
143impl From<(&str, Vec<&str>)> for Variable {
144    fn from(value: (&str, Vec<&str>)) -> Self {
145        Variable::new(
146            value.0.to_owned(),
147            value.1.iter().map(|v| v.to_string()).collect(),
148        )
149    }
150}
151
152// Constraint
153
154pub enum Constraint<T: Clone = String> {
155    Unary(String, fn(&T) -> bool),
156    Binary(String, String, fn(&T, &T) -> bool),
157}
158// Solver
159
160#[derive(Default)]
161pub enum Solver {
162    #[default]
163    RecursiveBacktracking,
164}
165
166#[derive(Clone)]
167pub struct Assingment<T> {
168    values: HashMap<String, T>,
169}
170
171impl<T: Clone> Assingment<T> {
172    pub fn new() -> Self {
173        Self {
174            values: HashMap::new(),
175        }
176    }
177
178    pub fn is_consistent(&self, problem: &Problem<T>) -> bool {
179        for con in problem.constraints.iter() {
180            match con {
181                Constraint::Unary(a, unary_test) => {
182                    let Some(value_a) = self.values.get(a) else {
183                        continue;
184                    };
185
186                    if !unary_test(&value_a) {
187                        return false;
188                    }
189                }
190                Constraint::Binary(a, b, binary_test) => {
191                    let Some(value_a) = self.values.get(a) else {
192                        continue;
193                    };
194                    let Some(value_b) = self.values.get(b) else {
195                        continue;
196                    };
197
198                    if !binary_test(&value_a, &value_b) {
199                        return false;
200                    }
201                }
202            }
203        }
204        true
205    }
206
207    pub fn is_complete(&self, problem: &Problem<T>) -> bool {
208        for var in problem.varaibles.iter() {
209            if !self.values.contains_key(var.name()) {
210                return false;
211            }
212        }
213        true
214    }
215
216    pub fn select_variable(&self, problem: &Problem<T>) -> Option<Variable<T>> {
217        for var in problem.varaibles.iter() {
218            if !self.values.contains_key(var.name()) {
219                return Some(var.clone());
220            }
221        }
222        None
223    }
224
225    pub fn insert(&mut self, name: &str, value: &T) {
226        self.values.insert(name.to_string(), value.clone());
227    }
228
229    pub fn remove(&mut self, name: &str) {
230        self.values.remove(name);
231    }
232
233    pub fn solution(self) -> Solution<T> {
234        Solution(self.values)
235    }
236}
237
238fn basic_recursive_backtracking<T: Clone>(problem: &Problem<T>) -> Vec<Solution<T>> {
239    let mut assigment = Assingment::new();
240    let mut solutions = vec![];
241    recursive_backtracking(&mut solutions, &mut assigment, &problem);
242    solutions
243}
244
245fn recursive_backtracking<T: Clone>(
246    solutons: &mut Vec<Solution<T>>,
247    assigment: &mut Assingment<T>,
248    problem: &Problem<T>,
249) -> bool {
250    let Some(var) = assigment.select_variable(&problem) else {
251        solutons.push(assigment.clone().solution());
252        return true;
253    };
254
255    for value in var.domains() {
256        assigment.insert(&var.name, &value);
257        if assigment.is_consistent(&problem) {
258            recursive_backtracking(solutons, assigment, &problem);
259        }
260        assigment.remove(&var.name)
261    }
262
263    false
264}