dlx_rs/aztec.rs
1//! An interface to a [`Solver`] in order to solve an Aztec diamond problem
2use crate::Solver;
3use std::collections::HashSet;
4
5enum Color {
6 Red,
7 Yellow,
8 Blue,
9 Green,
10 Black,
11}
12
13/// Finds all solutions to Aztec diamond problem
14/// ```
15///# use dlx_rs::aztec::Aztec;
16/// for n in 1..=5 {
17/// let az = Aztec::new(n);
18/// // Check number of solutions is equal to 2^(n*(n+1)/2)
19/// assert_eq!(az.count(), 1 << (n*(n+1)/2));
20/// }
21/// ```
22pub struct Aztec {
23 n: usize,
24 solver: Solver<String>,
25}
26
27impl Aztec {
28 /// Creates new `Aztec` set up with constraints for the order `n` Aztec diamond
29 pub fn new(n: usize) -> Aztec {
30 // Create blank solver
31
32 // Only constraint is that each square must be covered, and there are
33
34 // (1+2+...+n)*4 = 2*n*(n+1) squares for the order n Aztec diamond
35
36 // Squares are laid out sequentially in memory running left to right from the top down i.e.
37
38 // 1 2
39 // 3 4 5 6
40 // 7 8 9 10
41 // 11 12
42
43 // 1 2
44 // 3 4 5 6
45 // 7 8 9 10 11 12
46 // 13 14 15 16 17 18
47 // 19 20 21 22
48 // 23 24
49
50 let mut solver = Solver::new(2 * n * (n + 1));
51
52 // Now add options: each option corresponds to either a vertical or horizontal dominos
53 // We first add the horizontal dominos, which run along every tile except for the last on each row, which means we have
54 // 2*n*(n+1) - 2*n = 2*n*n horizontal domino constraints
55 let max = 2 * n * (n + 1);
56
57 // Construct positions at end of row
58 let row_ends_top = (1..=n).map(|x| x * (x + 1));
59 let row_ends_bottom = (1..=n).map(|x| max - x * (x - 1));
60
61 let row_ends = row_ends_top.chain(row_ends_bottom);
62 let row_ends_set: HashSet<usize> = HashSet::from_iter(row_ends);
63
64 println!();
65
66 // Horizontal dominoes
67
68 for x in 1..=2 * n * (n + 1) {
69 if !row_ends_set.contains(&x) {
70 let pos1 = x;
71 let pos2 = pos1 + 1;
72 let con_name = format!("H{}#{}", pos1, pos2);
73 solver.add_option(con_name, &[pos1, pos2]);
74 }
75 }
76
77 // Vertical dominoes
78 // First n-1 rows are trivial: for row j pick square i, and square i + j*(j+1) - j*(j-1) + 1 = i + 2*j + 1
79 for j in 1..=n - 1 {
80 for i in 1..=2 * j {
81 let pos1 = j * (j - 1) + i;
82 let pos2 = pos1 + 2 * j + 1;
83
84 let con_name = format!("V{}#{}", pos1, pos2);
85 solver.add_option(con_name, &[pos1, pos2]);
86
87 // Now add mirror image of this
88 let mpos1 = max - pos1 + 1;
89 let mpos2 = max - pos2 + 1;
90
91 let mcon_name = format!("V{}#{}", mpos2, mpos1);
92 solver.add_option(mcon_name, &[mpos2, mpos1]);
93 }
94 }
95 // Final (biggest row), runs from n(n-1) + 1 -> n(n-1) + 1 + 2n -1, and pairs with
96 let final_min = n * (n - 1) + 1;
97 let final_max = final_min + 2 * n - 1;
98 for x in final_min..=final_max {
99 let pos1 = x;
100 let pos2 = x + 2 * n;
101
102 let con_name = format!("V{}#{}", pos1, pos2);
103 solver.add_option(con_name, &[pos1, pos2]);
104 }
105
106 Aztec { solver, n }
107 }
108
109 /// Prints a solution using ANSI colour codes on the terminal
110 /// ```
111 ///# use dlx_rs::aztec::Aztec;
112 /// let n = 5;
113 /// let az = Aztec::new(n);
114 /// for sol in az {
115 /// Aztec::pretty_print_sol(&sol);
116 /// }
117 /// ```
118 pub fn pretty_print_sol(sol: &[(usize, usize)]) {
119 // Gets n from length of solution
120 let n = (sol.len() as f64).sqrt() as usize;
121 let max = 2 * n * (n + 1);
122
123 // Construct positions at end of row
124 let row_ends_top = (1..=n).map(|x| x * (x + 1));
125 let row_ends_bottom = (1..=n).map(|x| max - x * (x - 1));
126
127 let row_ends = row_ends_top.chain(row_ends_bottom);
128 let row_ends_set: HashSet<usize> = HashSet::from_iter(row_ends);
129
130 let mut solc: Vec<Color> = Vec::with_capacity(2 * sol.len());
131 for _ in 1..=2 * sol.len() {
132 solc.push(Color::Black);
133 }
134
135 // Go through items in solution
136 for item in sol {
137 let min = (item.0).min(item.1);
138 let max = (item.0).max(item.1);
139
140 let par = match min {
141 x if x > n * (n + 1) => 1,
142 _ => 0,
143 };
144 // If horizontal bond
145 if max == min + 1 {
146 if min % 2 == par {
147 solc[min - 1] = Color::Blue;
148 solc[max - 1] = Color::Blue;
149 } else {
150 solc[min - 1] = Color::Yellow;
151 solc[max - 1] = Color::Yellow;
152 }
153 } else if min % 2 == par {
154 solc[min - 1] = Color::Green;
155 solc[max - 1] = Color::Green;
156 } else {
157 solc[min - 1] = Color::Red;
158 solc[max - 1] = Color::Red;
159 }
160 }
161
162 // Now print first n rows
163 let mut row_dir = true;
164 let mut row_pad = n;
165 let mut rr = " ".repeat(row_pad);
166
167 print!("{}", rr);
168 for (i, _) in solc.iter().enumerate() {
169 // Print appropriate colour
170 match solc[i] {
171 Color::Red => print!("\x1b[31;41mX\x1b[0m"),
172 Color::Green => print!("\x1b[32;42mX\x1b[0m"),
173 Color::Yellow => print!("\x1b[33;43mX\x1b[0m"),
174 Color::Blue => print!("\x1b[34;44mX\x1b[0m"),
175 Color::Black => print!("\x1b[30;40mX\x1b[0m"),
176 };
177
178 // Padding for each row, decrease padding until row `n`, then increase again
179 if row_ends_set.contains(&(i + 1)) {
180 if row_dir {
181 row_pad -= 1;
182 if row_pad == 0 {
183 row_dir = false;
184 row_pad += 1;
185 }
186 } else {
187 row_pad += 1;
188 }
189 println!();
190 rr = " ".repeat(row_pad);
191 print!("{}", rr);
192 }
193 }
194 println!();
195 }
196}
197
198impl Iterator for Aztec {
199 type Item = Vec<(usize, usize)>;
200 /// Returns the next solution, which is a vector of tuples denoting the Row and Column of the N queens in the solution
201 fn next(&mut self) -> Option<Self::Item> {
202 if let Some(sol) = self.solver.next() {
203 let mut dom_solved = Vec::with_capacity(self.n);
204 for i in sol {
205 let i = i.as_str();
206 let s: Vec<&str> = i.split(&['H', 'V', '#']).collect();
207 let p1: usize = s[1].parse().unwrap();
208 let p2: usize = s[2].parse().unwrap();
209 dom_solved.push((p1, p2));
210 }
211 Some(dom_solved)
212 } else {
213 None
214 }
215 }
216}