From adacfac9cebc77f9da41229f45bd6228a2e8798f Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Thu, 30 Jun 2016 17:59:06 -0800 Subject: bar --- .gitignore | 1 + src/main.rs | 320 ++++++++++++++++++++++++------------------------------------ 2 files changed, 126 insertions(+), 195 deletions(-) create mode 100644 .gitignore 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 { - 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 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) -> 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 { +/* + * 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 { /* * 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 { * 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) -> Option { - 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, - iter: &mut Iterator) -> Option { - let by_block = [0u16; 9]; +fn constrain_multiple(b: BitBoard, p: BitBoardPos) -> Option { + 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) -> Option { -} + if i.y != p.y { + other_rows |= b[i]; + } + } -fn constrain_multiple(mut b: BitBoard) -> Option { - each_block() - .fold_while(b, |b, i| constrain_multiple_block(b, &mut i.block())) -} -*/ - -fn do_solve(b: Option) -> Option { - 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) -> Option { - 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 { - 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 { /* * 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 { 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>; - -fn solve_memoized(b: &BitBoard, memo: &mut Memoize) -> Vec { - 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 { - 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); - */ } } -*/ -- cgit v1.2.3