lisudoku_solver/
types.rs

1use std::fmt::{self, Display, Debug};
2use itertools::Itertools;
3use serde::{Serialize, Deserialize};
4
5#[derive(Serialize, Deserialize, Debug, Clone)]
6pub struct SudokuConstraints {
7  pub grid_size: usize,
8  pub fixed_numbers: Vec<FixedNumber>,
9  pub regions: Vec<Region>,
10  pub extra_regions: Vec<Region>,
11  pub killer_cages: Vec<KillerCage>,
12  pub thermos: Vec<Thermo>,
13  pub arrows: Vec<Arrow>,
14  pub primary_diagonal: bool,
15  pub secondary_diagonal: bool,
16  pub anti_knight: bool,
17  pub anti_king: bool,
18  pub kropki_dots: Vec<KropkiDot>,
19  pub kropki_negative: bool,
20  pub odd_cells: Vec<CellPosition>,
21  pub even_cells: Vec<CellPosition>,
22  pub top_bottom: bool,
23  pub renbans: Vec<Renban>,
24  pub palindromes: Vec<Palindrome>,
25}
26
27#[derive(Serialize, Deserialize, Debug, Copy, Clone, PartialEq)]
28pub struct FixedNumber {
29  pub position: CellPosition,
30  pub value: u32,
31}
32
33#[derive(Serialize, Deserialize, Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
34pub struct CellPosition {
35  pub row: usize,
36  pub col: usize,
37}
38
39impl CellPosition {
40  pub fn new(row: usize, col: usize) -> CellPosition {
41    CellPosition {
42      row,
43      col,
44    }
45  }
46
47  pub fn to_string(&self) -> String {
48    format!("R{}C{}", self.row + 1, self.col + 1)
49  }
50}
51
52#[derive(Serialize, Deserialize, Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
53pub struct CellDirection {
54  pub row: isize,
55  pub col: isize,
56}
57
58pub type Region = Vec<CellPosition>;
59
60pub type Grid = Vec<Vec<u32>>;
61
62#[derive(Serialize, Deserialize, Debug, Clone)]
63pub struct KillerCage {
64  pub sum: Option<u32>,
65  pub region: Region,
66}
67
68#[derive(Serialize, Deserialize, Debug, Clone)]
69pub struct KropkiDot {
70  pub dot_type: KropkiDotType,
71  pub cell_1: CellPosition,
72  pub cell_2: CellPosition,
73}
74
75#[derive(Serialize, Deserialize, Debug, PartialEq, Clone)]
76pub enum KropkiDotType {
77  Consecutive,
78  Double,
79  Negative,
80}
81
82#[derive(Serialize, Deserialize, Debug)]
83pub struct SudokuGrid {
84  pub values: Grid,
85}
86
87#[derive(Serialize, Deserialize, Debug)]
88pub struct SudokulogicalSolveResult {
89  pub solution_type: SolutionType,
90  pub solution: Option<Grid>,
91  pub steps: Vec<SolutionStep>,
92  pub invalid_state_reason: Option<InvalidStateReason>,
93}
94
95#[derive(Serialize, Deserialize, Debug, PartialEq)]
96pub enum SolutionType {
97  Full,
98  Partial,
99  None,
100}
101
102#[derive(Serialize, Deserialize, Debug, PartialEq, Clone)]
103pub struct InvalidStateReason {
104  pub state_type: InvalidStateType,
105  pub area: Area,
106  pub values: Vec<u32>,
107}
108
109#[derive(Serialize, Deserialize, Debug, PartialEq, Clone)]
110pub enum InvalidStateType {
111  CellNoCandidates,
112  CellEmpty,
113  CellInvalidValue,
114  AreaValueConflict,
115  AreaCandidates,
116  AreaConstraint,
117}
118
119#[derive(Serialize, Deserialize, Debug)]
120pub struct SudokuBruteSolveResult {
121  pub solution_count: u32,
122  pub solution: Option<Grid>,
123}
124
125#[derive(Serialize, Deserialize, Debug, Clone)]
126pub struct SolutionStep {
127  pub rule: Rule,
128  // Used for grid steps (the first cell should have <value>) or e.g. Rule::XWing to
129  // show which cells build the X shape
130  pub cells: Vec<CellPosition>,
131  // The meaning can vary between rules
132  pub values: Vec<u32>,
133  // Used in rules that are applies inside an area. Could be multiple e.g. Rule::XWing
134  pub areas: Vec<Area>,
135  // Used for non-grid steps. The meaning can vary between rules,
136  // but we will remove candidates from these cells.
137  pub affected_cells: Vec<CellPosition>,
138  // Used for Rule::Candidates
139  pub candidates: Option<Vec<Vec<Vec<u32>>>>,
140  // Used for Rule::NishioForcingChains
141  pub invalid_state_reason: Option<InvalidStateReason>,
142}
143
144#[derive(Serialize, Deserialize, Debug, PartialEq, Copy, Clone, Eq, Hash)]
145pub enum Rule {
146  // Easy
147  NakedSingle, // 1 Cell Position, 1 value + who it is constrained by
148  HiddenSingle, // 1 Cell Position, 1 value, the row/col/region + who it is constrained by
149  Thermo,
150  Kropki,
151  Candidates,
152  AdvancedCandidates,
153  ThermoCandidates,
154  KillerCandidates,
155  ArrowCandidates,
156  RenbanCandidates,
157  PalindromeValues,
158  PalindromeCandidates,
159  // Medium
160  ArrowAdvancedCandidates,
161  Killer45,
162  KropkiChainCandidates,
163  KropkiAdvancedCandidates,
164  TopBottomCandidates,
165  LockedCandidatesPairs, // 2 CellPositions + what they affect
166  NakedPairs, // 2 Cell Positions, 2 values + what they affect
167  HiddenPairs,
168  // Hard
169  CommonPeerElimination, // cells = have common peers, affected_cells = would eliminate them
170  CommonPeerEliminationKropki,
171  CommonPeerEliminationArrow,
172  LockedCandidatesTriples,
173  NakedTriples, // 2 Cell Positions, 2 values + what they affect
174  HiddenTriples,
175  XWing,
176  XYWing,
177  Swordfish, // ???
178  TurbotFish,
179  EmptyRectangles,
180  AdhocNakedSet,
181  PhistomefelRing,
182  NishioForcingChains,
183}
184
185#[derive(Serialize, Deserialize, Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
186pub enum Area {
187  Grid,
188  Adhoc(Vec<CellPosition>),
189  Cell(usize, usize),
190  Row(usize),
191  Column(usize),
192  Region(usize),
193  Thermo(usize),
194  Arrow(usize),
195  KillerCage(usize),
196  KropkiDot(usize),
197  PrimaryDiagonal,
198  SecondaryDiagonal,
199  Renban(usize),
200  Palindrome(usize),
201}
202
203pub type Thermo = Vec<CellPosition>;
204
205#[derive(Serialize, Deserialize, Debug, Clone)]
206pub struct Arrow {
207  pub circle_cells: Vec<CellPosition>,
208  pub arrow_cells: Vec<CellPosition>,
209}
210
211pub type Renban = Vec<CellPosition>;
212
213pub type Palindrome = Vec<CellPosition>;
214
215impl Display for Rule {
216  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
217      Debug::fmt(self, f)
218  }
219}
220
221impl Arrow {
222  pub fn all_cells(&self) -> Vec<CellPosition> {
223    [
224      self.arrow_cells.to_vec(),
225      self.circle_cells.iter().sorted().copied().collect()
226    ].concat()
227  }
228}
229
230impl SudokuConstraints {
231  pub fn new(grid_size: usize, fixed_numbers: Vec<FixedNumber>) -> SudokuConstraints {
232    SudokuConstraints {
233      grid_size,
234      fixed_numbers,
235      regions: SudokuConstraints::default_regions(grid_size),
236      extra_regions: vec![],
237      killer_cages: vec![],
238      thermos: vec![],
239      arrows: vec![],
240      primary_diagonal: false,
241      secondary_diagonal: false,
242      anti_knight: false,
243      anti_king: false,
244      kropki_dots: vec![],
245      kropki_negative: false,
246      odd_cells: vec![],
247      even_cells: vec![],
248      top_bottom: false,
249      renbans: vec![],
250      palindromes: vec![],
251    }
252  }
253
254  #[allow(dead_code)]
255  pub fn default_regions(grid_size: usize) -> Vec<Region> {
256    let (region_height, region_width) = SudokuConstraints::compute_region_sizes(grid_size);
257
258    let mut regions: Vec<Region> = vec![];
259    for region_row_index in 0..(grid_size / region_height) {
260      for region_col_index in 0..(grid_size / region_width) {
261        let mut region: Region = vec![];
262        for row_index in 0..region_height {
263          for col_index in 0..region_width {
264            let cell = CellPosition {
265              row: region_row_index * region_height + row_index,
266              col: region_col_index * region_width + col_index,
267            };
268            region.push(cell);
269          }
270        }
271        regions.push(region);
272      }
273    }
274
275    regions
276  }
277
278  pub fn compute_region_sizes(grid_size: usize) -> (usize, usize) {
279    if grid_size == 4 {
280      (2, 2)
281    } else if grid_size == 6 {
282      (2, 3)
283    } else {
284      (3, 3)
285    }
286  }
287
288  #[cfg(test)]
289  pub fn with_top_bottom(mut self) -> Self {
290    self.top_bottom = true;
291    self
292  }
293
294  #[cfg(test)]
295  pub fn with_anti_king(mut self) -> Self {
296    self.anti_king = true;
297    self
298  }
299
300  #[cfg(test)]
301  pub fn with_anti_knight(mut self) -> Self {
302    self.anti_knight = true;
303    self
304  }
305
306  #[cfg(test)]
307  pub fn with_diagonals(mut self) -> Self {
308    self.primary_diagonal = true;
309    self.secondary_diagonal = true;
310    self
311  }
312
313  pub fn to_lz_string(&self) -> String {
314    let json = serde_json::to_string(&self).unwrap();
315    let lz_string = lz_str::compress_to_base64(&json);
316    lz_string
317  }
318
319  pub fn to_grid_string(&self) -> String {
320    SudokuGrid::from_fixed_numbers(self.grid_size, &self.fixed_numbers).to_string(Some("\n"))
321  }
322
323  pub fn to_import_string(&self) -> String {
324    self.to_grid_string().replace("\n", "")
325  }
326}
327
328impl FixedNumber {
329  pub fn new(row: usize, col: usize, value: u32) -> FixedNumber {
330    FixedNumber {
331      position: CellPosition {
332        row,
333        col,
334      },
335      value,
336    }
337  }
338}
339
340impl KropkiDot {
341  #[cfg(test)]
342  pub fn consecutive(cell_1: CellPosition, cell_2: CellPosition) -> KropkiDot {
343    KropkiDot {
344      dot_type: KropkiDotType::Consecutive,
345      cell_1,
346      cell_2,
347    }
348  }
349
350  #[cfg(test)]
351  pub fn double(cell_1: CellPosition, cell_2: CellPosition) -> KropkiDot {
352    KropkiDot {
353      dot_type: KropkiDotType::Double,
354      cell_1,
355      cell_2,
356    }
357  }
358
359  pub fn other_cell(&self, cell: &CellPosition) -> CellPosition {
360    if self.cell_1.eq(cell) {
361      self.cell_2
362    } else {
363      self.cell_1
364    }
365  }
366
367  pub fn check_values(&self, value1: u32, value2: u32) -> bool {
368    value1 == 0 ||
369      value2 == 0 ||
370      (
371        self.dot_type != KropkiDotType::Negative && (
372          self.apply_operation(value1) == value2 ||
373          self.apply_operation(value2) == value1
374        )
375      ) ||
376      (
377        self.dot_type == KropkiDotType::Negative &&
378        value1 + 1 != value2 && value2 + 1 != value1 &&
379        value1 * 2 != value2 && value2 * 2 != value1
380      )
381  }
382
383  fn apply_operation(&self, value: u32) -> u32 {
384    match self.dot_type {
385      KropkiDotType::Consecutive => value + 1,
386      KropkiDotType::Double => value * 2,
387      KropkiDotType::Negative => unimplemented!(),
388    }
389  }
390}
391
392impl SudokulogicalSolveResult {
393  pub fn no_solution(invalid_state_reason: InvalidStateReason) -> SudokulogicalSolveResult {
394    SudokulogicalSolveResult {
395      solution_type: SolutionType::None,
396      solution: None,
397      steps: vec![],
398      invalid_state_reason: Some(invalid_state_reason),
399    }
400  }
401}
402
403impl SolutionStep {
404  pub fn new(
405    rule: Rule, cells: Vec<CellPosition>, values: Vec<u32>,
406    areas: Vec<Area>, affected_cells: Vec<CellPosition>,
407  ) -> SolutionStep {
408    SolutionStep {
409      rule,
410      cells,
411      values,
412      areas,
413      affected_cells,
414      candidates: None,
415      invalid_state_reason: None,
416    }
417  }
418
419  pub fn is_grid_step(&self) -> bool {
420    [ Rule::NakedSingle, Rule::HiddenSingle, Rule::Thermo, Rule::PalindromeValues ].contains(&self.rule)
421  }
422}
423
424impl SudokuGrid {
425  pub fn new(grid: Grid) -> Self {
426    SudokuGrid {
427      values: grid,
428    }
429  }
430
431  pub fn from_string(grid_str: String) -> Self {
432    let grid_size = f32::sqrt(grid_str.len() as f32) as usize;
433    assert_eq!(grid_size * grid_size, grid_str.len(), "Invalid grid passed");
434    let grid_chars = grid_str.chars().collect_vec();
435    let grid: Grid = (0..grid_size).map(|row| {
436      (0..grid_size).map(|col| {
437        let index = row * grid_size + col;
438        grid_chars[index].to_digit(10).unwrap()
439      }).collect()
440    }).collect();
441    Self {
442      values: grid,
443    }
444  }
445
446  pub fn from_fixed_numbers(grid_size: usize, fixed_numbers: &Vec<FixedNumber>) -> Self {
447    let mut grid: Grid = vec![ vec![ 0; grid_size ]; grid_size ];
448    for fixed_number in fixed_numbers {
449      let cell = fixed_number.position;
450      grid[cell.row][cell.col] = fixed_number.value;
451    }
452    SudokuGrid::new(grid)
453  }
454
455  pub fn to_fixed_numbers(&self) -> Vec<FixedNumber> {
456    let mut fixed_numbers = vec![];
457    for (row_index, row) in self.values.iter().enumerate() {
458      for (col_index, &value) in row.iter().enumerate() {
459        if value != 0 {
460          fixed_numbers.push(FixedNumber::new(row_index, col_index, value));
461        }
462      }
463    }
464    fixed_numbers
465  }
466
467  pub fn to_string(&self, separator: Option<&str>) -> String {
468    self.values
469      .iter()
470      .map(|row| {
471        row.iter()
472          .map(|digit| digit.to_string() )
473          .collect::<Vec<String>>()
474          .join("")
475      })
476      .collect::<Vec<String>>()
477      .join(separator.unwrap_or(""))
478  }
479}
480
481impl Area {
482  pub fn to_string(&self) -> String {
483    match self {
484      Area::Row(row) => format!("row {}", row + 1),
485      Area::Column(col) => format!("column {}", col + 1),
486      Area::Region(region) => format!("box {}", region + 1),
487      Area::Grid | Area::Adhoc(_) | Area::Cell(_, _) |
488        Area::Thermo(_) | Area::Arrow(_) |
489        Area::KillerCage(_) | Area::KropkiDot(_) |
490        Area::PrimaryDiagonal | Area::SecondaryDiagonal |
491        Area::Renban(_) | Area::Palindrome(_) => unimplemented!(),
492    }
493  }
494}
495
496// https://www.reddit.com/r/sudoku/comments/11kpwbt/fun_puzzle_link_in_comment/
497#[test]
498fn check_sudoku_constraints_import_string() {
499  let fixed_numbers = SudokuGrid::new(vec![
500    vec![ 2, 0, 3, 0, 0, 0, 1, 0, 7 ],
501    vec![ 9, 1, 0, 0, 4, 0, 0, 2, 6 ],
502    vec![ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
503    vec![ 3, 0, 8, 0, 1, 0, 7, 0, 9 ],
504    vec![ 1, 0, 0, 0, 0, 0, 0, 0, 2 ],
505    vec![ 0, 0, 2, 0, 0, 0, 8, 0, 0 ],
506    vec![ 0, 0, 4, 1, 6, 7, 2, 0, 0 ],
507    vec![ 7, 0, 0, 0, 8, 0, 0, 0, 1 ],
508    vec![ 8, 0, 0, 2, 0, 9, 0, 0, 3 ],
509  ]).to_fixed_numbers();
510  let constraints = SudokuConstraints::new(9, fixed_numbers);
511  assert_eq!(constraints.to_import_string(), String::from(
512    "203000107910040026000000000308010709100000002002000800004167200700080001800209003"
513  ))
514}
515
516#[test]
517fn check_sudoku_grid_from_string() {
518  let grid_str = String::from("203000107910040026000000000308010709100000002002000800004167200700080001800209003");
519  let grid = SudokuGrid::from_string(grid_str).values;
520  let expected_grid = vec![
521    vec![ 2, 0, 3, 0, 0, 0, 1, 0, 7 ],
522    vec![ 9, 1, 0, 0, 4, 0, 0, 2, 6 ],
523    vec![ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
524    vec![ 3, 0, 8, 0, 1, 0, 7, 0, 9 ],
525    vec![ 1, 0, 0, 0, 0, 0, 0, 0, 2 ],
526    vec![ 0, 0, 2, 0, 0, 0, 8, 0, 0 ],
527    vec![ 0, 0, 4, 1, 6, 7, 2, 0, 0 ],
528    vec![ 7, 0, 0, 0, 8, 0, 0, 0, 1 ],
529    vec![ 8, 0, 0, 2, 0, 9, 0, 0, 3 ],
530  ];
531  assert_eq!(grid, expected_grid);
532}
lisudoku_solver/types.rs

lisudoku_solver/
types.rs
