sudoku solver

2 files changed, 306 insertions, 0 deletions

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 <kent.overstreet@gmail.com>"]
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));
+}