sudoku-solver-rust/src/hecht.rs

use std::collections::HashSet;
use crate::solver::{Solver, Generator, SodokuComplexity};
use crate::board::Board;
use crate::utils::*;
use std::rc::Rc;
use std::hash::{Hash, Hasher};

const NUM : usize = 3;
const VALUES : usize = NUM * NUM;
const CELLS : usize = VALUES * VALUES;
type TodoType<T> = IndexableVec<T, CELLS>;
// type TodoType<T> = HashSet<T>;


pub struct HechtSolver {
}


#[derive(Hash, Clone, Eq, PartialEq, Debug, Copy)]
struct Point {
    pub x: usize,
    pub y: usize,
    pub s: usize,
}

#[derive(Debug, Clone, Eq, PartialEq, Hash)]
enum Action {
    Trivial(Point, u16),
    Logic(Point, u16),
    Probe(Point, u16),
}


#[derive(Clone)]
struct SolverBoard {
    arr: [[u16; VALUES]; VALUES],
    todos: TodoType<Point>,
    valid: bool,
}

enum SolverBoardItem {
    Process(Rc<SolverBoard>, Action),
    Initial(SolverBoard),
}

struct SolverBoardIterator {
    cache: HashSet<[[u16; VALUES]; VALUES]>, // to avoid processing the same board twice
    stack: Vec<SolverBoardItem>,
    solve: bool,
}

impl PartialEq for SolverBoard {
    fn eq(&self, other: &SolverBoard) -> bool {
        self.arr == other.arr && self.valid == other.valid
    }
}

impl Hash for SolverBoard {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.arr.hash(state);
    }
}

impl HechtSolver {
    pub fn new() -> HechtSolver {
        return HechtSolver {};
    }
    
    pub fn test(&self, board: &Board) {
        let count = SolverBoardIterator::new(board)
            .filter(|x| x.is_solved())
            .inspect(|_| println!("Solved Board detected"))
            .count();
        println!("Count: {}", count);
            
    }

    
}

impl Solver for HechtSolver {
    fn solve(&self, board: &Board) -> Option<Board> {
        SolverBoardIterator::new(board)
            .find(|x| x.is_solved())
            .map(|x| x.to_board())
            .flatten()
    }
    
    fn is_unique(&self, board: &Board) -> bool {
        SolverBoardIterator::new(board)
            .filter(|x| x.is_solved())
            .nth(1).is_none()
    }
}

impl Generator for HechtSolver {
    fn generate(&self, _complexity:SodokuComplexity) -> Board {
        let board = Board::new();

        SolverBoardIterator::new(&board)
            .filter_map(|x| x.to_board())
            .filter(|board| self.is_unique(board))
            .next()
            .unwrap_or(board)

    }

}

impl SolverBoard {
    
    pub fn new() -> SolverBoard {
        let points = [0usize..CELLS].into_iter().flatten()
            .map(|idx| Point::from_index(idx))
            .collect::<TodoType<_>>();
            
        SolverBoard { arr: [[0x1FFu16; VALUES]; VALUES], todos: points, valid: true}
    }
    
    pub fn from(pg: &Board) -> SolverBoard {
        let mut spg = SolverBoard::new();

        for idx in 0usize..CELLS {
            let p = Point::from_index(idx);
            if let Some(value) = pg.get_value(p.x, p.y) {
                spg.set_value(&p, value);
                assert!(spg.valid);
            }
        }
        
        spg.solve_logically();
        spg
    }
    
    fn to_board(&self) -> Option<Board> {
        let mut pg = Board::new();
        
        for x in 0..VALUES {
            for y in 0..VALUES {
                let value = self.arr[y][x];
                if value.count_ones() == 1 {
                    pg.set_value(x, y, (value.trailing_zeros() + 1) as u8);
                }
            }
        }
        
        Some(pg)
    }

    fn solve_logically(&mut self) {
        while self.valid {
            if let Some(action) = self.get_simple_action() {
                self.apply(action);
            } else {
                break;
            }
        }
    }
    
    fn is_solved(&self) -> bool {
        self.valid && self.todos.len() == 0
    }

    fn set_value(&mut self, p : &Point, value : u8) {
        let bit_value = 1u16 << (value - 1);
        self.set_bit_value(p, bit_value)
    }
    
    fn get_sector(index : usize) -> usize {
        static SECTOR_ARRAY : [usize; CELLS] = [
            0,0,0,1,1,1,2,2,2,
            0,0,0,1,1,1,2,2,2,
            0,0,0,1,1,1,2,2,2,
            3,3,3,4,4,4,5,5,5,
            3,3,3,4,4,4,5,5,5,
            3,3,3,4,4,4,5,5,5,
            6,6,6,7,7,7,8,8,8,
            6,6,6,7,7,7,8,8,8,
            6,6,6,7,7,7,8,8,8,
        ];
        SECTOR_ARRAY[index]
    }

    #[inline]
    fn get_y(index : usize) -> usize {
        index / VALUES
    }

    #[inline]
    fn get_x(index : usize) -> usize {
        index % VALUES
    }
    
    fn set_bit_value(&mut self, p : &Point, bit_value : u16) {
        assert!(bit_value.count_ones() == 1);
        if !self.todos.remove(p) {
            // Point was not in todo-list -> no further action required
            return;
        }

        self.arr[p.y][p.x] = bit_value;

        for idx in 0..CELLS {
            let other = Point::from_index(idx);
            if p != &other && (other.x == p.x || other.y == p.y || other.s == p.s) {
                self.remove_value(other, bit_value)
            }
        }

    }
    
