rsudoku/
lib.rs

1use std::ops::Range;
2use std::{char, fmt::Display, ops::{Index, IndexMut}};
3
4use solver::SudokuSolver;
5use unchecked_array::UncheckedArray;
6
7pub mod solver;
8use solver::BacktrackingSudokuSolver;
9
10#[cfg(feature = "builder")]
11mod builder;
12#[cfg(feature = "builder")]
13pub use builder::build_sudoku;
14
15fn box_iter(n: usize) -> Range<usize> {
16    let base = n - n % 3;
17    base..base+3
18}
19
20#[derive(Clone)]
21pub struct Sudoku(UncheckedArray<UncheckedArray<u8,9>,9>);
22
23impl Sudoku {
24    const UNASSIGNED: u8 = 0;
25
26    pub fn empty() -> Self {
27        [Self::UNASSIGNED; 81].into()
28    }
29
30    pub fn new(a: impl Into<Self>) -> Self {
31        a.into()
32    }
33
34    pub fn from_str_pattern(l: &str) -> Result<Self,String> {
35        let mut chars = l.chars();
36        let mut arr = [0_u8; 9 * 9];
37        arr.iter_mut().try_for_each(|e| {
38            let c = chars.next().unwrap_or('.');
39            *e = match c {
40                '0'..='9' => c as u8 - b'0',
41                '.' => Self::UNASSIGNED,
42                _ => return Err(format!("Unknown character {c}")),
43            };
44            Ok(())
45        })?;
46        Ok(arr.into())
47    }
48
49    fn find_unsassigned(&self) -> Option<(usize,usize)> {
50        for row in 0..9 {
51            for col in 0..9 {
52                if self.0[row][col] == Self::UNASSIGNED {
53                    return Some((row,col));
54                }
55            }
56        }
57        None
58    }
59
60    pub fn is_solved(&mut self) -> bool {
61        (0..9).all(|i|
62            (0..9).all(|j|
63                self.is_unique(i, j)))
64    }
65
66    fn used_in_row(&self, row: usize, n: u8) -> bool {
67        (0..9).any(|col| self[row][col] == n)
68    }
69
70    fn used_in_col(&self, col: usize, n: u8) -> bool {
71        (0..9).any(|row| self[row][col] == n)
72    }
73
74    fn used_in_box(&self, row: usize, col: usize, n: u8) -> bool {
75        box_iter(row).any(|row|
76            box_iter(col).any(|col|
77                self[row][col] == n))
78    }
79
80    fn is_unique(&mut self, row: usize, col: usize) -> bool {
81        let n = self[row][col];
82        self[row][col] = Self::UNASSIGNED;
83        let res =
84           n != Self::UNASSIGNED
85        && !self.used_in_row(row, n)
86        && !self.used_in_col(col, n)
87        && !self.used_in_box(row, col, n);
88        self[row][col] = n;
89        res
90    }
91
92    fn is_safe(&self, row: usize, col: usize, n: u8) -> bool {
93        !self.used_in_row(row, n)
94        && !self.used_in_col(col, n)
95        && !self.used_in_box(row, col, n)
96        && self.0[row][col] == Self::UNASSIGNED
97    }
98
99    fn check_well_formatted(&mut self) -> Option<()> {
100        for row in 0..9 {
101            for col in 0..9 {
102                if self[row][col] != Self::UNASSIGNED && !self.is_unique(row, col)  {
103                    return None;
104                }
105            }
106        }
107        Some(())
108    }
109
110    pub fn solve(&self) -> Option<Sudoku> {
111        self.solve_with(BacktrackingSudokuSolver)
112    }
113
114    pub fn solve_with(&self, mut solver: impl SudokuSolver) -> Option<Sudoku> {
115        let mut s = self.clone();
116        s.check_well_formatted()?;
117        solver.solve(&mut s);
118        Some(s)
119    }
120
121    #[cfg(feature = "random")]
122    pub fn remove_digits(&mut self, mut n: usize) {
123        use rand::Rng;
124
125        let mut rng = rand::thread_rng();
126        while n > 0 {
127            let id = rng.gen_range(0..81);
128            let row = id / 9;
129            let col = id % 9;
130
131            let cell = &mut self[row][col];
132            if *cell != Sudoku::UNASSIGNED {
133                *cell = Sudoku::UNASSIGNED;
134                n -= 1;
135            }
136        }
137    }
138}
139
140impl Index<usize> for Sudoku {
141    type Output = [u8; 9];
142
143    fn index(&self, index: usize) -> &Self::Output {
144        &self.0[index]
145    }
146}
147
148impl IndexMut<usize> for Sudoku {
149    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
150        &mut self.0[index]
151    }
152}
153
154impl From<[[u8; 9]; 9]> for Sudoku {
155    fn from(value: [[u8; 9]; 9]) -> Self {
156        let mut dst: UncheckedArray<UncheckedArray<u8,9>,9> = UncheckedArray::default();
157        for (i,e) in (0..9).zip(value.into_iter()) {
158            dst[i] = UncheckedArray::from(e);
159        }
160        Sudoku(dst)
161    }
162}
163
164impl From<[u8; 81]> for Sudoku {
165    fn from(value: [u8; 81]) -> Self {
166        let mut src = 0;
167        let mut dst = [[0_u8; 9]; 9];
168        dst.iter_mut().for_each(|it| {
169            it.iter_mut().for_each(|n| {
170                *n = value[src];
171                src += 1;
172            });
173        });
174        Sudoku::new(dst)
175    }
176}
177
178impl Display for Sudoku {
179    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
180        for row in 0..9 {
181            for col in 0..9 {
182                if col == 0 {
183                    write!(f, "|")?;
184                }
185                let n = self.0[row][col];
186                let n = if n != Self::UNASSIGNED {
187                    (b'0' + n) as char
188                } else {
189                    '?'
190                };
191                write!(f, "{n}|")?;
192            }
193            if row < 8 {
194                writeln!(f)?;
195            }
196        }
197        Ok(())
198    }
199}
200
201impl PartialEq for Sudoku {
202    fn eq(&self, other: &Self) -> bool {
203        self.0 == other.0
204    }
205}
rsudoku/lib.rs

rsudoku/
lib.rs
