From d9b3f87c02eacb3c2dde18eb9099046b2b1886d6 Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Wed, 29 Jun 2016 01:53:20 -0800 Subject: foo --- src/main.rs | 328 +++++++++++++++++++++++++++++++++++++++++++++++------------- 1 file 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(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(self, init: T, mut f: F) -> Option where + Self: Sized, F: FnMut(T, Self::Item) -> Option, + { + let mut accum = init; + for x in self { + accum = match f(accum, x) { + Some(a) => a, + None => return None + } + + } + Some(accum) + } +} + +impl 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 for BitBoard { type Output = u16; @@ -126,7 +170,7 @@ impl IndexMut 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) -> 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) -> bool { +/* Start of solver: */ + +fn strike_solved(b: BitBoard, p: BitBoardPos) -> Option { /* - * 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) -> Option { 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, + iter: &mut Iterator) -> Option { + 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) -> Option { +} - if !each_pos().all(|i| solve_at_pos(b, i)) { - return false; - } +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)) +} + +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))) +} + +fn solve(b: BitBoard) -> Vec { + 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>; + +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 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); + */ + } } +*/ -- cgit v1.2.3