summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorKent Overstreet <kent.overstreet@gmail.com>2016-06-29 01:53:20 -0800
committerKent Overstreet <kent.overstreet@gmail.com>2016-06-29 01:53:20 -0800
commitd9b3f87c02eacb3c2dde18eb9099046b2b1886d6 (patch)
treea724a81c2ae50342bac5039da3677c003c2b6335 /src
parent163e12484f847624673485d22b49fa6dbb15b994 (diff)
downloadsudoku-d9b3f87c02eacb3c2dde18eb9099046b2b1886d6.tar.zst
foo
Diffstat (limited to 'src')
-rw-r--r--src/main.rs328
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);
+ */
+ }
}
+*/