rudoku_core/sudoku/
mod.rs

1#[cfg(test)]
2mod tests;
3pub mod sudoku_value;
4
5use rand::seq::SliceRandom;
6use rand;
7use itertools::Itertools;
8
9use super::util::*;
10use sudoku_value::*;
11use std::convert::TryFrom;
12
13#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Copy, Clone)]
14pub struct Sudoku {
15    board: [[SudokuValue; 9]; 9]
16}
17
18impl Sudoku {
19    /// Populates a Sudoku board with n hints.
20    /// Returns `(unsolved sudoku, solved sudoku)`.
21    pub fn new(n: usize) -> (Self, Self) {
22        let arr = [[SudokuValue::Empty; 9]; 9];
23        let mut sudoku = Sudoku{ board: arr };
24        sudoku.fill(0, 0).unwrap();
25        let solution = sudoku.clone();
26        sudoku.decimate(n).unwrap();
27
28        (sudoku, solution)
29    }
30
31    /// Removes elements from a filled sudoku until there
32    /// are `n` elements left, while having only 1 solution.
33    pub fn decimate(&mut self, n: usize) -> Result<(), String> {
34        // < 17 is impossible
35        if 17 > n {
36            return Err(format!("It is impossible to create a Sudoku with an unique solution, with less than 17 hints. Input was {} hints.", n));
37        } else if n > 81 {
38            return Err(format!("Impossible to create a Sudoku with {} hints. A Sudoku has just 81 fields.", n));
39        } else if n == 81 {
40            return Ok(());
41        }
42
43        let mut rng = rand::thread_rng();
44        // capacity = sudoku_size - number_remaining_elements + 1 (last element doesn't have to be popped, because then the function returns)
45        let mut stack: Vec<(SudokuValue, Vec<usize>)> = Vec::with_capacity(9*9 - n + 1);
46        let mut all_indices = (0..9).permutations(2).collect_vec();
47        loop {
48            all_indices.shuffle(&mut rng);
49            for index in &all_indices {
50                if self.board[index[0]][index[1]] == SudokuValue::Empty {
51                    continue;
52                }
53                // remove from the board
54                stack.push((self.board[index[0]][index[1]], index.clone()));
55                self.board[index[0]][index[1]] = SudokuValue::Empty;
56                if self.solve(0, 0) != 1 {
57                    // if there isn't one distinct solution revert
58                    match stack.pop() {
59                        Some((val, index)) => {
60                            self.board[index[0]][index[1]] = val;
61                        },
62                        None => return Err(format!("Popped with no elements left!"))
63                    }
64                }
65                if self.count(SudokuValue::Empty) == 81-n {
66                    return Ok(());
67                }
68            }
69            // if this branch didn't have any unique solutions revert
70            match stack.pop() {
71                Some((val, index)) => {
72                    self.board[index[0]][index[1]] = val;
73                },
74                None => return Err(format!("Popped with no elements left!"))
75            }
76        }
77    }
78
79    /// Returns the number of different solutions of a given Sudoku
80    /// call this function with `sudoku.solve(0, 0)`.
81    pub fn solve(&mut self, r: usize, c: usize) -> i32 {
82        // code is similar to Sudoku::fill, maybe a helper function can combine some of the code
83        let mut counter = 0;
84        if self.board[r][c] != SudokuValue::Empty {
85            let next_r: usize;
86            let next_c: usize;
87            match (r, c) {
88                // impossible, because then every field, would be filled but it wouldn't be solved
89                // (8, 8) => ...
90                (_, 8) => {
91                    next_r = r + 1;
92                    next_c = 0;
93                },
94                (_, _) => {
95                    next_r = r;
96                    next_c = c + 1;
97                }
98            }
99            if self.solved() {
100                // this recursion reached it's end with a completed Sudoku so return.
101                // it isn't possible for another number to fit this r, c value.
102                // Mutating the original Sudoku, so it has to be restored
103                return 1;
104            } else {
105                // don't return, other numbers in this field could lead to additional solutions
106                return counter + self.solve(next_r, next_c);
107                // Mutating the original Sudoku, so it has to be restored
108            }
109        }
110        let sudoku_numbers: [SudokuValue; 9] = SudokuValue::get_number_array();
111        for number in &sudoku_numbers {
112            self.board[r][c] = *number;
113            if self.check(r, c) {
114                let next_r: usize;
115                let next_c: usize;
116                match (r, c) {
117                    // impossible, because then every field, would be filled but it wouldn't be solved
118                    // (8, 8) => ...
119                    (_, 8) => {
120                        next_r = r + 1;
121                        next_c = 0;
122                    },
123                    (_, _) => {
124                        next_r = r;
125                        next_c = c + 1;
126                    }
127                }
128                if self.solved() {
129                    // this recursion reached it's end with a completed Sudoku so return.
130                    // it isn't possible for another number to fit this r, c value.
131                    // Mutating the original Sudoku, so it has to be restored
132                    self.board[r][c] = SudokuValue::Empty;
133                    return 1;
134                } else {
135                    // don't return, other numbers in this field could lead to additional solutions
136                    counter += self.solve(next_r, next_c);
137                    // Mutating the original Sudoku, so it has to be restored
138                    self.board[r][c] = SudokuValue::Empty;
139                }
140            }
141        }
142        // Mutating the original Sudoku, so it has to be restored
143        self.board[r][c] = SudokuValue::Empty;
144        counter
145    }
146
147    /// Fills an empty sudoku board.
148    /// Row and col are the first empty index.
149    /// Call this function with `sudoku.fill(0, 0)` to fill an empty board completely.
150    pub fn fill(&mut self, r: usize, c: usize) -> Result<(), ()> {
151        let mut rng = rand::thread_rng();
152        let mut sudoku_numbers: [SudokuValue; 9] = SudokuValue::get_number_array();
153        sudoku_numbers.shuffle(&mut rng);
154        for number in &sudoku_numbers {
155            self.board[r][c] = *number;
156            if self.check(r, c) {
157                let next_r: usize;
158                let next_c: usize;
159                match (r,c) {
160                    (8, 8) => return Ok(()),
161                    (_, 8) => {next_r = r + 1; next_c = 0;},
162                    (_, _) => {next_r = r; next_c = c + 1;}
163                }
164                if self.fill(next_r, next_c).is_ok() {
165                    return Ok(());
166                } else {
167                    self.board[r][c] = SudokuValue::Empty;
168                    continue;
169                }
170
171            }
172        }
173        // all numbers failed => impossible to continue from this => return false and make the recursion above try another number
174        self.board[r][c] = SudokuValue::Empty;
175        Err(())
176    }
177
178    /// Returns `true` if the sudoku is completely solved.
179    pub fn solved(&self) -> bool {
180        if self.count(SudokuValue::Empty) > 0 {
181            false
182        } else {
183            self.check_all()
184        }
185    }
186
187    /// Checks all rows, cols and squares by checking these indexes.
188    /// ```text
189    /// X** *** ***
190    /// *** X** ***
191    /// *** *** X**
192    /// *X* *** ***
193    /// *** *X* ***  the Xs get checked
194    /// *** *** *X*
195    /// **X *** ***
196    /// *** **X ***
197    /// *** *** **X
198    /// ```
199    pub fn check_all(&self) -> bool {
200        let indices = [(0, 0), (1, 3), (2, 6), (3, 1), (4, 4), (5, 7), (6, 2), (7, 5), (8, 8)];
201        for (r, c) in &indices {
202            if !self.check(*r, *c) {
203                return false;
204            }
205        }
206        true
207    }
208
209    /// Returns `true` if the row, column and square of the indices have no duplicate SudokuValue.
210    pub fn check(&self, r: usize, c: usize) -> bool {
211        let mut reference_arr_row: [&SudokuValue; 9] = match self.get_row(r) {
212            Some(x) => x,
213            None => panic!("IndexError")
214        };
215        let mut reference_arr_col: [&SudokuValue; 9] = match self.get_column(c) {
216            Some(x) => x,
217            None => panic!("IndexError")
218        };
219        let mut reference_arr_square: [&SudokuValue; 9] = match self.get_square(r, c) {
220            Some(x) => x,
221            None => panic!("IndexError")
222        };
223
224        has_only_unique_elements(&mut reference_arr_row, &SudokuValue::Empty)
225         && has_only_unique_elements(&mut reference_arr_col, &SudokuValue::Empty)
226         && has_only_unique_elements(&mut reference_arr_square, &SudokuValue::Empty)
227    }
228
229    /// Returns how often the SudokuValue is on the board.
230    pub fn count(&self, val: SudokuValue) -> usize {
231        let mut count = 0;
232        for r in 0..9 {
233            for c in 0..9 {
234                if self.board[r][c] == val {
235                    count += 1;
236                }
237            }
238        }
239        count
240    }
241
242    /// Returns the specified row.
243    pub fn get_row(&self, r: usize) -> Option<[&SudokuValue; 9]> {
244        return Some([
245            self.board.get(r)?.get(0)?,
246            self.board.get(r)?.get(1)?,
247            self.board.get(r)?.get(2)?,
248            self.board.get(r)?.get(3)?,
249            self.board.get(r)?.get(4)?,
250            self.board.get(r)?.get(5)?,
251            self.board.get(r)?.get(6)?,
252            self.board.get(r)?.get(7)?,
253            self.board.get(r)?.get(8)?
254        ]);
255    }
256
257    /// Returns the specified column.
258    pub fn get_column(&self, c: usize) -> Option<[&SudokuValue; 9]> {
259        return Some([
260            self.board.get(0)?.get(c)?,
261            self.board.get(1)?.get(c)?,
262            self.board.get(2)?.get(c)?,
263            self.board.get(3)?.get(c)?,
264            self.board.get(4)?.get(c)?,
265            self.board.get(5)?.get(c)?,
266            self.board.get(6)?.get(c)?,
267            self.board.get(7)?.get(c)?,
268            self.board.get(8)?.get(c)?
269        ]);
270    }
271
272    // Example:
273    // Sudoku:
274    // 111 222 333
275    // 111 222 333
276    // 111 222 333
277    // 444 555 666
278    // 444 555 666  r=4 c=7          -> [&SudokuValue::Eight; 9]
279    // 444 555 666
280    // 777 888 999
281    // 777 888 999
282    // 777 888 999
283    /// Returns the square in which the indices lie.
284    pub fn get_square(&self, r: usize, c: usize) -> Option<[&SudokuValue; 9]> {
285        return Some([
286            self.board.get((r / 3) * 3 + 0)?.get((c / 3) * 3 + 0)?,
287            self.board.get((r / 3) * 3 + 0)?.get((c / 3) * 3 + 1)?,
288            self.board.get((r / 3) * 3 + 0)?.get((c / 3) * 3 + 2)?,
289            self.board.get((r / 3) * 3 + 1)?.get((c / 3) * 3 + 0)?,
290            self.board.get((r / 3) * 3 + 1)?.get((c / 3) * 3 + 1)?,
291            self.board.get((r / 3) * 3 + 1)?.get((c / 3) * 3 + 2)?,
292            self.board.get((r / 3) * 3 + 2)?.get((c / 3) * 3 + 0)?,
293            self.board.get((r / 3) * 3 + 2)?.get((c / 3) * 3 + 1)?,
294            self.board.get((r / 3) * 3 + 2)?.get((c / 3) * 3 + 2)?
295        ]);
296    }
297
298    /// Returns the SudokuValue at the specified indices.
299    pub fn get(&self, r: usize, c: usize) -> Option<&SudokuValue> {
300        return self.board.get(r)?.get(c);
301    }
302
303    /// Sets the value at the specified indices.
304    pub fn set(&mut self, r: usize, c: usize, val: SudokuValue) {
305        self.board[r][c] = val;
306    }
307}
308
309impl TryFrom<&str> for Sudoku {
310    type Error = String;
311
312    /// The provided `&str` has to have a length of 81 and is only allowed to have the chars in 0-9.
313    fn try_from(sud_str: &str) -> Result<Self, Self::Error> {
314        if sud_str.len() != 81 {
315            return Err(format!("The provided String does not meet the required length of 81, it's length is {}", sud_str.len()));
316        }
317        let mut sud = Sudoku{board: [[SudokuValue::Empty; 9]; 9]};
318        let mut col = 0;
319        let mut row = 0;
320        let mut err = false;
321        for c in sud_str.chars() {
322            match c.to_digit(10) {
323                Some(x) => sud.board[row][col] = SudokuValue::try_from(i32::try_from(x).unwrap()).unwrap(),
324                None => err = true
325            }
326            match col {
327                8 => {col = 0; row += 1}
328                _ => col += 1
329            }
330        }
331        match err {
332            true => Err(String::from("SudokuValue has to be in the range 0..=9")),
333            false => Ok(sud)
334        }
335    }
336}
rudoku_core/sudoku/mod.rs

rudoku_core/sudoku/
mod.rs
