dlx_rs/sudoku.rs
1//! Sudoku solver
2
3use crate::solver::Solver;
4
5/// Implements sudoku solver
6///
7/// ```
8///# use dlx_rs::sudoku::Sudoku;
9/// // Define sudoku grid, 0 is unknown number
10/// let sudoku = vec![
11/// 5, 3, 0, 0, 7, 0, 0, 0, 0,
12/// 6, 0, 0, 1, 9, 5, 0, 0, 0,
13/// 0, 9, 8, 0, 0, 0, 0, 6, 0,
14/// 8, 0, 0, 0, 6, 0, 0, 0, 3,
15/// 4, 0, 0, 8, 0, 3, 0, 0, 1,
16/// 7, 0, 0, 0, 2, 0, 0, 0, 6,
17/// 0, 6, 0, 0, 0, 0, 2, 8, 0,
18/// 0, 0, 0, 4, 1, 9, 0, 0, 5,
19/// 0, 0, 0, 0, 8, 0, 0, 7, 9,
20/// ];
21///
22/// // Create new sudoku from this grid
23/// let mut s = Sudoku::new_from_input(&sudoku);
24///
25/// let true_solution = vec![
26/// 5, 3, 4, 6, 7, 8, 9, 1, 2,
27/// 6, 7, 2, 1, 9, 5, 3, 4, 8,
28/// 1, 9, 8, 3, 4, 2, 5, 6, 7,
29/// 8, 5, 9, 7, 6, 1, 4, 2, 3,
30/// 4, 2, 6, 8, 5, 3, 7, 9, 1,
31/// 7, 1, 3, 9, 2, 4, 8, 5, 6,
32/// 9, 6, 1, 5, 3, 7, 2, 8, 4,
33/// 2, 8, 7, 4, 1, 9, 6, 3, 5,
34/// 3, 4, 5, 2, 8, 6, 1, 7, 9,
35/// ];
36/// // Checks only solution is true solution
37/// let solution = s.next().unwrap();
38/// assert_eq!(solution, true_solution);
39/// assert_eq!(s.next(), None);
40/// ```
41pub struct Sudoku {
42 /// Internal solver
43 pub solver: Solver<String>,
44 input: Vec<usize>,
45 n: usize,
46}
47
48impl Sudoku {
49 /// Initialises the constraints for an n*n sudoku-grid (regular is n=3, as the grid is 9x9)
50 /// This corresponds to a matrix with dimension (n**6)x(4*n**4)
51 pub fn new(n: usize) -> Sudoku {
52 // What are the constraints we need to meet?
53 // 1. Each cell must contain a number i.e. R1C1 must have precisely one number in it
54 // 2. Each row must have a 1, each row must have a 2, ...n^2
55 // 3. Each col must have a 1, each col must have a 2, ...n^2
56 // 4. Each sub-square must have a 1, each sub-square must have a 2, ...n^2
57 #[allow(non_snake_case)]
58 let N = n * n; // Sudoku edge length
59
60 //1: N*N constraints
61 //2: N rows * N numbers
62 //3: N cols * N numbers
63 //4: N cols * N numbers
64 //T: 4 N**2 items
65
66 let mut solver = Solver::new(4 * N * N);
67
68 // And how many options are there?
69 // Each cell may contain N options, and there are N*N, so N*N*N options
70 // e.g. R1C1#1: inserting a 1 into R1, C1
71
72 // For standard sudoku: 4*9^2 x 9^3 = 324 x 729
73
74 // 1. First constraints run R1C1,R1C2,...,R1CN,R2C1,...,RNCN
75 // After N^2 of these, we then have
76 // 2. Row constraint runs R1#1 R1#2 ... R2#1 R2#2
77 // 3. Col constraint runs C1#1 C1#2 ... C2#1 C2#2
78 // 4. Sub constraint runs S1#1 S1#2 ... S2#1 S2#2
79
80 // Add all of the options
81 for row in 1..=N {
82 for col in 1..=N {
83 for val in 1..=N {
84 let constraint_name = format!("R{}C{}#{}", row, col, val);
85 // Now add option
86 // Runs 1->N*(N-1)+N = N*N
87 let cell_con = col + (row - 1) * N;
88 // Runs N*N+1 -> N*N + N*(N-1) + N = 2*N*N
89 let row_con = N * N + N * (row - 1) + val;
90 // Runs 2*N*N+1 -> 2*N*N + N*(N-1) + N = 3*N*N
91 let col_con = 2 * N * N + N * (col - 1) + val;
92 let sub = (col - 1) / n + n * ((row - 1) / n);
93 // Runs 3*N*N+1 -> 3*N*N + N*(N-1) + N = 4*N*N
94 let sub_con = 3 * N * N + N * (sub) + val;
95 //println!("Adding constraint: {}",constraint_name);
96 solver.add_option(constraint_name, &[cell_con, row_con, col_con, sub_con]);
97
98 /*
99 if !(0 < cell_con && cell_con <= N*N) {
100 panic!("Woops! cell_con = {}, MIN = {}, MAX = {}", cell_con, 0*N*N,1*N*N );
101 }
102 if !(N*N < row_con && row_con <= 2*N*N) {
103 panic!("Woops! row_con = {}, MIN = {}, MAX = {}", row_con, 1*N*N,2*N*N );
104 }
105 if !(2*N*N < col_con && col_con <= 3*N*N) {
106 panic!("Woops! col_con = {}, MIN = {}, MAX = {}", col_con, 2*N*N,3*N*N );
107 }
108 if !(3*N*N < sub_con && sub_con <= 4*N*N) {
109 panic!("Woops! sub_con = {}, MIN = {}, MAX = {}", sub_con, 3*N*N,4*N*N );
110 }
111 */
112 }
113 }
114 }
115
116 Sudoku {
117 solver,
118 n,
119 input: vec![],
120 }
121 }
122
123 /// Initialises an appropriately sized Sudoku with all of the correct
124 /// constraints, and then selects all of the options corresponding the the
125 /// non-zero entires in `input`
126 pub fn new_from_input(input: &[usize]) -> Self {
127 let inputv = input.to_vec();
128 let nsq: usize = inputv.len();
129 let n: usize = (nsq as f64).sqrt().sqrt() as usize;
130
131 if nsq != n * n * n * n {
132 panic!("Input must be an array of length n**4")
133 }
134 let mut s = Self::new(n);
135 s.input = inputv;
136
137 for (i, item) in input.iter().enumerate() {
138 if *item != 0 {
139 let row = i / (n * n);
140 let col = i - n * n * row;
141 let opt_string = format!("R{}C{}#{}", row + 1, col + 1, *item);
142 // println!("{}",opt_string);
143 s.solver.select(opt_string).unwrap();
144 }
145 }
146
147 s
148 }
149}
150
151impl Iterator for Sudoku {
152 type Item = Vec<usize>;
153
154 /// If a remaining solution exists, returns `Some(v)` where `v` is a `Vec<usize>` containing the flat solve Sudoku grid.
155 /// Otherwise returns `None`
156 /// ```
157 ///# use dlx_rs::sudoku::Sudoku;
158 /// // Define sudoku grid, 0 is unknown number
159 /// let sudoku = vec![
160 /// 5, 3, 0, 0, 7, 0, 0, 0, 0,
161 /// 6, 0, 0, 1, 9, 5, 0, 0, 0,
162 /// 0, 9, 8, 0, 0, 0, 0, 6, 0,
163 /// 8, 0, 0, 0, 6, 0, 0, 0, 3,
164 /// 4, 0, 0, 8, 0, 3, 0, 0, 1,
165 /// 7, 0, 0, 0, 2, 0, 0, 0, 6,
166 /// 0, 6, 0, 0, 0, 0, 2, 8, 0,
167 /// 0, 0, 0, 4, 1, 9, 0, 0, 5,
168 /// 0, 0, 0, 0, 8, 0, 0, 7, 9,
169 /// ];
170 ///
171 /// // Create new sudoku from this grid
172 /// let mut s = Sudoku::new_from_input(&sudoku);
173 ///
174 /// let true_solution = vec![
175 /// 5, 3, 4, 6, 7, 8, 9, 1, 2,
176 /// 6, 7, 2, 1, 9, 5, 3, 4, 8,
177 /// 1, 9, 8, 3, 4, 2, 5, 6, 7,
178 /// 8, 5, 9, 7, 6, 1, 4, 2, 3,
179 /// 4, 2, 6, 8, 5, 3, 7, 9, 1,
180 /// 7, 1, 3, 9, 2, 4, 8, 5, 6,
181 /// 9, 6, 1, 5, 3, 7, 2, 8, 4,
182 /// 2, 8, 7, 4, 1, 9, 6, 3, 5,
183 /// 3, 4, 5, 2, 8, 6, 1, 7, 9,
184 /// ];
185 /// // Checks solution
186 /// let solution =s.next();
187 /// assert_eq!(solution, Some(true_solution));
188 ///
189 /// let another = s.next();
190 /// assert_eq!(another, None);
191 ///
192 /// ```
193 ///
194 fn next(&mut self) -> Option<Self::Item> {
195 if let Some(sol) = self.solver.next() {
196 let mut sudoku_solved = self.input.clone();
197 for i in sol {
198 let i = i.as_str();
199 let s: Vec<&str> = i.split(&['R', 'C', '#']).collect(); //.split('C').split('#');
200 let r: usize = s[1].parse().unwrap();
201 let c: usize = s[2].parse().unwrap();
202 let v: usize = s[3].parse().unwrap();
203 sudoku_solved[(c - 1) + self.n * self.n * (r - 1)] = v;
204 }
205 Some(sudoku_solved)
206 } else {
207 None
208 }
209 }
210}
211
212impl Sudoku {
213 /// Takes an input sudoku array and produces a pretty printed version
214 /// ```
215 ///# use dlx_rs::sudoku::Sudoku;
216 /// let sudoku = vec![
217 /// 5, 3, 0, 0, 7, 0, 0, 0, 0,
218 /// 6, 0, 0, 1, 9, 5, 0, 0, 0,
219 /// 0, 9, 8, 0, 0, 0, 0, 6, 0,
220 /// 8, 0, 0, 0, 6, 0, 0, 0, 3,
221 /// 4, 0, 0, 8, 0, 3, 0, 0, 1,
222 /// 7, 0, 0, 0, 2, 0, 0, 0, 6,
223 /// 0, 6, 0, 0, 0, 0, 2, 8, 0,
224 /// 0, 0, 0, 4, 1, 9, 0, 0, 5,
225 /// 0, 0, 0, 0, 8, 0, 0, 7, 9,
226 /// ];
227 /// println!("{}",&Sudoku::pretty(&sudoku));
228 /// ```
229 /// produces
230 /// ```text
231 /// 5 3 ║ 7 ║
232 /// 6 ║ 1 9 5 ║
233 /// 9 8 ║ ║ 6
234 /// ═══════╬═══════╬═══════
235 /// 8 ║ 6 ║ 3
236 /// 4 ║ 8 3 ║ 1
237 /// 7 ║ 2 ║ 6
238 /// ═══════╬═══════╬═══════
239 /// 6 ║ ║ 2 8
240 /// ║ 4 1 9 ║ 5
241 /// ║ 8 ║ 7 9
242 /// ```
243 ///
244 ///
245 pub fn pretty(sudoku_solved: &[usize]) -> String {
246 let mut result = String::new();
247 let n = (sudoku_solved.len() as f64).sqrt().sqrt() as usize;
248 #[allow(non_snake_case)]
249 let N = n * n;
250 // Print the array in a pretty way
251 for i in 0..N {
252 result += " ";
253 for j in 0..N {
254 result += &match sudoku_solved[i * N + j] {
255 0 => String::from(" "),
256 v => v.to_string(),
257 };
258 result += " ";
259
260 if (j + 1) % n == 0 && j < N - 1 {
261 result += "║ ";
262 }
263 }
264 if i < N - 1 {
265 result += "\n";
266 }
267 if (i + 1) % n == 0 && i < N - 1 {
268 result += &("═".repeat(2 * n + 1));
269 for _ in 1..n {
270 result += "╬";
271 result += &("═".repeat(2 * n + 1));
272 }
273 result += "\n";
274 }
275 }
276 result
277 }
278}
279
280#[cfg(test)]
281mod test {
282 use super::*;
283
284 #[test]
285 fn sudoku_solve() {
286 let sudoku = vec![
287 5, 3, 0, 0, 7, 0, 0, 0, 0, 6, 0, 0, 1, 9, 5, 0, 0, 0, 0, 9, 8, 0, 0, 0, 0, 6, 0, 8, 0,
288 0, 0, 6, 0, 0, 0, 3, 4, 0, 0, 8, 0, 3, 0, 0, 1, 7, 0, 0, 0, 2, 0, 0, 0, 6, 0, 6, 0, 0,
289 0, 0, 2, 8, 0, 0, 0, 0, 4, 1, 9, 0, 0, 5, 0, 0, 0, 0, 8, 0, 0, 7, 9,
290 ];
291
292 let mut s = Sudoku::new_from_input(&sudoku);
293
294 let true_solution = vec![
295 5, 3, 4, 6, 7, 8, 9, 1, 2, 6, 7, 2, 1, 9, 5, 3, 4, 8, 1, 9, 8, 3, 4, 2, 5, 6, 7, 8, 5,
296 9, 7, 6, 1, 4, 2, 3, 4, 2, 6, 8, 5, 3, 7, 9, 1, 7, 1, 3, 9, 2, 4, 8, 5, 6, 9, 6, 1, 5,
297 3, 7, 2, 8, 4, 2, 8, 7, 4, 1, 9, 6, 3, 5, 3, 4, 5, 2, 8, 6, 1, 7, 9,
298 ];
299 let sol = s.next().unwrap();
300 assert_eq!(sol, true_solution);
301 }
302}