1use std::{collections::HashMap, fmt::Display};
2
3pub 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#[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
152pub enum Constraint<T: Clone = String> {
155 Unary(String, fn(&T) -> bool),
156 Binary(String, String, fn(&T, &T) -> bool),
157}
158#[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}