path: root/src/main.rs

use std::fmt;
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 {
    x:          usize,
    y:          usize,
}

struct EachPos {
    i:          Range<usize>,
}

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 })
    }
}

fn each_pos() -> EachPos {
    EachPos { i: (0..81) }
}

struct EachBlock {
    i:          Range<usize>,
}

impl Iterator for EachBlock {
    type Item = BitBoardPos;

    fn next(&mut self) -> Option<BitBoardPos> {
        self.i.next().map(|i| BitBoardPos { x: i / 3 * 3, y: i % 3 * 3 })
    }
}

fn each_block() -> EachBlock {
    EachBlock { i: (0..9) }
}

struct Column {
    x:          usize,
    y:          Range<usize>,
}

impl Iterator for Column {
    type Item = BitBoardPos;

    fn next(&mut self) -> Option<BitBoardPos> {
        self.y.next().map(|y| BitBoardPos { x: self.x, y: y })
    }
}

struct Row {
    x:          Range<usize>,
    y:          usize,
}

impl Iterator for Row {
    type Item = BitBoardPos;

    fn next(&mut self) -> Option<BitBoardPos> {
        self.x.next().map(|x| BitBoardPos { x: x, y: self.y })
    }
}

struct Block {
    start:      BitBoardPos,
    i:          Range<usize>,
}

impl Iterator for Block {
    type Item = BitBoardPos;

    fn next(&mut self) -> Option<BitBoardPos> {
        self.i.next().map(|i| BitBoardPos {
            x: self.start.x + i / 3,
            y: self.start.y + i % 3
        })
    }
}

impl BitBoardPos {
    fn col(self) -> Column {
        Column  { x: self.x, y: (0..9), }
    }

    fn row(self) -> Row {
        Row     { x: (0..9), y: self.y, }
    }

    fn block(self) -> Block {
        Block {
            start: BitBoardPos {
                x: self.x / 3 * 3,
                y: self.y / 3 * 3,
            },
            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, Hash, Copy, Clone)]
struct BitBoard {
    b:  [[u16; 9]; 9],
}

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 {
    type Output = u16;

    fn index<'a>(&'a self, p: BitBoardPos) -> &'a u16 {
        &self.b[p.x][p.y]
    }
}

impl IndexMut<BitBoardPos> for BitBoard {
    fn index_mut<'a>(&'a mut self, p: BitBoardPos) -> &'a mut u16 {
        &mut self.b[p.x][p.y]
    }
}

fn read_board() -> BitBoard {
    let mut b = BitBoard::new();

    for i in 0..9 {
        let mut line = String::new();

        if io::stdin().read_line(&mut line).unwrap() < 9 {
            println!("didn't get sudoku line");
            exit(1);
        }

        for (j, c) in line.chars().enumerate() {
            if c == '\n' {
                break;
            }

            b.b[i][j] = if c == '.' {
                ALL_NUMS
            } else {
                1 << ((c as u32) - ('0' as u32)) as u16
            }
        }
    }

    b
}

impl fmt::Display for BitBoard {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for p in each_pos() {
            if p.x == 0 && p.y != 0 && p.y % 3 == 0 {
                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(())
    }
}

/*
 * Check if a board configuration is valid: not actually used in the solver,
 * just an additional check:
 */
fn check(b: &BitBoard) -> bool {
    let origin = BitBoardPos { x: 0, y: 0 };

    /* 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.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.col())) &&
    origin.col().all(|i| check_iter(b, &mut i.row())) &&
    each_block().all(|i| check_iter(b, &mut i.block()))
}

/* Start of solver: */

/*
 * 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:
     */
    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]);

            if b[i] == 0 {
                println!("inconsistent at:\n{}", 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(mut b: BitBoard, p: BitBoardPos,
                    iter: &mut Iterator<Item=BitBoardPos>) -> Option<BitBoard> {
    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() {
            b = b.set(p, m);

            if b[p] == 0 {
                println!("inconsistent at:\n{}", b);
                return None;
            }
        }
    }

    Some(b)
}

fn constrain_multiple(b: BitBoard, p: BitBoardPos) -> Option<BitBoard> {
    let mut b = b;

    if !b.pos_known(p) {
        let mut other_rows = 0u16;
        let mut other_cols = 0u16;

        for i in p.block() {
            if i.x != p.x {
                other_cols |= b[i];
            }

            if i.y != p.y {
                other_rows |= b[i];
            }
        }

        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);

            if b[i] == 0 {
                println!("inconsistent at:\n{}", b);
                return None;
            }
        }
    }

    Some(b)
}

fn solve(b: BitBoard) -> Vec<BitBoard> {
    /*
     * 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(),
    };

    /*
     * When we get stuck, if there's unsolved cells left switch to backtracking:
     */
    match each_pos().find(|p| !b.pos_known(*p)) {
        None        => vec![b],
        Some(p)     => {
            println!("backtracking ({} solved {} choices):\n{}", b.nr_known(), b.nr_choices(), b);

            (1..10)
                .filter(|i| (b[p] & (1 << *i)) != 0)
                .flat_map(|i| solve(b.set(p, 1 << i)))
                .collect()
        }
    }
}

fn main() {
    let b = read_board();

    println!("Solving:\n{}", b);

    let solutions = solve(b);

    println!("Found {} solutions:", solutions.len());

    for i in solutions {
        println!("{} {}", i, check(&i));
    }
}