From 163e12484f847624673485d22b49fa6dbb15b994 Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Fri, 2 Oct 2015 16:47:55 -0800 Subject: sudoku solver --- Cargo.toml | 4 + src/main.rs | 302 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 306 insertions(+) create mode 100644 Cargo.toml create mode 100644 src/main.rs diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..219e172 --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,4 @@ +[package] +name = "sudoku" +version = "0.1.0" +authors = ["Kent Overstreet "] diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..e649372 --- /dev/null +++ b/src/main.rs @@ -0,0 +1,302 @@ +use std::fmt; +use std::io; +use std::io::prelude::*; +use std::ops::{Index, IndexMut, Range}; +use std::process::exit; + +#[derive(Eq, PartialEq, Copy, Clone)] +struct BitBoardPos { + x: usize, + y: usize, +} + +struct EachPos { + i: Range, +} + +impl Iterator for EachPos { + type Item = BitBoardPos; + + fn next(&mut self) -> Option { + self.i.next().map(|i| BitBoardPos { x: i / 9, y: i % 9 }) + } +} + +fn each_pos() -> EachPos { + EachPos { i: (0..81) } +} + +struct EachBlock { + i: Range, +} + +impl Iterator for EachBlock { + type Item = BitBoardPos; + + fn next(&mut self) -> Option { + self.i.next().map(|i| BitBoardPos { x: i / 3 * 3, y: i % 3 * 3 }) + } +} + +fn each_block() -> EachBlock { + EachBlock { i: (0..9) } +} + +struct Column { + x: usize, + y: Range, +} + +impl Iterator for Column { + type Item = BitBoardPos; + + fn next(&mut self) -> Option { + self.y.next().map(|y| BitBoardPos { x: self.x, y: y }) + } +} + +struct Row { + x: Range, + y: usize, +} + +impl Iterator for Row { + type Item = BitBoardPos; + + fn next(&mut self) -> Option { + self.x.next().map(|x| BitBoardPos { x: x, y: self.y }) + } +} + +struct Block { + start: BitBoardPos, + i: Range, +} + +impl Iterator for Block { + type Item = BitBoardPos; + + fn next(&mut self) -> Option { + self.i.next().map(|i| BitBoardPos { + x: self.start.x + i / 3, + y: self.start.y + i % 3 + }) + } +} + +impl BitBoardPos { + fn column(self) -> Column { + Column { x: self.x, y: (0..9), } + } + + fn row(self) -> Row { + Row { x: (0..9), y: self.y, } + } + + fn block(self) -> Block { + Block { + start: BitBoardPos { + x: self.x / 3 * 3, + y: self.y / 3 * 3, + }, + i: (0..9), + } + } +} + +const ALL_NUMS: u16 = ((1 << 9) - 1) << 1; + +#[derive(Eq, PartialEq, Copy, Clone)] +struct BitBoard { + b: [[u16; 9]; 9], +} + +impl Index for BitBoard { + type Output = u16; + + fn index<'a>(&'a self, p: BitBoardPos) -> &'a u16 { + &self.b[p.x][p.y] + } +} + +impl IndexMut for BitBoard { + fn index_mut<'a>(&'a mut self, p: BitBoardPos) -> &'a mut u16 { + &mut self.b[p.x][p.y] + } +} + +fn read_board() -> BitBoard { + let mut b = BitBoard { b: [[0u16; 9]; 9], }; + + for i in 0..9 { + let mut line = String::new(); + + if io::stdin().read_line(&mut line).unwrap() < 9 { + println!("didn't get sudoku line"); + exit(1); + } + + for (j, c) in line.chars().enumerate() { + if c == '\n' { + break; + } + + b.b[i][j] = if c == '.' { + ALL_NUMS + } else { + 1 << ((c as u32) - ('0' as u32)) as u16 + } + } + } + + b +} + +impl fmt::Display for BitBoard { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + for i in self.b.iter() { + for j in i.iter() { + if j.is_power_of_two() { + write!(f, "{}", j.trailing_zeros()) + } else { + write!(f, ".") + }.unwrap(); + } + + write!(f, "\n").unwrap(); + } + + Ok(()) + } +} + +/* + * Check if a board configuration is valid: not actually used in the solver, + * just an additional check: + */ +fn check(b: &BitBoard) -> bool { + let origin = BitBoardPos { x: 0, y: 0 }; + + /* Check a column/row/block for duplicates - true if no duplicates */ + fn check_iter(b: &BitBoard, iter: &mut Iterator) -> bool { + let mut v = 0u16; + + iter.filter(|i| b[*i].is_power_of_two()) + .all(|i| (v & b[i]) == 0 && {v |= b[i]; true}) + } + + origin.row() .all(|i| check_iter(b, &mut i.column())) && + origin.column() .all(|i| check_iter(b, &mut i.row())) && + each_block() .all(|i| check_iter(b, &mut i.block())) +} + +fn solve_by_constraints(b: &mut BitBoard, p: BitBoardPos, + iter: &mut Iterator) -> bool { + /* + * Check every other cell in the same row/column/block as this cell - if + * there is a number that we've determined can't be in any of those cells, + * then it must be in this cell: + */ + if !b[p].is_power_of_two() { + let m = iter + .filter(|i| *i != p) + .fold(0u16, |a, i| a | b[i]) + ^ ALL_NUMS; + + if m.is_power_of_two() { + if (b[p] & m) == 0 { + return false; + } + + b[p] = m; + } + } + + true +} + +fn solve_at_pos(b: &mut BitBoard, p: BitBoardPos) -> bool { + if !solve_by_constraints(b, p, &mut p.column()) || + !solve_by_constraints(b, p, &mut p.row()) || + !solve_by_constraints(b, p, &mut p.block()) { + return false; + } + + /* + * if we know what number is in this slot - strike it from every other cell + * in the same row/column/block: + */ + if b[p].is_power_of_two() { + for i in p.column() + .chain(p.row()) + .chain(p.block()) + .filter(|i| *i != p) { + if (b[i] & b[p]) != 0 { + b[i] ^= b[p]; + if b[i] == 0 { + return false; + } + } + } + } + + true +} + +/* returns true on success, false if board is inconsistent: */ +fn solve(b: &mut BitBoard) -> bool { + /* + * First, try solving by constraints, as long as we're able to make + * progress - iterate until fixed point: + */ + while { + let prev = *b; + + if !each_pos().all(|i| solve_at_pos(b, i)) { + return false; + } + + prev != *b + } {} + + /* + * When we get stuck, if there's unsolved cells left switch to backtracking: + */ + match each_pos().find(|i| !b[*i].is_power_of_two()) { + None => true, + Some(i) => { + println!("backtracking at:\n{}", b); + + for j in 1..10 { + if (b[i] & (1 << j)) != 0 { + let mut r = *b; + + r[i] = 1 << j; + + if solve(&mut r) { + *b = r; + return true; + } + + println!("inconsistent at:\n{} {}", r, check(&r)); + } + } + + /* + * If none of the attempts worked, we were already had an + * inconsistent board but we needed multiple guesses to prove that: + */ + return false; + } + } +} + +fn main() { + let mut b = read_board(); + + println!("{} {}", b, check(&b)); + + solve(&mut b); + + println!("{} {}", b, check(&b)); +} -- cgit v1.2.3