lisudoku_solver/solver/logical_solver/
common_peer_elimination.rs

1use crate::solver::Solver;
2use crate::types::{SolutionStep, CellPosition, Rule, Area};
3use std::collections::{HashSet, HashMap};
4use itertools::Itertools;
5use super::technique::Technique;
6
7// Cell can’t be X because it eliminates all X candidates from a region
8// It is a more general version of the Locked Candidates
9// For diagonal puzzles the rule applied on the is called Crossover
10// For antiknight puzzles the rule is called L technique
11pub struct CommonPeerElimination;
12
13impl Technique for CommonPeerElimination {
14  fn get_rule(&self) -> Rule { Rule::CommonPeerElimination }
15
16  fn run(&self, solver: &Solver) -> Vec<SolutionStep> {
17    if !solver.candidates_active {
18      return vec![]
19    }
20
21    for area in solver.get_all_proper_areas() {
22      let cells_by_value = solver.compute_cells_by_value_in_area(&area, &solver.candidates);
23      for (value, cells) in cells_by_value.into_iter().sorted() {
24        let step = self.find_common_peer_elimination_cells_with_value(solver, &area, cells, value);
25        if step.is_some() {
26          return vec![ step.unwrap() ]
27        }
28      }
29    }
30
31    vec![]
32  }
33}
34
35impl CommonPeerElimination {
36  fn find_common_peer_elimination_cells_with_value(&self, solver: &Solver, area: &Area, cells: Vec<CellPosition>, value: u32) -> Option<SolutionStep> {
37    let values: HashSet<u32> = HashSet::from([value]);
38    let affected_cells: Vec<CellPosition> = self.find_common_peers_for_cells_with_values(solver, &cells, &values);
39
40    if affected_cells.is_empty() {
41      return None
42    }
43
44    Some(
45      self.build_solution_step(
46        cells,
47        vec![ value ],
48        vec![ area.clone() ],
49        affected_cells,
50      )
51    )
52  }
53
54  fn find_common_peers_for_cells_with_values(&self, solver: &Solver, cells: &Vec<CellPosition>, values: &HashSet<u32>) -> Vec<CellPosition> {
55    let common_peers = Self::find_common_peers_for_cells(solver, cells);
56    let common_peers_with_values: Vec<CellPosition> = solver.filter_cells_with_any_candidates(
57      &common_peers, &values
58    );
59    common_peers_with_values
60  }
61
62  pub fn find_common_peers_for_cells(solver: &Solver, cells: &Vec<CellPosition>) -> Vec<CellPosition> {
63    let mut peer_counts = vec![ vec![ 0; solver.constraints.grid_size ]; solver.constraints.grid_size ];
64    for cell in cells {
65      for CellPosition { row, col } in solver.get_cell_peers(cell, true) {
66        peer_counts[row][col] += 1;
67      }
68    }
69    for &CellPosition { row, col } in cells {
70      peer_counts[row][col] = 0;
71    }
72    let common_peers: Vec<CellPosition> = solver.get_empty_area_cells(&Area::Grid)
73      .into_iter()
74      .filter(|&cell| peer_counts[cell.row][cell.col] == cells.len())
75      .collect();
76
77    common_peers
78  }
79
80  // TODO: remove after refactoring kropki
81  pub fn find_common_peers_for_cells_with_subset_values(solver: &Solver, cells: &Vec<CellPosition>, values: &HashSet<u32>) -> Vec<CellPosition> {
82    let common_peers = Self::find_common_peers_for_cells(solver, cells);
83    let common_peers_with_values: Vec<CellPosition> = solver.filter_cells_with_subset_candidates(&common_peers, &values);
84    common_peers_with_values
85  }
86
87  pub fn find_cell_eliminations(cells: Vec<CellPosition>, combinations: Vec<Vec<u32>>, solver: &Solver) -> Vec<(CellPosition, u32)> {
88    let cell_peers: Vec<Vec<CellPosition>> = cells.iter().map(|cell| {
89      solver.get_cell_peers(cell, true)
90    }).collect();
91
92    let mut cell_eliminations: HashSet<(CellPosition, u32)> = HashSet::new();
93
94    for (idx, combination) in combinations.iter().enumerate() {
95      let mut changed_cells: HashMap<CellPosition, HashSet<u32>> = HashMap::new();
96      for cell_index in 0..cells.len() {
97        let cell_value = combination[cell_index];
98        for peer_cell in &cell_peers[cell_index] {
99          if solver.candidates[peer_cell.row][peer_cell.col].contains(&cell_value) {
100            let entry = changed_cells.entry(*peer_cell).or_insert(HashSet::new());
101            entry.insert(cell_value);
102          }
103        }
104      }
105
106      let updates: HashSet<(CellPosition, u32)> = changed_cells.into_iter().flat_map(|(cell, candidates)| {
107        candidates.into_iter().map(|c| (cell, c)).collect::<Vec<_>>()
108      }).collect();
109
110      if idx == 0 {
111        cell_eliminations = updates;
112      } else {
113        cell_eliminations = cell_eliminations.intersection(&updates).copied().collect();
114      }
115    }
116
117    cell_eliminations.into_iter().sorted().collect_vec()
118  }
119}
lisudoku_solver/solver/logical_solver/common_peer_elimination.rs

lisudoku_solver/solver/logical_solver/
common_peer_elimination.rs
