sudoku.rs

use std::cell::Cell;
use std::fmt::{self, Display};
use std::collections::HashSet;

const ORDER: usize = 3;
const OR2: usize = ORDER * ORDER;
const OR4: usize = OR2 * OR2;

#[derive(Copy, Clone, Debug)]
struct SCell {
    fixed: Option<usize>,
    possible: [bool; OR2],
    // Rust issue: I would like to have references to what scopes contain this cell here
}

impl SCell {
    pub fn new() -> SCell { SCell { fixed: None, possible: [true; OR2] } }

    // Set this cell to a fixed number.
    pub fn fix(&mut self, v: usize) -> bool {
        if self.fixed == Some(v) { return false; }
        self.fixed = Some(v);

        for (i, ref mut vv) in self.possible.iter_mut().enumerate() { **vv = v == i };
        // println!("Fixed: {:?}!", self);
        true
    }

    // Take away the possibility that this cell can contain this value
    pub fn reduce(&mut self, v: usize) -> bool {
        if !self.possible[v] { return false; }
        self.possible[v] = false;
        assert_eq!(self.fixed, None);

        // Set fixed if only one possibility left
        let mut h = None;
        for (i, vv) in self.possible.iter().enumerate() {
            if *vv { if h == None { h = Some(i); } else { return true; }}
        }
        self.fix(h.unwrap())
    }
} 

impl Display for SCell {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        match self.fixed {
            None => write!(f, "*"),
            Some(s) => write!(f, "{}", s+1),
        }
    }
}

fn same_cell(a: &Cell<SCell>, b: &Cell<SCell>) -> bool {
     return a as *const Cell<SCell> == b as *const Cell<SCell>;
}

#[derive(Debug)]
struct SScope<'a> {
    name: String, // Debug
    cells: Vec<& 'a Cell<SCell>>,
}

impl<'a> SScope<'a> {
    pub fn new(table: &'a [Cell<SCell>]) -> Vec<SScope<'a>> {
        let rows: Vec<SScope<'a>> = (0..OR2).map(|y| SScope {
            name: format!("Row {}", y),
            cells: (0..OR2).map(|x| &table[y * OR2 + x]).collect()
        }).collect();
        let cols: Vec<SScope<'a>> = (0..OR2).map(|x| SScope {
            name: format!("Col {}", x),
            cells: (0..OR2).map(|y| &table[y * OR2 + x]).collect()
        }).collect();
        let boxes: Vec<SScope<'a>> = (0..OR2).map(|a| SScope {
            name: format!("Box {}", a),
            cells: (0..OR2).map(|b| {
                let y = (a / ORDER) * ORDER + (b % ORDER);
                let x = (a % ORDER) * ORDER + (b / ORDER);
                // println!("Box {}, cell {}:{}", a, y, x);
                &table[y * OR2 + x]
            }).collect()
        }).collect();

        let mut scopes = boxes;
        scopes.extend(rows);
        scopes.extend(cols);
        scopes
    }

    pub fn cell_update<F: FnMut(&'a Cell<SCell>)>(&self, c: &Cell<SCell>, mut f: F) {
        if self.cells.iter().position(|cc| same_cell(c, cc)).is_none() { return; }
        // println!("Visiting scope {}", self.name);

        // If a number just got fixed, then we can remove that possibility from the rest
        if let Some(n) = c.get().fixed {
            for cc in self.cells.iter().filter(|cc| !same_cell(c, cc)) {
                let mut z = cc.get();
                if z.reduce(n) {
                    cc.set(z);
                    f(cc);
                }
            }
        }

        // For every non-possibility, check if there's only one possibility left for that number
        for i in (0..OR2) {
            if c.get().possible[i] { continue; }
            let mut t = None;
            for cc in self.cells.iter() {
                if cc.get().possible[i] {
                    if t.is_none() { t = Some(cc) } else { t = None; break }
                }
            }
            if let Some(cc) = t {
                let mut z = cc.get();
                if z.fix(i) {
                    cc.set(z);
                    f(cc);
                }
            }
        }
    }

    pub fn solved(&self) -> bool {
        let mut h = HashSet::new();
        self.cells.iter().all(|x| {
            if let Some(z) = x.get().fixed {
                // Verify that we have one of each number
                assert!(z < OR2);
                assert!(!h.contains(&z));
                h.insert(z);
                // println!("Verified {} {} ", self.name, z);
                true
            }
            else { false }
        })
    }
}

#[derive(Debug)]
struct Sudoku<'a> {
    // Rust issue: I wanted to have fixed arrays here, but they cannot
    // be initialized. :-(
    table: &'a [Cell<SCell>],
    scopes: &'a [SScope<'a>],

    queue: Vec<&'a Cell<SCell>>,
}

impl<'a> Display for Sudoku<'a> {
    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        for (i, s) in self.table.iter().enumerate() {
            let c = s.get();
            match i % OR2 {
                0 => try!(write!(f, "{}", c)),
                // Rust issue: Cannot match on OR2-1 directly
                z if z == OR2-1 => try!(write!(f, " {}\n", c)),
                _ => try!(write!(f, " {}", c)),
            }
        }
        Ok(())
    }
}

impl<'a> Sudoku<'a> {
    pub fn solve(&mut self) -> bool {
        // Push all pre-initalized values for checking
        for i in self.table {
            if i.get().fixed.is_some() { self.queue.push(i) }
        }
        while let Some(c) = self.queue.pop() {
            for s in self.scopes { s.cell_update(c, |cc| self.queue.push(cc)); }
        }

        self.scopes.iter().all(|x| x.solved())
    }
}

#[cfg(test)]
mod tests {

// Rust issue: words() is unstable, so I can't make anything with line feeds
const MEDIUM_INPUT: &'static str = "\
* * * * 6 * * * * \
9 * * 2 * * * 4 8 \
2 * * * 4 * * * * \
7 3 * * * * * * 5 \
* * 5 1 * 8 3 * * \
* 9 * * * * * * 7 \
* 1 6 9 * * * 5 * \
* * 3 * * 5 * 9 * \
* * * * * * 8 6 1";


#[test]
fn solve_medium() {
    use super::{SCell, OR4, SScope, Sudoku};
    use std::cell::Cell;

    let table = vec!(Cell::new(SCell::new()); OR4);
    let scopes = SScope::new(&table);
    let mut s = Sudoku { table: &table, scopes: &scopes, queue: vec!() };
    for (i, val) in MEDIUM_INPUT.split(" ").enumerate() {
        if let Ok(n) = val.parse::<usize>() { 
            let mut z = table[i].get();
            if z.fix(n-1) { table[i].set(z); }
        }
        //println!("After {:?}!", table[i].get().fixed);
    }
    println!("Before:\n{}\n", s);
    let ss = s.solve();
    println!("After:\n{}\n", s);
    assert!(ss);
}

}