lisudoku_solver/solver/
brute_solver.rs

1use std::collections::HashSet;
2use crate::solver::Solver;
3use crate::types::{SudokuBruteSolveResult, Grid, SolutionType, CellPosition};
4
5impl Solver {
6  pub fn brute_solve(&mut self, use_logical: bool) -> SudokuBruteSolveResult {
7    // Not sure if there is value in running it without logical
8    assert!(use_logical);
9
10    let mut solution_count = 0;
11    self.recursive_check(&mut solution_count, use_logical, 1);
12
13    let res = SudokuBruteSolveResult {
14      solution_count,
15      solution: if let Some(grid) = &self.solution { Some(grid.to_vec()) } else { None },
16    };
17    res
18  }
19
20  pub fn recursive_check(&mut self, solution_count: &mut u32, use_logical: bool, depth: u32) {
21    let mut best_cell: Option<CellPosition> = None;
22    let mut best_candidates: HashSet<u32> = HashSet::new();
23
24    let mut original_grid: Option<Grid> = None;
25    if use_logical {
26      original_grid = Some(self.grid.to_vec());
27      // No need to store candidates, we will recompute
28      // Storing would complicate things and we need to do it for each candidate at each depth
29      self.candidates_active = false;
30      let result = self.logical_solve();
31      if result.solution_type == SolutionType::None {
32        self.grid = original_grid.unwrap();
33        return
34      }
35    }
36
37    for cell in self.get_all_empty_cells() {
38      let cell_candidates = self.compute_cell_candidates(&cell);
39      if best_cell.is_none() || cell_candidates.len() < best_candidates.len() {
40        best_cell = Some(cell);
41        best_candidates = cell_candidates;
42      }
43    }
44
45    if best_cell.is_none() {
46      self.solution = Some(self.grid.to_vec());
47      *solution_count += 1;
48    } else if !best_candidates.is_empty() {
49      for value in best_candidates.into_iter() {
50        let CellPosition { row: best_row, col: best_col } = best_cell.unwrap();
51        self.grid[best_row][best_col] = value;
52
53        // Currently we only run the solver with logical and because of
54        // rules that restrict candidates to valid ones we know <value> is valid
55        self.recursive_check(solution_count, use_logical, depth + 1);
56
57        self.grid[best_row][best_col] = 0;
58        if *solution_count > 1 {
59          break
60        }
61      }
62    }
63
64    if use_logical {
65      self.grid = original_grid.unwrap();
66    }
67  }
68}
lisudoku_solver/solver/brute_solver.rs

lisudoku_solver/solver/
brute_solver.rs
