soku/solve/
brute_force.rs

1use crate::prelude::{Candidates, Coord, Digit, Sudoku, SudokuIndex, HOUSE_INDICES};
2
3use super::Solve;
4
5// TODO: tests
6// TODO: docs
7
8pub struct BruteForceSolver;
9
10impl BruteForceSolver {
11    pub const fn new() -> Self {
12        Self
13    }
14}
15
16impl Solve for BruteForceSolver {
17    fn solve(self, sudoku: &mut Sudoku) -> bool {
18        let all_candidates = sudoku.all_candidates();
19        Self::solve_inner(sudoku, all_candidates)
20        // measure!("Solver", {
21        //     let all_candidates = sudoku.all_candidates();
22        //     Self::solve_inner(sudoku, all_candidates)
23        // })
24    }
25}
26
27impl BruteForceSolver {
28    fn solve_inner(sudoku: &mut Sudoku, mut all_candidates: Vec<Candidates>) -> bool {
29        if let Some((index, candidates)) = Self::cell_with_least_candidates(sudoku, &all_candidates)
30        {
31            for digit in candidates.digits() {
32                sudoku.set_cell(index, digit);
33
34                Self::recalculate_all_candidates(&mut all_candidates, index, digit);
35
36                if Self::solve_inner(sudoku, all_candidates.clone()) {
37                    return true;
38                }
39            }
40
41            sudoku.clear_cell(index);
42
43            false
44        } else {
45            true
46        }
47    }
48
49    fn cell_with_least_candidates(
50        sudoku: &Sudoku,
51        all_candidates: &[Candidates],
52    ) -> Option<(usize, Candidates)> {
53        let mut best_candidates_count = usize::MAX;
54        let mut result = None;
55
56        for (i, _) in sudoku
57            .cells()
58            .enumerate()
59            .filter(|(_, cell)| cell.digit.is_none())
60        {
61            // let candidates = sudoku.cell_candidates(i);
62            let candidates = all_candidates[i];
63            let candidates_count = candidates.count();
64
65            if candidates_count < best_candidates_count {
66                best_candidates_count = candidates_count;
67                result = Some((i, candidates));
68
69                if best_candidates_count <= 1 {
70                    return result;
71                }
72            }
73        }
74
75        result
76    }
77
78    fn recalculate_all_candidates(all_candidates: &mut [Candidates], index: usize, digit: Digit) {
79        let coord @ Coord(row, col) = Coord::from_index(index);
80
81        // Remove digit from column
82        for r in HOUSE_INDICES {
83            if r != row {
84                let index = Coord(r, col).into_index();
85                all_candidates[index].remove(digit);
86            }
87        }
88
89        // Remove digit from column
90        for c in HOUSE_INDICES {
91            if c != col {
92                let index = Coord(row, c).into_index();
93                all_candidates[index].remove(digit);
94            }
95        }
96
97        for i in Sudoku::square_indices_of_cell(coord) {
98            if i != index {
99                all_candidates[i].remove(digit);
100            }
101        }
102    }
103}
soku/solve/brute_force.rs

soku/solve/
brute_force.rs
