summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorKent Overstreet <kent.overstreet@gmail.com>2015-10-02 16:47:55 -0800
committerKent Overstreet <kent.overstreet@gmail.com>2015-10-02 16:47:55 -0800
commit163e12484f847624673485d22b49fa6dbb15b994 (patch)
tree6a9eb6cd6d183cf5e30111f7766cbe3a6f135a46 /src
downloadsudoku-163e12484f847624673485d22b49fa6dbb15b994.tar.zst
sudoku solver
Diffstat (limited to 'src')
-rw-r--r--src/main.rs302
1 files changed, 302 insertions, 0 deletions
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<usize>,
+}
+
+impl Iterator for EachPos {
+ type Item = BitBoardPos;
+
+ fn next(&mut self) -> Option<BitBoardPos> {
+ self.i.next().map(|i| BitBoardPos { x: i / 9, y: i % 9 })
+ }
+}
+
+fn each_pos() -> EachPos {
+ EachPos { i: (0..81) }
+}
+
+struct EachBlock {
+ i: Range<usize>,
+}
+
+impl Iterator for EachBlock {
+ type Item = BitBoardPos;
+
+ fn next(&mut self) -> Option<BitBoardPos> {
+ 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<usize>,
+}
+
+impl Iterator for Column {
+ type Item = BitBoardPos;
+
+ fn next(&mut self) -> Option<BitBoardPos> {
+ self.y.next().map(|y| BitBoardPos { x: self.x, y: y })
+ }
+}
+
+struct Row {
+ x: Range<usize>,
+ y: usize,
+}
+
+impl Iterator for Row {
+ type Item = BitBoardPos;
+
+ fn next(&mut self) -> Option<BitBoardPos> {
+ self.x.next().map(|x| BitBoardPos { x: x, y: self.y })
+ }
+}
+
+struct Block {
+ start: BitBoardPos,
+ i: Range<usize>,
+}
+
+impl Iterator for Block {
+ type Item = BitBoardPos;
+
+ fn next(&mut self) -> Option<BitBoardPos> {
+ 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<BitBoardPos> for BitBoard {
+ type Output = u16;
+
+ fn index<'a>(&'a self, p: BitBoardPos) -> &'a u16 {
+ &self.b[p.x][p.y]
+ }
+}
+
+impl IndexMut<BitBoardPos> 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<Item=BitBoardPos>) -> 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<Item=BitBoardPos>) -> 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));
+}