lisudoku_solver/solver/logical_solver/
empty_reclanges.rs

1use std::mem::swap;
2use std::collections::HashMap;
3use itertools::Itertools;
4
5use crate::solver::Solver;
6use crate::types::{SolutionStep, Rule, Area, CellPosition};
7use super::technique::Technique;
8
9pub struct EmptyRectangles;
10
11// Finds boxes X is on a row and col
12impl Technique for EmptyRectangles {
13  fn get_rule(&self) -> Rule { Rule::EmptyRectangles }
14
15  fn run(&self, solver: &Solver) -> Vec<SolutionStep> {
16    if !solver.candidates_active {
17      return vec![]
18    }
19
20    let strong_links_by_value = solver.get_all_strong_links_by_value();
21
22    for region_area in solver.get_region_areas() {
23      let value_cells = solver.compute_cells_by_value_in_area(&region_area, &solver.candidates);
24
25      for (value, region_cells) in value_cells.into_iter().sorted() {
26        if region_cells.len() < 3 {
27          continue
28        }
29
30        let (selected_row, selected_col) = self.find_most_frequent_row_col(&region_cells);
31
32        // Check if all cells are on the row or column
33        if region_cells.iter().any(|cell| cell.row != selected_row && cell.col != selected_col) {
34          continue
35        }
36        // Check that not all of them are on the same row or col (that would be LockedCandidates)
37        if region_cells.iter().all(|cell| cell.row == selected_row) ||
38           region_cells.iter().all(|cell| cell.col == selected_col) {
39          continue
40        }
41
42        let empty_strong_links = vec![];
43        let strong_links = strong_links_by_value.get(&value).unwrap_or(&empty_strong_links);
44
45        // Search for strong links that see selected_row
46        for cell in solver.get_area_cells_with_candidate(&Area::Row(selected_row), value) {
47          if region_cells.contains(&cell) {
48            continue
49          }
50          let col = cell.col;
51
52          for (area, _, mut c1, mut c2) in strong_links {
53            if area != &Area::Column(col) || (c1.row != selected_row && c2.row != selected_row) {
54              continue
55            }
56
57            if c2.row == selected_row {
58              swap(&mut c1, &mut c2);
59            }
60
61            let common_cell = CellPosition::new(c2.row, selected_col);
62            if solver.grid[common_cell.row][common_cell.col] == 0 &&
63               solver.candidates[common_cell.row][common_cell.col].contains(&value) &&
64               !region_cells.contains(&common_cell) {
65              return vec![
66                self.build_solution_step(
67                  vec![ c1, c2 ], // the strong link
68                  vec![ value ],
69                  vec![ region_area, Area::Row(selected_row), Area::Column(selected_col) ],
70                  vec![ common_cell ],
71                )
72              ]
73            }
74          }
75        }
76
77        // Search for strong links that see selected_col
78        for cell in solver.get_area_cells_with_candidate(&Area::Column(selected_col), value) {
79          if region_cells.contains(&cell) {
80            continue
81          }
82          let row = cell.row;
83
84          for (area, _, mut c1, mut c2) in strong_links {
85            if area != &Area::Row(row) || (c1.col != selected_col && c2.col != selected_col) {
86              continue
87            }
88
89            if c2.col == selected_col {
90              swap(&mut c1, &mut c2);
91            }
92
93            let common_cell = CellPosition::new(selected_row, c2.col);
94            if solver.grid[common_cell.row][common_cell.col] == 0 &&
95               solver.candidates[common_cell.row][common_cell.col].contains(&value) &&
96               !region_cells.contains(&common_cell) {
97              return vec![
98                self.build_solution_step(
99                  vec![ c1, c2 ], // the strong link
100                  vec![ value ],
101                  vec![ region_area, Area::Row(selected_row), Area::Column(selected_col) ],
102                  vec![ common_cell ],
103                )
104              ]
105            }
106          }
107        }
108      }
109    }
110
111    vec![]
112  }
113}
114
115impl EmptyRectangles {
116  fn find_most_frequent_row_col(&self, cells: &Vec<CellPosition>) -> (usize, usize) {
117    let mut row_freq: HashMap<usize, u32> = HashMap::new();
118    let mut col_freq: HashMap<usize, u32> = HashMap::new();
119    for cell in cells {
120      let row_entry = row_freq.entry(cell.row).or_default();
121      *row_entry += 1;
122      let col_entry = col_freq.entry(cell.col).or_default();
123      *col_entry += 1;
124    }
125
126    let row = *row_freq.iter().max_by_key(|&(_, &freq)| freq).unwrap().0;
127    let col = *col_freq.iter().max_by_key(|&(_, &freq)| freq).unwrap().0;
128
129    (row, col)
130  }
131}
lisudoku_solver/solver/logical_solver/empty_reclanges.rs

lisudoku_solver/solver/logical_solver/
empty_reclanges.rs
