sudoku_variants/solver/strategy/
solvers.rs

1//! This module defines different [Solver]s related to strategies, in
2//! particular the partial [StrategicSolver] and the perfect
3//! [StrategicBacktrackingSolver]. All of them are re-exported in
4//! [crate::solver::strategy], so you should not have to `use` anything from
5//! this module directly.
6
7use crate::Sudoku;
8use crate::constraint::Constraint;
9use crate::solver::{Solution, Solver};
10use crate::solver::strategy::{Strategy, SudokuInfo};
11
12/// A partial [Solver] which uses a [Strategy] to solve a Sudoku as well as
13/// possible. If it finds a contradiction, it will conclude that the Sudoku is
14/// impossible. If it cannot solve it, it will resort to returning
15/// `Solution::Ambiguous`. Only if the wrapped strategy is able to solve the
16/// Sudoku completely, a `Solution::Unique` variant is returned.
17pub struct StrategicSolver<S: Strategy> {
18    strategy: S
19}
20
21impl<S: Strategy> StrategicSolver<S> {
22
23    /// Creates a new strategic solver that uses the given `strategy` to
24    /// attempt to solve Sudoku.
25    pub fn new(strategy: S) -> StrategicSolver<S> {
26        StrategicSolver { strategy }
27    }
28}
29
30impl<S: Strategy> Solver for StrategicSolver<S> {
31    fn solve(&self, sudoku: &Sudoku<impl Constraint + Clone>) -> Solution {
32        let mut sudoku_info = SudokuInfo::from_sudoku(sudoku.clone());
33
34        while !sudoku_info.sudoku().grid().is_full() &&
35            self.strategy.apply(&mut sudoku_info) { }
36
37        if !sudoku_info.sudoku().is_valid() {
38            Solution::Impossible
39        }
40        else if sudoku_info.sudoku().grid().is_full() {
41            Solution::Unique(sudoku_info.sudoku().grid().clone())
42        }
43        else if sudoku_info.cell_options().iter().any(|c| c.is_empty()) {
44            Solution::Impossible
45        }
46        else {
47            Solution::Ambiguous
48        }
49    }
50}
51
52impl<S: Strategy + Clone> Clone for StrategicSolver<S> {
53    fn clone(&self) -> Self {
54        StrategicSolver::new(self.strategy.clone())
55    }
56}
57
58/// A perfect [Solver] which uses a [Strategy] to accelerate the solving
59/// process. Under the assumption that the strategy is correct, this should
60/// yield the same result as a
61/// [BacktrackingSolver](crate::solver::BacktrackingSolver). Note that using a
62/// complicated strategy can also reduce performance if its utility is too low.
63pub struct StrategicBacktrackingSolver<S: Strategy> {
64    strategy: S
65}
66
67/// Finds the cell for which there are the fewest options and returns its
68/// coordinates in the form `(column, row)`.
69fn find_min_options<C: Constraint + Clone>(sudoku_info: &mut SudokuInfo<C>)
70        -> (usize, usize) {
71    let size = sudoku_info.size();
72    let mut min_options_column = 0usize;
73    let mut min_options_row = 0usize;
74    let mut min_options = size + 1;
75
76    for row in 0..size {
77        for column in 0..size {
78            let cell = sudoku_info.get_cell(column, row).unwrap();
79            let options = sudoku_info.get_options(column, row).unwrap();
80
81            if cell == None && options.len() < min_options {
82                min_options_column = column;
83                min_options_row = row;
84                min_options = options.len();
85            }
86        }
87    }
88
89    (min_options_column, min_options_row)
90}
91
92fn to_solution(sudoku: &Sudoku<impl Constraint + Clone>) -> Option<Solution> {
93    if sudoku.grid().is_full() {
94        if sudoku.is_valid() {
95            Some(Solution::Unique(sudoku.grid().clone()))
96        }
97        else {
98            Some(Solution::Impossible)
99        }
100    }
101    else {
102        None
103    }
104}
105
106impl<S: Strategy> StrategicBacktrackingSolver<S> {
107
108    /// Creates a new strategic backtracing solver that uses the given
109    /// `strategy`.
110    pub fn new(strategy: S) -> StrategicBacktrackingSolver<S> {
111        StrategicBacktrackingSolver { strategy }
112    }
113
114    fn solve_rec(&self, sudoku_info: &mut SudokuInfo<impl Constraint + Clone>) -> Solution {
115        while {
116            if let Some(solution) = to_solution(sudoku_info.sudoku()) {
117                return solution;
118            }
119
120            self.strategy.apply(sudoku_info)
121        } { }
122
123        let (min_options_column, min_options_row) =
124            find_min_options(sudoku_info);
125        let options = sudoku_info
126            .get_options(min_options_column, min_options_row)
127            .unwrap()
128            .iter();
129        let mut solution = Solution::Impossible;
130
131        for number in options {
132            let mut sudoku_info = sudoku_info.clone();
133            sudoku_info.enter_cell(min_options_column, min_options_row, number)
134                .unwrap();
135            let next_solution = self.solve_rec(&mut sudoku_info);
136            solution = solution.union(next_solution);
137
138            if solution == Solution::Ambiguous {
139                break;
140            }
141        }
142
143        solution
144    }
145}
146
147impl<S: Strategy> Solver for StrategicBacktrackingSolver<S> {
148    fn solve(&self, sudoku: &Sudoku<impl Constraint + Clone>) -> Solution {
149        self.solve_rec(&mut SudokuInfo::from_sudoku(sudoku.clone()))
150    }
151}
152
153#[cfg(test)]
154mod tests {
155
156    use super::*;
157
158    use crate::SudokuGrid;
159    use crate::constraint::{
160        AdjacentConsecutiveConstraint,
161        CompositeConstraint,
162        DefaultConstraint,
163        DiagonalsConstraint,
164        KingsMoveConstraint,
165        KnightsMoveConstraint
166    };
167    use crate::solver::strategy::{
168        BoundedOptionsBacktrackingStrategy,
169        BoundedCellsBacktrackingStrategy,
170        CompositeStrategy,
171        NakedSingleStrategy,
172        OnlyCellStrategy,
173        TupleStrategy
174    };
175
176    fn naked_single_strategy_solver() -> StrategicSolver<impl Strategy> {
177        StrategicSolver::new(NakedSingleStrategy)
178    }
179
180    fn only_cell_strategy_solver() -> StrategicSolver<impl Strategy> {
181        StrategicSolver::new(OnlyCellStrategy)
182    }
183
184    fn complex_strategy_solver() -> StrategicSolver<impl Strategy> {
185        let strategy = CompositeStrategy::new(NakedSingleStrategy,
186            CompositeStrategy::new(OnlyCellStrategy,
187                CompositeStrategy::new(TupleStrategy::new(|_| 7),
188                    CompositeStrategy::new(
189                        BoundedOptionsBacktrackingStrategy::new(|_| 2,
190                            |_| Some(1), OnlyCellStrategy),
191                        BoundedCellsBacktrackingStrategy::new(|_| 2,
192                            |_| Some(1), OnlyCellStrategy)))));
193        StrategicSolver::new(strategy)
194    }
195
196    fn complex_strategic_backtracking_solver()
197            -> StrategicBacktrackingSolver<impl Strategy> {
198        // This solver is used in the benchmark, where an error was found.
199
200        StrategicBacktrackingSolver::new(CompositeStrategy::new(
201            CompositeStrategy::new(
202                NakedSingleStrategy, OnlyCellStrategy),
203            CompositeStrategy::new(
204                TupleStrategy::new(|size| size - 2),
205                CompositeStrategy::new(
206                    BoundedCellsBacktrackingStrategy::new(|size| size - 2,
207                        |_| Some(1), OnlyCellStrategy),
208                    BoundedOptionsBacktrackingStrategy::new(|_| 2,
209                        |_| Some(1), CompositeStrategy::new(
210                            NakedSingleStrategy, OnlyCellStrategy
211                        )
212                    )
213                )
214            )
215        ))
216    }
217
218    fn difficult_sudoku() -> Sudoku<DefaultConstraint> {
219        // This Sudoku is taken from the World Puzzle Federation Sudoku GP 2020
220        // Round 5 Puzzle 5
221        // Puzzle: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2020/2020_SudokuRound5.pdf
222        // Solution: https://gp.worldpuzzle.org/sites/default/files/Puzzles/2020/2020_SudokuRound5_SB.pdf
223        // The naked single strategy is insufficient to solve this puzzle.
224
225        Sudoku::parse("3x3;\
226             ,5, ,3, , , ,7, ,\
227            1, , , ,2, ,8, , ,\
228             ,2, ,4, ,9, , , ,\
229             , ,3,1, , ,7, ,6,\
230             ,4, , ,6, , ,5, ,\
231            5, ,6, , ,3,4, , ,\
232             , , ,8, ,2, ,3, ,\
233             , ,7, ,9, , , ,2,\
234             ,6, , , ,1, ,8, ", DefaultConstraint).unwrap()
235    }
236
237    fn assert_can_solve_difficult_sudoku(solver: impl Solver) {
238        let sudoku = difficult_sudoku();
239        let solution = solver.solve(&sudoku);
240        let expected = Solution::Unique(SudokuGrid::parse("3x3;\
241            6,5,4,3,1,8,2,7,9,\
242            1,3,9,7,2,6,8,4,5,\
243            7,2,8,4,5,9,1,6,3,\
244            8,9,3,1,4,5,7,2,6,\
245            2,4,1,9,6,7,3,5,8,\
246            5,7,6,2,8,3,4,9,1,\
247            9,1,5,8,7,2,6,3,4,\
248            3,8,7,6,9,4,5,1,2,\
249            4,6,2,5,3,1,9,8,7").unwrap());
250
251        assert_eq!(expected, solution);
252    }
253
254    #[test]
255    fn naked_single_strategy_solves_uniquely() {
256        let sudoku = Sudoku::parse("3x3;\
257             , ,1, , ,7,3,6, ,\
258            7,2, , ,8, ,5, ,9,\
259             ,8, , ,3,1, , , ,\
260             , , ,6,7, , ,3,5,\
261            9, ,5,8, , , ,7, ,\
262            2,6, , ,1, , , ,4,\
263            3, , ,1,5, , ,4,6,\
264             ,7,4, , ,3, ,5,2,\
265            5,1, ,7, ,4,8, , ", DefaultConstraint).unwrap();
266        let solution = naked_single_strategy_solver().solve(&sudoku);
267        let expected = Solution::Unique(SudokuGrid::parse("3x3;\
268            4,5,1,2,9,7,3,6,8,\
269            7,2,3,4,8,6,5,1,9,\
270            6,8,9,5,3,1,4,2,7,\
271            1,4,8,6,7,9,2,3,5,\
272            9,3,5,8,4,2,6,7,1,\
273            2,6,7,3,1,5,9,8,4,\
274            3,9,2,1,5,8,7,4,6,\
275            8,7,4,9,6,3,1,5,2,\
276            5,1,6,7,2,4,8,9,3").unwrap());
277
278        assert_eq!(expected, solution);
279    }
280
281    #[test]
282    fn naked_single_strategy_detects_impossibility() {
283        let sudoku = Sudoku::parse("3x3;\
284             , , , , , ,1, , ,\
285             , , , , , ,2, , ,\
286             , , , , , ,3, , ,\
287             , , , , , , , , ,\
288            1,2,3,4,5,6,7, , ,\
289             , , , , , ,4, , ,\
290            3,1,2,6,7,9, ,8, ,\
291             , , , , , ,6, , ,\
292             , , , , , ,9, , ", DefaultConstraint).unwrap();
293        let solution = naked_single_strategy_solver().solve(&sudoku);
294
295        assert_eq!(Solution::Impossible, solution);
296    }
297
298    #[test]
299    fn naked_single_strategy_unable_to_solve() {
300        let sudoku = difficult_sudoku();
301        let solution = naked_single_strategy_solver().solve(&sudoku);
302
303        assert_eq!(Solution::Ambiguous, solution);
304    }
305
306    #[test]
307    fn only_cell_strategy_solves_uniquely() {
308        let sudoku = Sudoku::parse("3x3;\
309             ,1, ,2, , ,7, ,9,\
310             , ,6, ,8, ,3, , ,\
311            8,2, , ,1,3, ,4,6,\
312            4, ,5, ,7, ,6, ,1,\
313            2,7,1,6, , , ,5, ,\
314             ,9, , ,3, , , , ,\
315             ,4, , ,5,8, ,6,7,\
316            5, ,3,9,4, , ,2,8,\
317            9,8, , , ,6,4,3, ", DefaultConstraint).unwrap();
318        let solution = only_cell_strategy_solver().solve(&sudoku);
319        let expected = Solution::Unique(SudokuGrid::parse("3x3;\
320            3,1,4,2,6,5,7,8,9,\
321            7,5,6,4,8,9,3,1,2,\
322            8,2,9,7,1,3,5,4,6,\
323            4,3,5,8,7,2,6,9,1,\
324            2,7,1,6,9,4,8,5,3,\
325            6,9,8,5,3,1,2,7,4,\
326            1,4,2,3,5,8,9,6,7,\
327            5,6,3,9,4,7,1,2,8,\
328            9,8,7,1,2,6,4,3,5").unwrap());
329
330        assert_eq!(expected, solution);
331    }
332
333    #[test]
334    fn strategic_backtracking_more_powerful() {
335        let solver = StrategicBacktrackingSolver::new(NakedSingleStrategy);
336        assert_can_solve_difficult_sudoku(solver);
337    }
338
339    #[test]
340    fn complex_strategy_solves_difficult_sudoku() {
341        let solver = complex_strategy_solver();
342        assert_can_solve_difficult_sudoku(solver);
343    }
344
345    #[test]
346    fn complex_strategic_backtracking_is_sound_default() {
347        let sudoku = Sudoku::parse("3x3;
348             , , , , ,7,3, , ,\
349             ,1,2, , , ,5,4, ,\
350             , ,3,4, , , ,1, ,\
351             , ,5,6, , , ,8, ,\
352             , , , , , , , , ,\
353            7, , , , ,2,4, , ,\
354            6,4,1, , , ,8, , ,\
355            5,3, , , ,6,7, , ,\
356             , , , , ,9, , , ", DefaultConstraint).unwrap();
357        let solution = complex_strategic_backtracking_solver().solve(&sudoku);
358        let expected = Solution::Unique(SudokuGrid::parse("3x3;
359            4,5,6,2,1,7,3,9,8,\
360            8,1,2,9,6,3,5,4,7,\
361            9,7,3,4,5,8,6,1,2,\
362            1,2,5,6,7,4,9,8,3,\
363            3,6,4,8,9,1,2,7,5,\
364            7,9,8,5,3,2,4,6,1,\
365            6,4,1,7,2,5,8,3,9,\
366            5,3,9,1,8,6,7,2,4,\
367            2,8,7,3,4,9,1,5,6").unwrap());
368
369        assert_eq!(expected, solution);
370    }
371
372    #[test]
373    fn complex_strategic_backtracking_is_sound_diagonals() {
374        let sudoku = Sudoku::parse("3x3;
375             , , , ,3, , , , ,\
376             , , ,7, ,6, , , ,\
377             , ,4, , , ,2, , ,\
378             ,4, , , , , ,1, ,\
379            1, , , , , , , ,6,\
380             ,2, , , , , ,7, ,\
381             , ,9, , , ,5, , ,\
382             , , ,2, ,1, , , ,\
383             , , , ,7, , , , ",
384            CompositeConstraint::new(DefaultConstraint, DiagonalsConstraint))
385            .unwrap();
386        let solution = complex_strategic_backtracking_solver().solve(&sudoku);
387        let expected = Solution::Unique(SudokuGrid::parse("3x3;
388            7,9,6,5,3,2,1,8,4,\
389            8,1,2,7,4,6,3,5,9,\
390            5,3,4,9,1,8,2,6,7,\
391            9,4,3,6,2,7,8,1,5,\
392            1,5,7,3,8,4,9,2,6,\
393            6,2,8,1,5,9,4,7,3,\
394            2,7,9,8,6,3,5,4,1,\
395            4,6,5,2,9,1,7,3,8,\
396            3,8,1,4,7,5,6,9,2").unwrap());
397
398        assert_eq!(expected, solution);
399    }
400
401    #[test]
402    fn complex_strategic_backtracking_is_sound_knights_move() {
403        let sudoku = Sudoku::parse("3x3;
404            5,3, , , , , ,8,7,\
405            1, , , , , , , ,9,\
406             , , ,7, ,2, , , ,\
407             , , , , ,4,7, , ,\
408             , , , , , , , , ,\
409             , ,4,6, , , , , ,\
410             , , ,3, ,8, , , ,\
411            7, , , , , , , ,2,\
412            9,4, , , , , ,3,5",
413            CompositeConstraint::new(DefaultConstraint, KnightsMoveConstraint))
414            .unwrap();
415        let solution = complex_strategic_backtracking_solver().solve(&sudoku);
416        let expected = Solution::Unique(SudokuGrid::parse("3x3;
417            5,3,2,4,9,1,6,8,7,\
418            1,8,7,5,3,6,2,4,9,\
419            4,9,6,7,8,2,5,1,3,\
420            3,6,9,8,2,4,7,5,1,\
421            8,7,5,9,1,3,4,2,6,\
422            2,1,4,6,7,5,3,9,8,\
423            6,2,1,3,5,8,9,7,4,\
424            7,5,3,1,4,9,8,6,2,\
425            9,4,8,2,6,7,1,3,5").unwrap());
426
427        assert_eq!(expected, solution);
428    }
429
430    #[test]
431    fn complex_strategic_backtracking_is_sound_kings_move() {
432        let sudoku = Sudoku::parse("3x3;
433             ,8, , , , , ,9, ,\
434            3,2, , , , , ,5,4,\
435             , , ,2, ,5, , , ,\
436             , ,7,8, ,6,4, , ,\
437             , , , , , , , , ,\
438             , ,6,3, ,1,9, , ,\
439             , , ,7, ,8, , , ,\
440            4,7, , , , , ,6,5,\
441             ,9, , , , , ,1, ",
442            CompositeConstraint::new(DefaultConstraint, KingsMoveConstraint))
443            .unwrap();
444        let solution = complex_strategic_backtracking_solver().solve(&sudoku);
445        let expected = Solution::Unique(SudokuGrid::parse("3x3;
446            7,8,5,6,4,3,1,9,2,\
447            3,2,1,9,8,7,6,5,4,\
448            9,6,4,2,1,5,8,7,3,\
449            5,3,7,8,9,6,4,2,1,\
450            8,1,9,4,7,2,5,3,6,\
451            2,4,6,3,5,1,9,8,7,\
452            1,5,2,7,6,8,3,4,9,\
453            4,7,8,1,3,9,2,6,5,\
454            6,9,3,5,2,4,7,1,8").unwrap());
455
456        assert_eq!(expected, solution);
457    }
458
459    #[test]
460    fn complex_strategic_backtracking_is_sound_adjacent_consecutive() {
461        let sudoku = Sudoku::parse("3x3;
462             , , , , , , , , ,\
463             , , , ,4, , , , ,\
464             , ,7, ,6, ,5, , ,\
465             , , , ,1, , , , ,\
466             ,9,4,8, ,5,2,6, ,\
467             , , , ,9, , , , ,\
468             , ,1, ,2, ,4, , ,\
469             , , , ,8, , , , ,\
470             , , , , , , , , ",
471            CompositeConstraint::new(DefaultConstraint, 
472                AdjacentConsecutiveConstraint))
473            .unwrap();
474        let solution = complex_strategic_backtracking_solver().solve(&sudoku);
475        let expected = Solution::Unique(SudokuGrid::parse("3x3;
476            2,4,9,5,7,3,8,1,6,
477            6,1,5,2,4,8,3,7,9,
478            8,3,7,9,6,1,5,2,4,
479            3,5,2,6,1,7,9,4,8,
480            7,9,4,8,3,5,2,6,1,
481            1,6,8,4,9,2,7,3,5,
482            5,8,1,7,2,6,4,9,3,
483            9,2,6,3,8,4,1,5,7,
484            4,7,3,1,5,9,6,8,2").unwrap());
485
486        assert_eq!(expected, solution);
487    }
488}
sudoku_variants/solver/strategy/solvers.rs

sudoku_variants/solver/strategy/
solvers.rs
