foo

1 files changed, 257 insertions, 71 deletions

diff --git a/src/main.rs b/src/main.rs
index e649372..2e2d4d8 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -3,6 +3,40 @@ use std::io;
 use std::io::prelude::*;
 use std::ops::{Index, IndexMut, Range};
 use std::process::exit;
+use std::vec::Vec;
+//use std::collections::HashMap;
+
+#[inline]
+fn fixed_point<T, F>(x: T, f: F) -> T
+    where T: Eq + Clone, F: Fn(T) -> T
+{
+    let n = f(x.clone());
+
+    if n == x {
+        x
+    } else {
+        fixed_point(n, f)
+    }
+}
+
+trait FoldWhile: Iterator {
+    #[inline]
+    fn fold_while<T, F>(self, init: T, mut f: F) -> Option<T> where
+        Self: Sized, F: FnMut(T, Self::Item) -> Option<T>,
+    {
+        let mut accum = init;
+        for x in self {
+            accum = match f(accum, x) {
+                Some(a)     => a,
+                None        => return None
+            }
+
+        }
+        Some(accum)
+    }
+}
+
+impl<I> FoldWhile for I where I: Iterator {}
 
 #[derive(Eq, PartialEq, Copy, Clone)]
 struct BitBoardPos {
@@ -102,15 +136,25 @@ impl BitBoardPos {
             i: (0..9),
         }
     }
+
+    fn blocknr(self) -> usize {
+        self.x / 3  * 3 + self.y / 3
+    }
 }
 
 const  ALL_NUMS: u16 = ((1 << 9) - 1) << 1;
 
-#[derive(Eq, PartialEq, Copy, Clone)]
+#[derive(Eq, PartialEq, Hash, Copy, Clone)]
 struct BitBoard {
     b:  [[u16; 9]; 9],
 }
 
