lisudoku_solver/solver/logical_solver/
hidden_set.rs

1use std::collections::HashSet;
2use crate::solver::Solver;
3use crate::types::{CellPosition, InvalidStateReason, Rule, SolutionStep};
4use combinations::Combinations;
5use itertools::Itertools;
6use super::technique::Technique;
7
8// Within a house, X and Y are candidates in only 2 cells, so you can remove any other
9// candidate from those 2 cells.
10pub struct HiddenSet {
11  set_size: usize,
12}
13
14impl Technique for HiddenSet {
15  fn get_rule(&self) -> Rule { if self.set_size == 2 { Rule::HiddenPairs } else { Rule::HiddenTriples } }
16
17  fn run(&self, solver: &Solver) -> Vec<SolutionStep> {
18    if !solver.candidates_active {
19      return vec![]
20    }
21
22    let areas = solver.get_all_proper_areas();
23    for area in areas {
24      let value_cells = solver.compute_cells_by_value_in_area(&area, &solver.candidates);
25
26      let area_values: Vec<u32> = solver.compute_area_candidates_union(&area).into_iter().sorted().collect();
27      let value_combinations: Vec<_> = if self.set_size < area_values.len() {
28        Combinations::new(area_values, self.set_size).collect()
29      } else {
30        // Has to be handled separately because of stupid crate
31        vec![area_values]
32      };
33
34      for values in value_combinations {
35        let mut combined_cells: HashSet<CellPosition> = HashSet::new();
36        for value in &values {
37          let cells: HashSet<CellPosition> = value_cells[value].iter().copied().collect();
38          combined_cells = combined_cells.union(&cells).cloned().collect();
39          if combined_cells.len() > self.set_size {
40            break
41          }
42        }
43
44        if combined_cells.len() != self.set_size {
45          continue
46        }
47
48        let cells_array: Vec<CellPosition> = combined_cells.into_iter().sorted().collect();
49        let values_set: HashSet<u32> = values.iter().copied().collect();
50        if !solver.any_cells_with_other_candidates(&cells_array, &values_set) {
51          continue
52        }
53
54        return vec![
55          self.build_solution_step(
56            cells_array,
57            values,
58            vec![area],
59            vec![],
60          )
61        ]
62      }
63    }
64
65    vec![]
66  }
67
68  fn apply(&self, step: &SolutionStep, solver: &mut Solver) -> (bool, Option<InvalidStateReason>) {
69    for &CellPosition { row, col } in &step.cells {
70      let value_set: HashSet<u32> = step.values.iter().copied().collect();
71      solver.candidates[row][col] = solver.candidates[row][col].intersection(&value_set).copied().collect();
72    }
73    (true, None)
74  }
75}
76
77impl HiddenSet {
78  pub fn new(set_size: usize) -> HiddenSet {
79    HiddenSet { set_size }
80  }
81}
lisudoku_solver/solver/logical_solver/hidden_set.rs

lisudoku_solver/solver/logical_solver/
hidden_set.rs
