lisudoku_solver/solver/logical_solver/
advanced_candidates.rs

1use crate::solver::Solver;
2use crate::types::CellPosition;
3use std::collections::{HashSet, HashMap};
4use std::ops::{BitOrAssign, BitAnd};
5use super::combinations::cell_combination_logic::CellsCacheKey;
6
7pub type CellEliminationsResult = Vec<(CellPosition, Vec<u32>)>;
8
9impl Solver {
10  // Eliminate combinations that remove all candidates from any cells
11  // Returns cells that need to be updated
12  pub fn eliminate_combinations(&self, combinations: &Vec<Vec<u32>>, cells: &Vec<CellPosition>) -> CellEliminationsResult {
13    let cache_key: CellsCacheKey = self.cells_to_cache_key(cells);
14    if let Some(cached_result) = self.cell_eliminations_cache.borrow().get(&cache_key) {
15      return cached_result.to_owned()
16    }
17
18    let cell_peers: Vec<Vec<CellPosition>> = cells.iter().map(|cell| {
19      self.get_cell_peers(cell, true)
20    }).collect();
21
22    let gs = self.constraints.grid_size;
23    let cand_sets: Vec<Vec<u32>> = (0..gs).map(|row| {
24      (0..gs).map(|col| {
25        self.candidates_to_set(CellPosition::new(row, col))
26      }).collect()
27    }).collect();
28
29    let valid_combinations: Vec<&Vec<u32>> = combinations.iter().filter(|combination| {
30      let mut changed_cells: HashMap<CellPosition, u32> = HashMap::new();
31      for cell_index in 0..cells.len() {
32        let cell_value = combination[cell_index];
33        for peer_cell in &cell_peers[cell_index] {
34          if cand_sets[peer_cell.row][peer_cell.col].bitand(1 << cell_value) != 0 {
35            let entry = changed_cells.entry(*peer_cell).or_default();
36            entry.bitor_assign(1 << cell_value);
37          }
38        }
39      }
40      changed_cells.into_iter().all(|(cell, candidate_updates)| {
41        candidate_updates != cand_sets[cell.row][cell.col]
42      })
43    }).collect();
44
45    let mut valid_candidates: Vec<HashSet<u32>> = vec![ HashSet::new(); cells.len() ];
46    for combination in valid_combinations {
47      for (cell_index, &candidate) in combination.iter().enumerate() {
48        valid_candidates[cell_index].insert(candidate);
49      }
50    }
51
52    let result = self.cell_candidates_diff(cells, valid_candidates);
53
54    self.cell_eliminations_cache.borrow_mut().insert(cache_key, result.to_vec());
55
56    result
57  }
58}
lisudoku_solver/solver/logical_solver/advanced_candidates.rs

lisudoku_solver/solver/logical_solver/
advanced_candidates.rs