    fn remove_value(&mut self, p : Point, bit_value: u16) {
        if (self.arr[p.y][p.x] & bit_value) == 0 {
            return;
        }
        self.arr[p.y][p.x] &= !bit_value;
        let point_value = self.arr[p.y][p.x];
        
        match point_value.count_ones() {
            1 => self.apply(Action::Trivial(p, point_value)),
            0 => self.valid = false,
            _ => {}
        }
    }
    
    fn create_action(p : &Point, bit_value: u16) -> Option<Action> {
        if bit_value.count_ones() != 1 {
            return None;
        }
        Some(Action::Logic(p.clone(), bit_value))
    }
    
    fn apply(&mut self, action : Action) {
        let (point, value) = action.get();
        self.set_bit_value(point, value);
        
        if let Action::Probe(_,_) = action {
            self.solve_logically();
        }
    }
    
    #[inline]
    fn get_bitvalue_sequence() -> &'static[u16; VALUES] {
        return &[0b0_0000_0001u16, // 1
                 0b0_0000_0010u16, // 2
                 0b0_0000_0100u16, // 3
                 0b0_0000_1000u16, // 4
                 0b0_0001_0000u16, // 5
                 0b0_0010_0000u16, // 6
                 0b0_0100_0000u16, // 7
                 0b0_1000_0000u16, // 8
                 0b1_0000_0000u16]; // 9
    }
    
    #[inline]
    fn get_value(&self, p : &Point) -> u16 {
        return self.arr[p.y][p.x];
    }

    fn get_simple_action(&self) -> Option<Action> {
        
        // println!("Simple Action");
        self.todos.iter()
            .find_map(|lhs| {
                    let own_value = self.get_value(lhs);
                    self.todos.iter()
                        .filter(|&rhs| lhs.x == rhs.x || lhs.y == rhs.y || lhs.s == rhs.s)
                        .filter(|&rhs| lhs != rhs)
                        .map(|rhs| {
                            let value = self.get_value(&rhs) & own_value;
                            let row_value = if lhs.x == rhs.x {value} else {0};
                            let col_value = if lhs.y == rhs.y {value} else {0};
                            let sec_value = if lhs.s == rhs.s {value} else {0};
                            
                            [row_value, col_value, sec_value]
                        } )
                        .reduce(|a,b| [a[0]|b[0], a[1]|b[1], a[2]|b[2]])
                        .iter()
                        .flatten()
                        .map(|value| value ^ own_value)
                        .filter(|value| value.count_ones() == 1)
                        .find_map(|value| SolverBoard::create_action(lhs, value))
                } )
    }

    fn get_probe_actions(&self) -> Vec<Action> {
        let result = self.todos.iter()
            .min_by_key(|point| self.get_value(point).count_ones());

        if let Some(point) = result {
            let p_value = self.get_value(point);
            return SolverBoard::get_bitvalue_sequence().iter()
                .filter(|&value| (p_value & value ) != 0)
                .map(|&value| Action::Probe(point.clone(), value))
                .collect();
        }
        Vec::new()
    }
    
}

impl SolverBoardIterator {
    fn new(board : &Board) -> SolverBoardIterator {
        SolverBoardIterator::from_board(SolverBoard::from(board))
    }
    
    fn from_board(board: SolverBoard) -> SolverBoardIterator {
        SolverBoardIterator{cache: HashSet::with_capacity(128), stack: vec![SolverBoardItem::Initial(board)], solve: true}
    }
    
    fn next_board(&mut self) -> Option<SolverBoard> {
        while let Some(item) = self.stack.pop() {
            println!("Stack size {}, cache size {}", self.stack.len(), self.cache.len());
            if let Some(board) = self.pop_board(item) {
                return Some(board);
            }
        }
        
        None
    }
    
    fn pop_board(&mut self, item : SolverBoardItem) -> Option<SolverBoard> {
        match item {
            SolverBoardItem::Initial(board) => {
                self.handle_initial(board)
            }
            SolverBoardItem::Process(board, action) => {
                self.handle_process(board, action)
            }
        }
    }
    
    fn handle_initial(&mut self, board: SolverBoard) -> Option<SolverBoard> {
        if board.valid {
            return self.handle_board(Rc::new(board))
        }
        None
    }

    fn handle_process(&mut self, board_ref: Rc<SolverBoard>, action: Action) -> Option<SolverBoard> {
        let mut board_ref = board_ref; // re-label
        let board = Rc::make_mut(&mut board_ref);
        
        // println!(" {} --> {:?}", board.todos.len(), action);
        board.apply(action);
        
        if !board.valid || !self.cache.insert(board.arr) {
            return None;
        }
        
        return self.handle_board(board_ref);
    }
    

    fn handle_board(&mut self, board: Rc<SolverBoard>)-> Option<SolverBoard> {
        if !board.is_solved() {
            
            let actions = board.get_probe_actions();
            actions.into_iter()
                   .for_each(|action| self.stack.push(SolverBoardItem::Process(Rc::clone(&board), action)))
        }
        Some((*board).clone())
    }
    
}

impl Iterator for SolverBoardIterator {
    type Item = SolverBoard;
    
    fn next(&mut self) -> Option<Self::Item> {
        self.next_board()
    }
}

impl Action {
    fn get(&self) -> (&Point, u16) {
        match self {
            Action::Logic(point,value) | Action::Probe(point,value) | Action::Trivial(point,value) => return (point, *value)
        }
    }
}

impl Indexable for Point {
    fn to_index(&self) -> usize {
        self.y * VALUES + self.x
    }
}

impl Point {
    fn from_xy(x: usize, y: usize) -> Point {
        Point{x, y, s: (y / NUM) * NUM + x / NUM}
    }
    
    fn from_index(idx: usize) -> Point {
        Point{x: SolverBoard::get_x(idx), y: SolverBoard::get_y(idx), s: SolverBoard::get_sector(idx)}
    }
}