barHEADmaster

2 files changed, 126 insertions, 195 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..eb5a316
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+target
diff --git a/src/main.rs b/src/main.rs
index 2e2d4d8..0e105d1 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -52,7 +52,7 @@ 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 })
+        self.i.next().map(|i| BitBoardPos { x: i % 9, y: i / 9 })
     }
 }
 
@@ -119,7 +119,7 @@ impl Iterator for Block {
 }
 
 impl BitBoardPos {
-    fn column(self) -> Column {
+    fn col(self) -> Column {
         Column  { x: self.x, y: (0..9), }
     }
 
@@ -153,6 +153,32 @@ impl BitBoard {
     fn new() -> BitBoard {
         BitBoard { b: [[ALL_NUMS; 9]; 9], }
     }
+
+    fn pos_known(&self, p: BitBoardPos) -> bool {
+        self[p].is_power_of_two()
+    }
+
+    fn nr_known(&self) -> usize {
+        each_pos()
+            .filter(|p| self.pos_known(*p))
+            .count()
+    }
+
+    fn nr_choices(&self) -> u32 {
+        each_pos().fold(0, |a, i| a + self[i].count_ones())
+    }
+
+    fn clear(&self, p: BitBoardPos, v: u16) -> BitBoard {
+        let mut b = *self;
+        b[p] &= v ^ ALL_NUMS;
+        b
+    }
+
+    fn set(&self, p: BitBoardPos, v: u16) -> BitBoard {
+        let mut b = *self;
+        b[p] &= v;
+        b
+    }
 }
 
 impl Index<BitBoardPos> for BitBoard {
@@ -198,16 +224,24 @@ fn read_board() -> BitBoard {
 
 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() {
-                    try!(write!(f, "{}", j.trailing_zeros()));
-                } else {
-                    try!(write!(f, "."));
-                }
+        for p in each_pos() {
+            if p.x == 0 && p.y != 0 && p.y % 3 == 0 {
+                try!(write!(f, "-------|-------|-------\n"));
             }
 
-            try!(write!(f, "\n"));
+            if p.x != 0 && p.x % 3 == 0 {
+                try!(write!(f, " |"));
+            }
+
+            if self.pos_known(p) {
+                try!(write!(f, " {}", self[p].trailing_zeros()));
+            } else {
+                try!(write!(f, " ."));
+            }
+
+            if p.x == 8 {
+                try!(write!(f, "\n"));
+            }
         }
 
         Ok(())
@@ -223,37 +257,38 @@ 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 {
-        iter.filter(|i| b[*i].is_power_of_two())
+        iter.filter(|i| b.pos_known(*i))
             .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())) &&
-    origin.column() .all(|i| check_iter(b, &mut i.row())) &&
-    each_block()    .all(|i| check_iter(b, &mut i.block()))
+    origin.row().all(|i| check_iter(b, &mut i.col())) &&
+    origin.col().all(|i| check_iter(b, &mut i.row())) &&
+    each_block().all(|i| check_iter(b, &mut i.block()))
 }
 
 /* Start of solver: */
 
-fn strike_solved(b: BitBoard, p: BitBoardPos) -> Option<BitBoard> {
+/*
+ * Given a position that we know the answer for, strike that number as a possibility from every
+ * other position in the same row, column and block:
+ */
+fn strike_solved(mut b: BitBoard, p: BitBoardPos) -> Option<BitBoard> {
     /*
      * if @p is solved, strike it from every other cell in the same
      * row/column/block:
      */
-    assert!(b[p].is_power_of_two());
+    if b.pos_known(p) {
+        for i in p.col()
+            .chain(p.row())
+            .chain(p.block())
+            .filter(|i| *i != p) {
+            b = b.clear(i, b[p]);
 
-    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));
+                println!("inconsistent at:\n{}", b);
                 return None;
             }
         }
@@ -267,77 +302,87 @@ fn strike_solved(b: BitBoard, p: BitBoardPos) -> Option<BitBoard> {
  * 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,
+fn constrain_single(mut b: BitBoard, p: BitBoardPos,
                     iter: &mut Iterator<Item=BitBoardPos>) -> Option<BitBoard> {
-    if !b[p].is_power_of_two() {
+    if !b.pos_known(p) {
         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 {
-                println!("inconsistent at:\n{} {}", b, check(&b));
+            b = b.set(p, m);
+
+            if b[p] == 0 {
+                println!("inconsistent at:\n{}", b);
                 return None;
             }
-
-            let mut b = b;
-            b[p] = m;
-
-            return strike_solved(b, p);
         }
     }
 
     Some(b)
 }
 
-/*
-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];
+fn constrain_multiple(b: BitBoard, p: BitBoardPos) -> Option<BitBoard> {
+    let mut b = b;
 
-    for i in iter {
-    }
+    if !b.pos_known(p) {
+        let mut other_rows = 0u16;
+        let mut other_cols = 0u16;
 
-    Some(b)
-}
+        for i in p.block() {
+            if i.x != p.x {
+                other_cols |= b[i];
+            }
 
-fn constrain_multiple_block(
-    mut b: BitBoard,
-    block: &mut Iterator<Item=BitBoardPos>) -> Option<BitBoard> {
-}
+            if i.y != p.y {
+                other_rows |= b[i];
+            }
+        }
 
-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))
-}
+        for i in p.col().filter(|i| i.blocknr() != p.blocknr()) {
+            b = b.set(i, other_cols);
+
+            if b[i] == 0 {
+                println!("inconsistent at:\n{}", b);
+                return None;
+            }
+        }
+
+        for i in p.row().filter(|i| i.blocknr() != p.blocknr()) {
+            b = b.set(i, other_rows);
 
-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)))
+            if b[i] == 0 {
+                println!("inconsistent at:\n{}", b);
+                return None;
+            }
+        }
+    }
+
+    Some(b)
 }
 
 fn solve(b: BitBoard) -> Vec<BitBoard> {
-    let b = match fixed_point(Some(b), strike_initial_solved) {
-        Some(b) => b,
-        None    => return Vec::new(),
-    };
-
-    let b = match fixed_point(Some(b), do_solve) {
+    /*
+     * Try to solve with the various constraint solvers until we hit a fixed point - until we
+     * either get stuck, or discover that we were inconsistent (because we were guessing in the
+     * backtracking solver:
+     *
+     * The nested fixed point iterations try the cheaper solvers first:
+     */
+    let b = match fixed_point(Some(b), |b| {
+        let b = fixed_point(b, |b| {
+            let b = fixed_point(b, |b| {
+                b.and_then(|b| each_pos().fold_while(b, |b, i| strike_solved(b, i)))
+            });
+
+            b.and_then(|b| each_pos().fold_while(b, |b, i| constrain_single(b, i, &mut i.col())))
+             .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())))
+        });
+
+        b.and_then(|b| each_pos().fold_while(b, |b, i| constrain_multiple(b, i)))
+    }) {
         Some(b) => b,
         None    => return Vec::new(),
     };
@@ -345,21 +390,14 @@ fn solve(b: BitBoard) -> Vec<BitBoard> {
     /*
      * When we get stuck, if there's unsolved cells left switch to backtracking:
      */
-    match each_pos().find(|i| !b[*i].is_power_of_two()) {
+    match each_pos().find(|p| !b.pos_known(*p)) {
         None        => vec![b],
-        Some(i)     => {
-            println!("backtracking at:\n{}", b);
-
-            let v = b[i];
+        Some(p)     => {
+            println!("backtracking ({} solved {} choices):\n{}", b.nr_known(), b.nr_choices(), b);
 
             (1..10)
-                .filter(|j| (v & (1 << *j)) != 0)
-                .flat_map(|j| {
-                    let mut r = b;
-
-                    r[i] = 1 << j;
-
-                    solve(r)})
+                .filter(|i| (b[p] & (1 << *i)) != 0)
+                .flat_map(|i| solve(b.set(p, 1 << i)))
                 .collect()
         }
     }
@@ -368,121 +406,13 @@ fn solve(b: BitBoard) -> Vec<BitBoard> {
 fn main() {
     let b = read_board();
 
-    println!("{} {}", b, check(&b));
+    println!("Solving:\n{}", 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 memo: Memoize = HashMap::new();
-
-    let b = read_board();
-
-    println!("{} {}", b, check(&b));
-
-    /*
-    let harder = make_harder(b, &mut memo);
-
-    println!("harder version: {} set, orig {} \n{}",
-             nr_set(&b),
-             nr_set(&harder),
-             harder);
-             */
-
-    let solutions = solve_memoized(&b, &mut memo);
-
-    println!("{} solutions:", solutions.len());
+    println!("Found {} 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);
-                 */
     }
 }
-*/