summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorKent Overstreet <kent.overstreet@gmail.com>2016-06-30 17:59:06 -0800
committerKent Overstreet <kent.overstreet@gmail.com>2016-06-30 17:59:06 -0800
commitadacfac9cebc77f9da41229f45bd6228a2e8798f (patch)
tree4750d049f8d5bf46e3ef0b74ddfe7bead873253c /src
parentd9b3f87c02eacb3c2dde18eb9099046b2b1886d6 (diff)
downloadsudoku-adacfac9cebc77f9da41229f45bd6228a2e8798f.tar.zst
Diffstat (limited to 'src')
-rw-r--r--src/main.rs320
1 files changed, 125 insertions, 195 deletions
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);
- */
}
}
-*/