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;

#[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 column(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),
        }
    }
}

const  ALL_NUMS: u16 = ((1 << 9) - 1) << 1;

#[derive(Eq, PartialEq, Copy, Clone)]
struct BitBoard {
    b:  [[u16; 9]; 9],
}

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 { b: [[0u16; 9]; 9], };

    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 i in self.b.iter() {
            for j in i.iter() {
                if j.is_power_of_two() {
                    write!(f, "{}", j.trailing_zeros())
                } else {
                    write!(f, ".")
                }.unwrap();
            }

            write!(f, "\n").unwrap();
        }

        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 {
        let mut v = 0u16;

        iter.filter(|i| b[*i].is_power_of_two())
            .all(|i| (v & b[i]) == 0 && {v |= b[i]; true})
    }

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

fn solve_by_constraints(b: &mut BitBoard, p: BitBoardPos,
                        iter: &mut Iterator<Item=BitBoardPos>) -> bool {
    /*
     * 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 !b[p].is_power_of_two() {
        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 {
                return false;
            }

            b[p] = m;
        }
    }

    true
}

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

    /*
     * 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;
                }
            }
        }
    }

    true
}

/* 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;

        if !each_pos().all(|i| solve_at_pos(b, i)) {
            return false;
        }

        prev != *b
    } {}

    /*
     * 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,
        Some(i)     => {
            println!("backtracking at:\n{}", b);

            for j in 1..10 {
                if (b[i] & (1 << j)) != 0 {
                    let mut r = *b;

                    r[i] = 1 << j;

                    if solve(&mut r) {
                        *b = r;
                        return true;
                    }

                    println!("inconsistent at:\n{} {}", r, check(&r));
                }
            }

            /*
             * If none of the attempts worked, we were already had an
             * inconsistent board but we needed multiple guesses to prove that:
             */
            return false;
        }
    }
}

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

    println!("{} {}", b, check(&b));

    solve(&mut b);

    println!("{} {}", b, check(&b));
}