sudoku_variants/solver/
mod.rs

1//! This module contains the logic for solving Sudoku.
2//!
3//! Most importantly, this module contains the definition of the [Solver] trait
4//! and the [BacktrackingSolver] as a generally usable implementation.
5
6use crate::{Sudoku, SudokuGrid};
7use crate::constraint::Constraint;
8
9pub mod strategy;
10
11/// An enumeration of the different ways a Sudoku can be solveable. Note that
12/// this may be relative to the solver, since an imperfect solver may be unable
13/// to continue at some point, yielding `Solution::Ambiguous`, where the Sudoku
14/// is actually uniquely solveable or impossible.
15#[derive(Clone, Debug, Eq, PartialEq)]
16pub enum Solution {
17
18    /// Indicates that the Sudoku is not solveable at all.
19    Impossible,
20
21    /// Indicates that the Sudoku has a unique solution, which is wrapped in
22    /// this instance.
23    Unique(SudokuGrid),
24
25    /// Indicates that the Sudoku has multiple solutions or, at least, that the
26    /// solver was unable to find a unique one or prove it is impossible.
27    Ambiguous
28}
29
30impl Solution {
31
32    /// Computes the union of two solutions. This is defined as follows:
33    ///
34    /// * If one solution is `Solution::Impossible`, the other one is returned.
35    /// * If one solution is `Solution::Ambiguous` then the result is also
36    /// ambiguous
37    /// * If both solutions are `Solution::Unique` with solution grids `g1` and
38    /// `g2`, then the result is `Solution::Unique(g1)` if `g1 == g2` and
39    /// `Solution::Ambiguous` otherwise.
40    pub fn union(self, other: Solution) -> Solution {
41        match self {
42            Solution::Impossible => other,
43            Solution::Unique(g) =>
44                match other {
45                    Solution::Impossible => Solution::Unique(g),
46                    Solution::Unique(other_g) =>
47                        if g == other_g {
48                            Solution::Unique(g)
49                        }
50                        else {
51                            Solution::Ambiguous
52                        }
53                    Solution::Ambiguous => Solution::Ambiguous
54                }
55            Solution::Ambiguous => Solution::Ambiguous
56        }
57    }
58}
59
60/// A trait for structs which have the ability to solve Sudoku. Not all
61/// implementers must be able to find a unique solution to every uniquely
62/// solveable Sudoku, some solvers may be less powerful, similar to a less
63/// experienced human solver. This may make sense to check whether some Sudoku
64/// is solveable using some strategy.
65pub trait Solver {
66
67    /// Solves, or attempts to solve, the provided Sudoku. If the solver cannot
68    /// prove that a Sudoku is impossible or uniquely solveable (either
69    /// because it isn't or the solver is not powerful enough), they shall
70    /// return `Solution::Ambiguous`.
71    fn solve(&self, sudoku: &Sudoku<impl Constraint + Clone>) -> Solution;
72}
73
74/// A perfect [Solver] which solves Sudoku by recursively testing all valid
75/// numbers for each cell. This means two things:
76///
77/// * Its worst-case runtime is exponential, i.e. it may be very slow if the
78/// Sudoku has many missing digits.
79/// * It can provide the correct [Solution] for any Sudoku with any constraint.
80pub struct BacktrackingSolver;
81
82impl BacktrackingSolver {
83    fn solve_rec(sudoku: &mut Sudoku<impl Constraint + Clone>, column: usize,
84            row: usize) -> Solution {
85        let size = sudoku.grid().size();
86        let last_cell = row == size;
87
88        if last_cell {
89            return Solution::Unique(sudoku.grid().clone());
90        }
91
92        let next_column = (column + 1) % size;
93        let next_row = if next_column == 0 { row + 1 } else { row };
94
95        if sudoku.grid().get_cell(column, row).unwrap().is_some() {
96            BacktrackingSolver::solve_rec(sudoku, next_column, next_row)
97        }
98        else {
99            let mut solution = Solution::Impossible;
100
101            for number in 1..=size {
102                if sudoku.is_valid_number(column, row, number).unwrap() {
103                    sudoku.grid_mut().set_cell(column, row, number).unwrap();
104                    let next_solution =
105                        BacktrackingSolver::solve_rec(sudoku, next_column,
106                            next_row);
107                    sudoku.grid_mut().clear_cell(column, row).unwrap();
108                    solution = solution.union(next_solution);
109
110                    if solution == Solution::Ambiguous {
111                        break;
112                    }
113                }
114            }
115
116            solution
117        }
118    }
119
120    fn solve(sudoku: &mut Sudoku<impl Constraint + Clone>) -> Solution {
121        BacktrackingSolver::solve_rec(sudoku, 0, 0)
122    }
123}
124
125impl Solver for BacktrackingSolver {
126    fn solve(&self, sudoku: &Sudoku<impl Constraint + Clone>) -> Solution {
127        let mut clone = sudoku.clone();
128        BacktrackingSolver::solve(&mut clone)
129    }
130}
131
132#[cfg(test)]
133mod tests {
134
135    use super::*;
136
137    use crate::constraint::{
138        AdjacentConsecutiveConstraint,
139        CompositeConstraint,
140        DefaultConstraint,
141        DiagonalsConstraint,
142        DiagonallyAdjacentConstraint,
143        KingsMoveConstraint,
144        KnightsMoveConstraint
145    };
146
147    fn test_solves_correctly<C>(puzzle: &str, solution: &str, constraint: C)
148    where
149        C: Constraint + Clone
150    {
151        let sudoku = Sudoku::parse(puzzle, constraint).unwrap();
152        let solver = BacktrackingSolver;
153        let found_solution = solver.solve(&sudoku);
154        
155        if let Solution::Unique(grid) = found_solution {
156            let expected_grid = SudokuGrid::parse(solution).unwrap();
157            assert_eq!(expected_grid, grid, "Solver gave wrong grid.");
158        }
159        else {
160            panic!("Solveable sudoku marked as impossible or ambiguous.");
161        }
162    }
163
164    // The example Sudoku are taken from the World Puzzle Federation Sudoku Grand Prix:
165
166    // Classic + Diagonals: GP 2020 Round 8 (Puzzles 2 + 6)
167    // Puzzles: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2020/2020_SudokuRound8.pdf
168    // Solutions: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2020/2020_SudokuRound8_SB.pdf
169
170    // No Knights Move: GP 2018 Round 1 (Puzzle 8)
171    // Puzzle: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2018/2018_SudokuRound1.pdf
172    // Solution: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2018/2018_SudokuRound1_SB.pdf
173
174    // No Kings Move: GP 2017 Round 1 (Puzzle 11)
175    // Puzzle: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2017/2017_SudokuRound1.pdf
176    // Solution: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2017/2017_SudokuRound1_SB.pdf
177
178    // No Adjacent Consecutive: GP 2019 Round 1 (Puzzle 7)
179    // Puzzle: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2019/2019_SudokuRound1.pdf
180    // Solution: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2019/2019_SudokuRound1_SB.pdf
181
182    #[test]
183    fn backtracking_solves_classic_sudoku() {
184        let puzzle = "3x3;\
185             , , , ,8,1, , , ,\
186             , ,2, , ,7,8, , ,\
187             ,5,3, , , ,1,7, ,\
188            3,7, , , , , , , ,\
189            6, , , , , , , ,3,\
190             , , , , , , ,2,4,\
191             ,6,9, , , ,2,3, ,\
192             , ,5,9, , ,4, , ,\
193             , , ,6,5, , , , ";
194        let solution = "3x3;\
195            7,4,6,2,8,1,3,5,9,\
196            9,1,2,5,3,7,8,4,6,\
197            8,5,3,4,9,6,1,7,2,\
198            3,7,4,1,2,5,6,9,8,\
199            6,2,8,7,4,9,5,1,3,\
200            5,9,1,3,6,8,7,2,4,\
201            1,6,9,8,7,4,2,3,5,\
202            2,8,5,9,1,3,4,6,7,\
203            4,3,7,6,5,2,9,8,1";
204        test_solves_correctly(puzzle, solution, DefaultConstraint);
205    }
206
207    #[test]
208    fn backtracking_solves_diagonals_sudoku() {
209        let puzzle = "3x3;\
210             ,1,2,3,4,5,6,7, ,\
211             , , , , , , , , ,\
212             , , , , , , , , ,\
213            7, , , , , , , ,5,\
214            2, , , , , , , ,1,\
215            9, , , , , , , ,3,\
216             , , , , , , , , ,\
217             , , , , , , , , ,\
218             ,3,4,5,6,7,8,9, ";
219        let solution = "3x3;\
220            8,1,2,3,4,5,6,7,9,\
221            3,7,5,6,8,9,1,2,4,\
222            4,9,6,1,7,2,3,5,8,\
223            7,4,1,9,3,6,2,8,5,\
224            2,6,3,7,5,8,9,4,1,\
225            9,5,8,4,2,1,7,6,3,\
226            5,2,7,8,9,3,4,1,6,\
227            6,8,9,2,1,4,5,3,7,\
228            1,3,4,5,6,7,8,9,2";
229        test_solves_correctly(puzzle, solution,
230            CompositeConstraint::new(DefaultConstraint, DiagonalsConstraint));
231    }
232
233    #[test]
234    fn backtracking_solves_knights_move_sudoku() {
235        let puzzle = "3x3;\
236             ,8, ,1, ,5, , , ,\
237            4, ,7, ,9, , , , ,\
238             ,1, ,8, , , , , ,\
239            1, ,8, , , , , ,5,\
240             ,7, , , , , ,8, ,\
241            5, , , , , ,3, ,4,\
242             , , , , ,8, ,4, ,\
243             , , , ,3, ,8, ,6,\
244             , , ,5, ,4, ,3, ";
245        let solution = "3x3;\
246            2,8,3,1,4,5,6,9,7,\
247            4,5,7,3,9,6,1,2,8,\
248            9,1,6,8,2,7,4,5,3,\
249            1,3,8,4,7,2,9,6,5,\
250            6,7,4,9,5,3,2,8,1,\
251            5,2,9,6,8,1,3,7,4,\
252            3,9,1,7,6,8,5,4,2,\
253            7,4,5,2,3,9,8,1,6,\
254            8,6,2,5,1,4,7,3,9";
255        test_solves_correctly(puzzle, solution, CompositeConstraint::new(
256            DefaultConstraint, KnightsMoveConstraint));
257    }
258
259    #[test]
260    fn backtracking_solves_kings_move_sudoku() {
261        let puzzle = "3x3;\
262             , , , ,2,1, , , ,\
263             ,6,1, , , , ,3, ,\
264             , , , , ,4, ,7, ,\
265            3, ,7, , , , , , ,\
266            2, , , ,5, , , ,7,\
267             , , , , , ,5, ,8,\
268             ,8, ,1, , , , , ,\
269             ,3, , , , ,6,4, ,\
270             , , ,7,6, , , , ";
271        let solution = "3x3;\
272            5,7,3,9,2,1,4,8,6,\
273            4,6,1,5,8,7,2,3,9,\
274            8,2,9,6,3,4,1,7,5,\
275            3,5,7,2,1,8,9,6,4,\
276            2,9,8,4,5,6,3,1,7,\
277            1,4,6,3,7,9,5,2,8,\
278            6,8,5,1,4,2,7,9,3,\
279            7,3,2,8,9,5,6,4,1,\
280            9,1,4,7,6,3,8,5,2";
281
282        // Since the default constraint is enforced, KingsMoveConstraint and
283        // DiagonallyAdjacentConstraint should yield the same result.
284
285        test_solves_correctly(puzzle, solution,
286            CompositeConstraint::new(DefaultConstraint, KingsMoveConstraint));
287        test_solves_correctly(puzzle, solution, CompositeConstraint::new(
288            DefaultConstraint, DiagonallyAdjacentConstraint));
289    }
290
291    #[test]
292    fn backtracking_solves_adjacent_consecutive_sudoku() {
293        let puzzle = "3x3;\
294             , , , , , , , ,7,\
295             , ,3,8, , , , , ,\
296             ,4,6, , , , , , ,\
297             ,7, , ,2, , , , ,\
298             , , ,9,4,7, , , ,\
299             , , , ,8, , ,5, ,\
300             , , , , , , ,9, ,\
301             , , , , ,4,6,2, ,\
302            5, , , , , , , , ";
303        let solution = "3x3;\
304            2,5,8,4,1,6,9,3,7,\
305            7,1,3,8,5,9,2,6,4,\
306            9,4,6,3,7,2,5,8,1,\
307            3,7,1,6,2,5,8,4,9,\
308            8,2,5,9,4,7,3,1,6,\
309            4,6,9,1,8,3,7,5,2,\
310            6,8,2,7,3,1,4,9,5,\
311            1,3,7,5,9,4,6,2,8,\
312            5,9,4,2,6,8,1,7,3";
313        test_solves_correctly(puzzle, solution,CompositeConstraint::new(
314            DefaultConstraint, AdjacentConsecutiveConstraint));
315    }
316}
sudoku_variants/solver/mod.rs

sudoku_variants/solver/
mod.rs