+impl BitBoard {
+    fn new() -> BitBoard {
+        BitBoard { b: [[ALL_NUMS; 9]; 9], }
+    }
+}
+
 impl Index<BitBoardPos> for BitBoard {
     type Output = u16;
 
@@ -126,7 +170,7 @@ impl IndexMut<BitBoardPos> for BitBoard {
 }
 
 fn read_board() -> BitBoard {
-    let mut b = BitBoard { b: [[0u16; 9]; 9], };
+    let mut b = BitBoard::new();
 
     for i in 0..9 {
         let mut line = String::new();
@@ -157,13 +201,13 @@ impl fmt::Display for BitBoard {
         for i in self.b.iter() {
             for j in i.iter() {
                 if j.is_power_of_two() {
-                    write!(f, "{}", j.trailing_zeros())
+                    try!(write!(f, "{}", j.trailing_zeros()));
                 } else {
-                    write!(f, ".")
-                }.unwrap();
+                    try!(write!(f, "."));
+                }
             }
 
-            write!(f, "\n").unwrap();
+            try!(write!(f, "\n"));
         }
 
         Ok(())
@@ -179,10 +223,11 @@ fn check(b: &BitBoard) -> bool {
 
     /* 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})
+            .fold_while(0u16, |v, i|
+                        if v & b[i] != 0 { None }
+                        else { Some(v | b[i]) })
+            .is_some()
     }
 
     origin.row()    .all(|i| check_iter(b, &mut i.column())) &&
@@ -190,13 +235,40 @@ fn check(b: &BitBoard) -> bool {
     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 {
+/* Start of solver: */
+
+fn strike_solved(b: BitBoard, p: BitBoardPos) -> Option<BitBoard> {
     /*
-     * 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 @p is solved, strike it from every other cell in the same
+     * row/column/block:
      */
+    assert!(b[p].is_power_of_two());
+
+    let mut b = b;
+
+    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 {
+                println!("inconsistent at:\n{} {}", b, check(&b));
+                return None;
+            }
+        }
+    }
+
+    Some(b)
+}
+
+/*
+ * 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:
+ */
+fn constrain_single(b: BitBoard, p: BitBoardPos,
+                    iter: &mut Iterator<Item=BitBoardPos>) -> Option<BitBoard> {
     if !b[p].is_power_of_two() {
         let m = iter
             .filter(|i| *i != p)
@@ -205,98 +277,212 @@ fn solve_by_constraints(b: &mut BitBoard, p: BitBoardPos,
 
         if m.is_power_of_two() {
             if (b[p] & m) == 0 {
-                return false;
+                println!("inconsistent at:\n{} {}", b, check(&b));
+                return None;
             }
 
+            let mut b = b;
             b[p] = m;
+
+            return strike_solved(b, p);
         }
     }
 
-    true
+    Some(b)
 }
 
-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;
-    }
+/*
+fn constrain_multiple_block_col(
+    mut b: BitBoard,
+    block: &mut Iterator<Item=BitBoardPos>,
+    iter: &mut Iterator<Item=BitBoardPos>) -> Option<BitBoard> {
+    let by_block = [0u16; 9];
 
-    /*
-     * 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;
-                }
-            }
-        }
+    for i in iter {
     }
 
-    true
+    Some(b)
 }
 
-/* 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;
+fn constrain_multiple_block(
+    mut b: BitBoard,
+    block: &mut Iterator<Item=BitBoardPos>) -> Option<BitBoard> {
+}
 
-        if !each_pos().all(|i| solve_at_pos(b, i)) {
-            return false;
-        }
+fn constrain_multiple(mut b: BitBoard) -> Option<BitBoard> {
+    each_block()
+        .fold_while(b, |b, i| constrain_multiple_block(b, &mut i.block()))
+}
+*/
+
+fn do_solve(b: Option<BitBoard>) -> Option<BitBoard> {
+    b.and_then(|b| each_pos().fold_while(b, |b, i| 
+                                         constrain_single(b, i, &mut i.column())))
+     .and_then(|b| each_pos().fold_while(b, |b, i| 
+                                         constrain_single(b, i, &mut i.row())))
+     .and_then(|b| each_pos().fold_while(b, |b, i| 
+                                         constrain_single(b, i, &mut i.block())))
+     //.and_then(|b| constrain_multiple(b))
+}
+
+fn strike_initial_solved(b: Option<BitBoard>) -> Option<BitBoard> {
+    b.and_then(|b| each_pos()
+               .filter(|i| b[*i].is_power_of_two())
+               .fold_while(b, |b, i| strike_solved(b, i)))
+}
+
+fn solve(b: BitBoard) -> Vec<BitBoard> {
+    let b = match fixed_point(Some(b), strike_initial_solved) {
+        Some(b) => b,
+        None    => return Vec::new(),
+    };
 
-        prev != *b
-    } {}
+    let b = match fixed_point(Some(b), do_solve) {
+        Some(b) => b,
+        None    => return Vec::new(),
+    };
 
     /*
      * 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,
+        None        => vec![b],
         Some(i)     => {
             println!("backtracking at:\n{}", b);
 
-            for j in 1..10 {
-                if (b[i] & (1 << j)) != 0 {
-                    let mut r = *b;
+            let v = b[i];
+
+            (1..10)
+                .filter(|j| (v & (1 << *j)) != 0)
+                .flat_map(|j| {
+                    let mut r = b;
 
                     r[i] = 1 << j;
 
-                    if solve(&mut r) {
-                        *b = r;
-                        return true;
-                    }
+                    solve(r)})
+                .collect()
+        }
+    }
+}
 
-                    println!("inconsistent at:\n{} {}", r, check(&r));
-                }
-            }
+fn main() {
+    let b = read_board();
 
-            /*
-             * If none of the attempts worked, we were already had an
-             * inconsistent board but we needed multiple guesses to prove that:
-             */
-            return false;
+    println!("{} {}", b, check(&b));
+
+    let solutions = solve(b);
+
+    for i in solutions {
+        println!("{} {}", i, check(&i));
+    }
+}
+
+
+/*
+type Memoize = HashMap<BitBoard, Vec<BitBoard>>;
+
+fn solve_memoized(b: &BitBoard, memo: &mut Memoize) -> Vec<BitBoard> {
+    match memo.get(b) {
+        Some(i)     => return i.clone(),
+        None        => ()
+    }
+
+    let ret = solve(*b);
+
+    memo.insert(*b, ret.clone());
+
+    if memo.len() % 1000 == 0 {
+        println!("cached {} solutions", memo.len());
+    }
+
+    ret
+}
+
+fn make_harder_recurse(b: &BitBoard, memo: &mut Memoize) -> Vec<BitBoard> {
+    let nr_solutions = solve_memoized(&b, memo).len();
+
+    assert!(nr_solutions != 0);
+
+    if nr_solutions > 1 {
+        //println!("{} solutions at:\n{}", nr_solutions, b);
+        return Vec::new();
+    }
+
+    each_pos()
+        .filter(|i| b[*i].is_power_of_two())
+        .flat_map(|i| {
+            let mut r = *b;
+
+            r[i] = ALL_NUMS;
+
+            make_harder_recurse(&mut r, memo)})
+        .chain(vec![*b].into_iter())
+        .collect()
+}
+
+fn nr_set(b: &BitBoard) -> usize {
+    each_pos()
+        .filter(|i| b[*i].is_power_of_two())
+        .count()
+}
+
+fn make_harder(_b: BitBoard, memo: &mut Memoize) -> BitBoard {
+    let mut b = _b;
+    let mut nr_ret = nr_set(&b);
+
+    for i in each_pos() {
+        if !b[i].is_power_of_two() {
+            b[i] = ALL_NUMS;
+        }
+    }
+
+    let boards = make_harder_recurse(&b, memo);
+
+    assert!(boards.len() != 0);
+
+    for i in boards {
+        let nr_i = nr_set(&i);
+
+        if nr_i < nr_ret {
+            nr_ret = nr_i;
+            b = i;
         }
     }
+
+    b
 }
 
 fn main() {
-    let mut b = read_board();
+    let mut memo: Memoize = HashMap::new();
+
+    let b = read_board();
 
     println!("{} {}", b, check(&b));
 
-    solve(&mut b);
+    /*
+    let harder = make_harder(b, &mut memo);
 
-    println!("{} {}", b, check(&b));
+    println!("harder version: {} set, orig {} \n{}",
+             nr_set(&b),
+             nr_set(&harder),
+             harder);
+             */
+
+    let solutions = solve_memoized(&b, &mut memo);
+
+    println!("{} solutions:", solutions.len());
+
+    for i in solutions {
+        println!("{} {}", i, check(&i));
+        /*
+
+        let harder = make_harder(&i, &mut memo);
+
+        println!("harder version: {} set, orig {} \n{}",
+                 nr_set(&i),
+                 nr_set(&harder),
+                 harder);
+                 */
+    }
 }
+*/