sudoku/
sudoku.rs

1use std::io::{self, stdout, Write};
2
3use backtracking::{Problem, Solutions};
4
5fn main() -> io::Result<()> {
6    // An empty sudoku field
7    let sudoku = Sudoku::from_bytes([
8        6, 0, 3, 0, 0, 0, 1, 0, 0, 0, 0, 9, 0, 0, 0, 2, 0, 0, 0, 0, 7, 4, 0, 9, 0, 0, 0, 0, 0, 0,
9        0, 1, 0, 0, 0, 7, 4, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 5, 3, 0, 1, 0, 0, 0, 0,
10        0, 4, 0, 0, 0, 6, 3, 0, 7, 0, 9, 0, 0, 9, 0, 0, 0, 2, 0, 3, 0,
11    ]);
12    for solution in Solutions::new(sudoku).take(1) {
13        solution.print_to(&mut stdout())?
14    }
15    Ok(())
16}
17
18#[derive(Clone)]
19pub struct Sudoku {
20    /// All 9 by 9 fields, in top to bottom, left to right order. `0` represents empty. Other valid
21    /// values are 1..=9
22    fields: [u8; 9 * 9],
23}
24
25impl Sudoku {
26    pub fn new() -> Self {
27        let fields = [0u8; 9 * 9];
28        Self::from_bytes(fields)
29    }
30
31    pub fn from_bytes(bytes: [u8; 9 * 9]) -> Self {
32        if bytes.iter().any(|&n| n > 9) {
33            panic!("Only values from 0 to 9 are valid.")
34        }
35        Self { fields: bytes }
36    }
37
38    pub fn print_to(&self, to: &mut impl Write) -> io::Result<()> {
39        for index in 0..self.fields.len() {
40            // New row beginnig?
41            if index % 9 == 0 && index != 0 {
42                writeln!(to)?;
43            }
44            match self.fields[index] {
45                0 => write!(to, "X")?,
46                n @ 1..=9 => write!(to, "{n}")?,
47                _ => unreachable!(),
48            };
49        }
50        writeln!(to)?;
51        Ok(())
52    }
53
54    pub fn possible_digits_at(&self, index: u8) -> impl Iterator<Item = u8> + '_ {
55        let row = index as usize / 9;
56        let col = index as usize % 9;
57        let group = col / 3 + (row / 3) * 3;
58        // Index upper right corner of group
59        let group_off = group * 3 + (group / 3) * 18;
60        let is_in_row = move |digit| (0..9).any(|c| self.fields[c + row * 9] == digit);
61        let is_in_col = move |digit| (0..9).any(|r| self.fields[col + r * 9] == digit);
62        let is_in_group =
63            move |digit| (0..9).any(|i| self.fields[group_off + i % 3 + (i / 3) * 9] == digit);
64        (1..=9)
65            .filter(move |digit| !is_in_row(*digit))
66            .filter(move |digit| !is_in_col(*digit))
67            .filter(move |digit| !is_in_group(*digit))
68    }
69}
70
71impl Default for Sudoku {
72    fn default() -> Self {
73        Self::new()
74    }
75}
76
77#[derive(Clone, Copy)]
78pub struct WriteDigit {
79    index: u8,
80    digit: u8,
81}
82
83impl Problem for Sudoku {
84    type Posibility = WriteDigit;
85    type Solution = Sudoku;
86
87    // We look over all posibilities for the first free index
88    fn extend_possibilities(&self, possible_moves: &mut Vec<WriteDigit>, _history: &[WriteDigit]) {
89        if let Some(index) = self.fields.iter().position(|value| *value == 0) {
90            let index = index as u8;
91            let mut all_possible_digits = self.possible_digits_at(index);
92            // Treat the first digit special, because we want to shirt circut in case we there is
93            // not even one digit.
94            if let Some(digit) = all_possible_digits.next() {
95                possible_moves.push(WriteDigit { index, digit });
96            } else {
97                // Not even one possible digit could be found for this field. This implies that this
98                // Sudoku is unsolvable and has no possible moves, since we verified that this field
99                // is free.
100                possible_moves.clear();
101                return;
102            }
103            // Add the remaining digits for this field to the possibilities
104            possible_moves.extend(all_possible_digits.map(|digit| WriteDigit { index, digit }));
105        }
106    }
107
108    fn undo(&mut self, last: &WriteDigit, _history: &[WriteDigit]) {
109        self.fields[last.index as usize] = 0;
110    }
111
112    fn what_if(&mut self, move_: WriteDigit) {
113        self.fields[move_.index as usize] = move_.digit;
114    }
115
116    fn is_solution(&self, _history: &[WriteDigit]) -> Option<Self::Solution> {
117        if self.fields.iter().all(|digit| *digit != 0) {
118            Some(self.clone())
119        } else {
120            None
121        }
122    }
123}
124
125#[cfg(test)]
126mod tests {
127    use crate::lib::Game;
128
129    use super::{Sudoku, WriteDigit};
130
131    #[test]
132    fn print_empty_sudoku() {
133        let mut out = Vec::new();
134        let game = Sudoku::new();
135
136        game.print_to(&mut out).unwrap();
137
138        let expect = "XXXXXXXXX\n\
139            XXXXXXXXX\n\
140            XXXXXXXXX\n\
141            XXXXXXXXX\n\
142            XXXXXXXXX\n\
143            XXXXXXXXX\n\
144            XXXXXXXXX\n\
145            XXXXXXXXX\n\
146            XXXXXXXXX\n\
147        ";
148        assert_eq!(expect, std::str::from_utf8(&out).unwrap());
149    }
150
151    #[test]
152    fn print_with_first_row_filled() {
153        let mut out = Vec::new();
154        let mut game = Sudoku::new();
155        game.play_move(WriteDigit { index: 0, digit: 1 });
156        game.play_move(WriteDigit { index: 1, digit: 2 });
157        game.play_move(WriteDigit { index: 2, digit: 3 });
158        game.play_move(WriteDigit { index: 3, digit: 4 });
159        game.play_move(WriteDigit { index: 4, digit: 5 });
160        game.play_move(WriteDigit { index: 5, digit: 6 });
161        game.play_move(WriteDigit { index: 6, digit: 7 });
162        game.play_move(WriteDigit { index: 7, digit: 8 });
163        game.play_move(WriteDigit { index: 8, digit: 9 });
164
165        game.print_to(&mut out).unwrap();
166
167        let expect = "123456789\n\
168            XXXXXXXXX\n\
169            XXXXXXXXX\n\
170            XXXXXXXXX\n\
171            XXXXXXXXX\n\
172            XXXXXXXXX\n\
173            XXXXXXXXX\n\
174            XXXXXXXXX\n\
175            XXXXXXXXX\n\
176        ";
177        assert_eq!(expect, std::str::from_utf8(&out).unwrap());
178    }
179
180    #[test]
181    fn prevent_same_digit_twice_in_same_row() {
182        let mut game = Sudoku::new();
183        game.play_move(WriteDigit { index: 0, digit: 2 });
184        game.play_move(WriteDigit { index: 8, digit: 5 });
185        // Won't play a role, because neither same group, row or column
186        game.play_move(WriteDigit {
187            index: 7 * 9 + 6,
188            digit: 5,
189        });
190
191        let possibilities = game.possible_digits_at(1).collect::<Vec<u8>>();
192
193        assert_eq!(&[1u8, 3, 4, 6, 7, 8, 9][..], possibilities);
194    }
195
196    #[test]
197    fn prevent_same_digit_twice_in_same_col() {
198        let mut game = Sudoku::new();
199        game.play_move(WriteDigit { index: 3, digit: 2 });
200        game.play_move(WriteDigit {
201            index: 3 + 9 * 5,
202            digit: 5,
203        });
204
205        let possibilities = game.possible_digits_at(3 + 9 * 2).collect::<Vec<u8>>();
206
207        assert_eq!(&[1u8, 3, 4, 6, 7, 8, 9][..], possibilities);
208    }
209
210    #[test]
211    fn short_ciruct_if_one_field_has_no_more_possibile_digits() {
212        let mut game = Sudoku::new();
213        game.play_move(WriteDigit { index: 0, digit: 1 });
214        game.play_move(WriteDigit { index: 1, digit: 2 });
215        game.play_move(WriteDigit { index: 2, digit: 3 });
216        game.play_move(WriteDigit { index: 3, digit: 4 });
217        game.play_move(WriteDigit { index: 4, digit: 5 });
218        game.play_move(WriteDigit { index: 5, digit: 6 });
219        game.play_move(WriteDigit { index: 6, digit: 7 });
220        game.play_move(WriteDigit { index: 7, digit: 8 });
221        game.play_move(WriteDigit {
222            index: 9 + 8,
223            digit: 9,
224        });
225
226        let mut possible_moves = Vec::new();
227        game.fill_possible_moves(&mut possible_moves);
228
229        assert_eq!(0, game.possible_digits_at(8).count());
230        assert!(possible_moves.is_empty());
231    }
232}
sudoku/sudoku.rs

sudoku/
sudoku.rs
