use std::io::{self, stdout, Write}; use backtracking::{Problem, Solutions}; fn main() -> io::Result<()> { // An empty sudoku field let sudoku = Sudoku::from_bytes([ 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, 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, 0, 4, 0, 0, 0, 6, 3, 0, 7, 0, 9, 0, 0, 9, 0, 0, 0, 2, 0, 3, 0, ]); for solution in Solutions::new(sudoku).take(1) { solution.print_to(&mut stdout())? } Ok(()) } #[derive(Clone)] pub struct Sudoku { /// All 9 by 9 fields, in top to bottom, left to right order. `0` represents empty. Other valid /// values are 1..=9 fields: [u8; 9 * 9], } impl Sudoku { pub fn new() -> Self { let fields = [0u8; 9 * 9]; Self::from_bytes(fields) } pub fn from_bytes(bytes: [u8; 9 * 9]) -> Self { if bytes.iter().any(|&n| n > 9) { panic!("Only values from 0 to 9 are valid.") } Self { fields: bytes } } pub fn print_to(&self, to: &mut impl Write) -> io::Result<()> { for index in 0..self.fields.len() { // New row beginnig? if index % 9 == 0 && index != 0 { writeln!(to)?; } match self.fields[index] { 0 => write!(to, "X")?, n @ 1..=9 => write!(to, "{n}")?, _ => unreachable!(), }; } writeln!(to)?; Ok(()) } pub fn possible_digits_at(&self, index: u8) -> impl Iterator + '_ { let row = index as usize / 9; let col = index as usize % 9; let group = col / 3 + (row / 3) * 3; // Index upper right corner of group let group_off = group * 3 + (group / 3) * 18; let is_in_row = move |digit| (0..9).any(|c| self.fields[c + row * 9] == digit); let is_in_col = move |digit| (0..9).any(|r| self.fields[col + r * 9] == digit); let is_in_group = move |digit| (0..9).any(|i| self.fields[group_off + i % 3 + (i / 3) * 9] == digit); (1..=9) .filter(move |digit| !is_in_row(*digit)) .filter(move |digit| !is_in_col(*digit)) .filter(move |digit| !is_in_group(*digit)) } } impl Default for Sudoku { fn default() -> Self { Self::new() } } #[derive(Clone, Copy)] pub struct WriteDigit { index: u8, digit: u8, } impl Problem for Sudoku { type Posibility = WriteDigit; type Solution = Sudoku; // We look over all posibilities for the first free index fn extend_possibilities(&self, possible_moves: &mut Vec, _history: &[WriteDigit]) { if let Some(index) = self.fields.iter().position(|value| *value == 0) { let index = index as u8; let mut all_possible_digits = self.possible_digits_at(index); // Treat the first digit special, because we want to shirt circut in case we there is // not even one digit. if let Some(digit) = all_possible_digits.next() { possible_moves.push(WriteDigit { index, digit }); } else { // Not even one possible digit could be found for this field. This implies that this // Sudoku is unsolvable and has no possible moves, since we verified that this field // is free. possible_moves.clear(); return; } // Add the remaining digits for this field to the possibilities possible_moves.extend(all_possible_digits.map(|digit| WriteDigit { index, digit })); } } fn undo(&mut self, last: &WriteDigit, _history: &[WriteDigit]) { self.fields[last.index as usize] = 0; } fn what_if(&mut self, move_: WriteDigit) { self.fields[move_.index as usize] = move_.digit; } fn is_solution(&self, _history: &[WriteDigit]) -> Option { if self.fields.iter().all(|digit| *digit != 0) { Some(self.clone()) } else { None } } } #[cfg(test)] mod tests { use crate::lib::Game; use super::{Sudoku, WriteDigit}; #[test] fn print_empty_sudoku() { let mut out = Vec::new(); let game = Sudoku::new(); game.print_to(&mut out).unwrap(); let expect = "XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ "; assert_eq!(expect, std::str::from_utf8(&out).unwrap()); } #[test] fn print_with_first_row_filled() { let mut out = Vec::new(); let mut game = Sudoku::new(); game.play_move(WriteDigit { index: 0, digit: 1 }); game.play_move(WriteDigit { index: 1, digit: 2 }); game.play_move(WriteDigit { index: 2, digit: 3 }); game.play_move(WriteDigit { index: 3, digit: 4 }); game.play_move(WriteDigit { index: 4, digit: 5 }); game.play_move(WriteDigit { index: 5, digit: 6 }); game.play_move(WriteDigit { index: 6, digit: 7 }); game.play_move(WriteDigit { index: 7, digit: 8 }); game.play_move(WriteDigit { index: 8, digit: 9 }); game.print_to(&mut out).unwrap(); let expect = "123456789\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ XXXXXXXXX\n\ "; assert_eq!(expect, std::str::from_utf8(&out).unwrap()); } #[test] fn prevent_same_digit_twice_in_same_row() { let mut game = Sudoku::new(); game.play_move(WriteDigit { index: 0, digit: 2 }); game.play_move(WriteDigit { index: 8, digit: 5 }); // Won't play a role, because neither same group, row or column game.play_move(WriteDigit { index: 7 * 9 + 6, digit: 5, }); let possibilities = game.possible_digits_at(1).collect::>(); assert_eq!(&[1u8, 3, 4, 6, 7, 8, 9][..], possibilities); } #[test] fn prevent_same_digit_twice_in_same_col() { let mut game = Sudoku::new(); game.play_move(WriteDigit { index: 3, digit: 2 }); game.play_move(WriteDigit { index: 3 + 9 * 5, digit: 5, }); let possibilities = game.possible_digits_at(3 + 9 * 2).collect::>(); assert_eq!(&[1u8, 3, 4, 6, 7, 8, 9][..], possibilities); } #[test] fn short_ciruct_if_one_field_has_no_more_possibile_digits() { let mut game = Sudoku::new(); game.play_move(WriteDigit { index: 0, digit: 1 }); game.play_move(WriteDigit { index: 1, digit: 2 }); game.play_move(WriteDigit { index: 2, digit: 3 }); game.play_move(WriteDigit { index: 3, digit: 4 }); game.play_move(WriteDigit { index: 4, digit: 5 }); game.play_move(WriteDigit { index: 5, digit: 6 }); game.play_move(WriteDigit { index: 6, digit: 7 }); game.play_move(WriteDigit { index: 7, digit: 8 }); game.play_move(WriteDigit { index: 9 + 8, digit: 9, }); let mut possible_moves = Vec::new(); game.fill_possible_moves(&mut possible_moves); assert_eq!(0, game.possible_digits_at(8).count()); assert!(possible_moves.is_empty()); } }