sudoku-rust/sudoku/src/sudoku.rs

// pub mod group;
use crate::group::*;

// use std::collections::HashSet;
use std::string::String;

/// Width of the sudoku board.
const WIDTH: u8 = 9;
/// Size (width * height) of the board.
const MAX_SIZE: u8 = 81;

// Use bitfields instead of HashSets.
use bit_field::BitField;

extern crate rand_chacha;
use rand::prelude::*;
use rand::seq::SliceRandom;
use rand_chacha::rand_core::SeedableRng;
use rand_chacha::ChaCha20Rng;

#[derive(Debug, Copy, Clone, PartialEq)]
pub struct Possible(u16);

/// Set bits number of bits to 1 (true)
pub const fn set_bits(bits: u8) -> u16 {
    (1 << (bits)) - 1
}

impl Possible {
    /// clear all bits
    pub fn clear(&mut self) {
        self.0 = 0;
    }

    /// set bit to state of value.
    pub fn set(&mut self, bit: u8, value: bool) {
        self.0.set_bit(bit as usize, value);
    }

    /// get state of bit.
    pub fn get(&self, bit: u8) -> bool {
        self.0.get_bit(bit as usize)
    }

    /// set bits on, given number of bits initially to set.
    pub fn set_bits(&mut self, bits: u8) {
        self.0 = set_bits(bits);
    }

    /// count number of bits set.
    pub fn count_set(&self) -> u8 {
        let mut count = 0;
        for i in 0..u16::BIT_LENGTH {
            if self.get(i as u8) {
                count += 1;
            }
        }
        count
    }
}

struct PossibleIterator<'a> {
    possible: &'a Possible,
    index: u8,
}

impl Possible {
    fn iter(&self) -> PossibleIterator {
        PossibleIterator {
            possible: self,
            index: 1,
        }
    }
}

impl<'a> Iterator for PossibleIterator<'a> {
    type Item = u8;

    fn next(&mut self) -> Option<u8> {
        while (self.index < u16::BIT_LENGTH as u8) && (!self.possible.get(self.index)) {
            self.index += 1;
            // println!("index = {}", self.index);
        }
        if self.index == u16::BIT_LENGTH as u8 {
            None
        } else {
            self.index += 1;
            Some(self.index - 1)
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::sudoku::*;

    #[test]
    fn check_possible_bitset() {
        let mut p = Possible(0);

        p.clear();

        for i in 0..9 {
            let mut result = p.get(i);
            assert_eq!(result, false);
            p.set(i, true);
            result = p.get(i);
            assert_eq!(result, true);
        }
    }

    #[test]
    fn check_possible_iter() {
        let mut p = Possible(0);
        p.set(3, true);
        p.set(5, true);
        p.set(6, true);
        assert_eq!(3, p.count_set());
        let values: Vec<u8> = p.iter().collect();
        assert_eq!(values, vec!(3, 5, 6));
        assert_eq!(3, p.count_set());
        p.set(0, true);
        assert_eq!(4, p.count_set());
    }

    #[test]
    fn check_bits() {
        // Set bits 0-5 (6 bits total)
        let p = Possible(set_bits(6));

        for i in 0..6 {
            let result = p.get(i);
            assert_eq!(result, true);
        }
        assert_eq!(p.get(6), false);
    }
}

pub type SudokuBoard = [u8; MAX_SIZE as usize];
pub type SudokuPossible = [Possible; MAX_SIZE as usize];

#[derive(Debug)]
pub struct Sudoku {
    pub board: [u8; MAX_SIZE as usize],
    // pub possible: [HashSet<u8>; MAX_SIZE as usize],
    pub possible: [Possible; MAX_SIZE as usize],
}

/// Translate x,y to position in board.
pub const fn pos(x: u8, y: u8) -> u8 {
    x + (y * WIDTH as u8)
}

/// Translate x,y (with starting index of 1) to position in board.
pub const fn pos1(x: u8, y: u8) -> u8 {
    (x - 1) + ((y - 1) * WIDTH as u8)
}

/// Translate post to x,y in board.
pub const fn xy(pos: u8) -> (u8, u8) {
    ((pos % WIDTH), (pos / WIDTH))
}

const DEBUG_OUTPUT: bool = false;

/*
(0 .. 10)
                        .map(|_| HashSet::<usize>::new())
                        .collect();

let arr: [Vec<u32>; 10] = [(); 10].map(|_| Vec::with_capacity(100));

*/

impl Sudoku {
    pub fn new() -> Self {
        // let b : HashSet<u8> = HashSet::from_iter(1..=9);
        let mut initial: Possible = Possible(set_bits(10));
        initial.set(0, false);

        let s = Sudoku {
            board: [0; MAX_SIZE as usize],
            possible: [initial; MAX_SIZE as usize],
        };
        s
    }

    pub fn clear(&mut self) {
        let mut initial = Possible(set_bits(10));
        initial.set(0, false);

        self.board = [0; MAX_SIZE as usize];
        self.possible = [initial; MAX_SIZE as usize];
    }

    /// Load puzzle from a string.
    /// Note, we load from (top,left), to (bottom,left) by columns.
    pub fn load_from_tld(&mut self, start_ch: char, blank: char, s: &str) {
        self.clear();
        let mut x: u8 = 0;
        let mut y: u8 = 0;

        for ch in s.chars() {
            if ch != blank {
                self.set(x, y, (ch as u8 - start_ch as u8) + 1);
            }
            y += 1;
            if y >= WIDTH {
                y = 0;
                x += 1;
            }
        }
    }

    /// Load puzzle from a string.
    /// This loads from (top,left) to (top,right), by rows.
    pub fn load_from_tlr(&mut self, start_ch: char, blank: char, s: &str) {
        self.clear();
        let mut i: u8 = 0;

        for ch in s.chars() {
            if ch != blank {
                self.set(xy(i).0, xy(i).1, (ch as u8 - start_ch as u8) + 1);
            }
            i += 1;
        }
    }

    pub fn save_to_tld(&self, mut start_ch: char, blank: char) -> String {
        let mut result = String::new();
        result.reserve(MAX_SIZE as usize);
        start_ch = (start_ch as u8 - 1) as char;
        let mut x: u8 = 0;
        let mut y: u8 = 0;

        for i in 0..MAX_SIZE {
            if self.board[pos(x, y) as usize] == 0 {
                result.push(blank);
            } else {
                result.push((start_ch as u8 + self.board[i as usize]) as char);
            }
            y += 1;
            if y >= WIDTH {
                y = 0;
                x += 1;
            }
        }
        result
    }

    pub fn save_to_tlr(&self, mut start_ch: char, blank: char) -> String {
        let mut result = String::new();
        result.reserve(MAX_SIZE as usize);
        start_ch = (start_ch as u8 - 1) as char;
        for i in 0..MAX_SIZE {
            if self.board[i as usize] == 0 {
                result.push(blank);
            } else {
                result.push((start_ch as u8 + self.board[i as usize]) as char);
            }
        }
        result
    }

    pub fn set(&mut self, x: u8, y: u8, value: u8) {
        self.board[pos(x, y) as usize] = value;
        // Ok, update the possible
        let mut g = for_row(y);
        // g.for_row(x, y);
        for g in g.0 {
            // remove value from these sets.
            self.possible[g as usize].set(value, false);
            // self.possible[g as usize].take(&value);
        }
        g = for_column(x);
        // g.for_column(x, y);
        for g in g.0 {
            // remove value from these sets.
            self.possible[g as usize].set(value, false);
            // self.possible[g as usize].take(&value);
        }
        g = for_cell(which_cell(x, y));
        // g.for_block(x, y);
        for g in g.0 {
            // remove value from these sets.
            self.possible[g as usize].set(value, false);
            // self.possible[g as usize].take(&value);
        }
        self.possible[pos(x, y) as usize].clear();
    }

    pub fn display(&self) {
        println!("╔═══╦═══╦═══╗");
        for y in 0..WIDTH {
            print!("║");
            for x in 0..WIDTH {
                let item = self.board[pos(x as u8, y as u8) as usize];
                if item == 0 {
                    print!(" ");
                } else if (item >= 1) && (item <= 9) {
                    print!("{}", item);
                }
                if x % 3 == 2 {
                    print!("║");
                }
            }
            println!("");
            if y % 3 == 2 {
                if y + 1 == WIDTH {
                    println!("╚═══╩═══╩═══╝");
                } else {
                    println!("╠═══╬═══╬═══╣");
                }
            }
        }
    }

    pub fn display_possible(&self) {
        for y in 0..WIDTH {
            for x in 0..WIDTH {
                // print!("p={:?}", self.possible[pos(x, y) as usize]);
                let mut possible = String::new();

                for p in self.possible[pos(x, y) as usize].iter() {
                    // print!("{},", p);
                    possible += format!("{},", p).as_str();
                }

                // for i in 0..SIZE {
                // let &pos = self.possible[pos(x, y) as usize];
                print!("({},{}):", x, y);
                // print!("{:20}", format!("{:?}", self.possible[pos(x, y) as usize]));
                print!("{:9}", possible);
                /*
                if pos == 0 {
                    print!(" ");
                } else {
                    print!("{}", pos);
                }
                */
                // }
                // print!(" ");
            }
            println!("");
        }
    }

    pub fn puzzle_complete(&self) -> bool {
        for i in 0..MAX_SIZE {
            if self.board[i as usize] == 0 {
                return false;
            }
        }
        true
    }

    fn calculate_possible(&mut self, total_solutions: &mut u16, solutions: &mut Vec<SudokuBoard>) -> bool {
        for idx in 0..MAX_SIZE {
            if self.board[idx as usize] == 0 {
                // Ok, there's a blank here

                let (x, y) = xy(idx);
                if DEBUG_OUTPUT {
                    println!("idx={} ({},{})", idx, x, y);
                    self.display();
                }

                'outer: for possible in 1..=9 {
                    let mut g = for_row(y);
                    for p in g.0 {
                        if self.board[p as usize] == possible {
                            continue 'outer;
                        }
                    }
                    g = for_column(x);
                    for p in g.0 {
                        if self.board[p as usize] == possible {
                            continue 'outer;
                        }
                    }
                    // check cell
                    let cell = which_cell(x, y);
                    g = for_cell(cell);
                    for p in g.0 {
                        if self.board[p as usize] == possible {
                            continue 'outer;
                        }
                    }

                    // Ok, it could go here!
                    if DEBUG_OUTPUT {
                        println!("({},{})={}", x, y, possible);
                    }

                    self.board[idx as usize] = possible;
                    if self.puzzle_complete() {
                        if *total_solutions < solutions.capacity() as u16 {
                            solutions.push(self.board);
                        }
                        *total_solutions += 1;
                        /*
                        println!("**SOLUTION**");
                        self.display();
                        println!("***");
                         */
                        break;
                    } else {
                        if self.calculate_possible(total_solutions, solutions) {
                            return true;
                        }
                    }
                }
                self.board[idx as usize] = 0;
                return false;
            }
        }

        false
    }

    pub fn bruteforce_solver(&self) -> u16 {
        let mut workset = Sudoku {
            board: self.board,
            possible: [Possible(0); MAX_SIZE as usize],
        };

        let mut total_solutions: u16 = 0;
        let mut solutions = Vec::new();
        solutions.reserve(1);
        workset.calculate_possible(&mut total_solutions, &mut solutions);

        // return number of solutions.
        if solutions.len() > 0 {
            println!("*** A solution:");
            workset.board = solutions[0];
            workset.display();
            println!("***");
        }
        total_solutions
    }

    pub fn make(&mut self) {
        let mut rng = ChaCha20Rng::from_entropy();

        self.fill_board(&mut rng);
    }

    fn fill_board(&mut self, rng: &mut ChaCha20Rng) -> bool {
        let backup = Sudoku {
            board: self.board,
            possible: self.possible,
        };

        for idx in 0..MAX_SIZE {
            if self.board[idx as usize] == 0 {
                let (x, y) = xy(idx);
                let mut available: [u8; WIDTH as usize] = [0; WIDTH as usize];
                let mut total_available: u8 = 0;

                for t in self.possible[idx as usize].iter() {
                    available[total_available as usize] = t;
                    total_available += 1;
                }

                if total_available == 0 {
                    // No possible moves remain.
                    /*
                    self.board = backup.board;
                    self.possible = backup.possible;
                     */
                    return false;
                }

                // Randomize the possible items.
                available[0..total_available as usize].shuffle(rng);
                for v_idx in 0..total_available {
                    let value = available[v_idx as usize];
                    self.set(x, y, value);
                    if self.fill_board(rng) {
                        return true;
                    }
                    // failure
                    self.board = backup.board;
                    self.possible = backup.possible;
                }

                // We've run out of possible.
                return false;
            }
        }

        // We've visited everything, and it isn't 0.
        return true;
    }

    pub fn make_(&mut self) {
        self.clear();

        let mut rng = ChaCha20Rng::from_entropy();

        let pick_one = |this: &Self, rng: &mut ChaCha20Rng, idx: u8| -> Option<u8> {
            let mut available: [u8; WIDTH as usize] = [0; WIDTH as usize];
            let mut total_available: u8 = 0;

            for t in this.possible[idx as usize].iter() {
                available[total_available as usize] = t;
                total_available += 1;
            }
            if total_available == 1 {
                return Some(available[0]);
            }
            if total_available == 0 {
                return None;
            }
            Some(available[rng.gen_range(0..total_available as usize)])
        };

        for i in 0..MAX_SIZE {
            let (x, y) = xy(i);
            if self.board[i as usize] == 0 {
                // Ok, we found a blank space.
                let value = pick_one(self, &mut rng, i);
                if value.is_some() {
                    let value = value.unwrap();
                    if DEBUG_OUTPUT {
                        println!("Set({},{})={}", x, y, value);
                    }
                    self.set(x, y, value);
                }
            }
        }
    }

    pub fn solve(&mut self, debug: bool) -> bool {
        // Pass 1: Look for singles in the possible sets.
        let mut found_something = false;

        for i in 0..MAX_SIZE {
            if self.possible[i as usize].count_set() == 1 {
                // Get the value
                let value = self.possible[i as usize].iter().next().unwrap();
                // Found one!
                if debug {
                    println!("Set1 {:?} to {}", xy(i), value);
                }
                self.set(xy(i).0, xy(i).1, value);
                found_something = true;
            }
        }

        let mut g = Group::new();
        let mut values = Possible(0); // HashSet<u8> = HashSet::new();

        let mut group_process = |this: &mut Self, grp: &Group| {
            // Collect all the possible values within the group.
            values.clear();
            for gidx in 0..WIDTH {
                // println!("possible: {:?}", this.possible[grp.items[gidx as usize] as usize]);
                for v in this.possible[grp.0[gidx as usize] as usize].iter() {
                    values.set(v, true);
                }
                // values.extend(this.possible[grp.0[gidx as usize] as usize]);
                // println!("now     : {:?}", this.possible[grp.items[gidx as usize] as usize]);
            }

            // println!("values {:?}", values);

            // Now, check for singles.
            for v in values.iter() {
                let mut count = 0;
                let mut pos = 0;
                for gidx in 0..WIDTH {
                    if this.possible[grp.0[gidx as usize] as usize].get(v) {
                        // if this.possible[grp.0[gidx as usize] as usize].contains(&v) {
                        count += 1;
                        pos = grp.0[gidx as usize];
                        if count > 1 {
                            break;
                        }
                    }
                }
                if count == 1 {
                    // don't need this, it was v!
                    // let value = this.possible[pos as usize].iter().next().cloned().unwrap();
                    if debug {
                        println!("Set2 {:?} to {}", xy(pos), v);
                    }
                    this.set(xy(pos).0, xy(pos).1, v);
                    found_something = true;
                }
            }
        };

        // Change to 0..WIDTH ...  Keep it simple.
        for i in 0..WIDTH {
            let mut g = for_column(i);
            // g.for_column(i, 1);
            group_process(self, &g);
            g = for_row(i);
            // g.for_row(1, i);
            group_process(self, &g);
            g = for_cell(i);
            // g.for_iter(i);
            group_process(self, &g);
        }

        if found_something {
            return found_something;
        }

        if debug {
            println!("Looking for pairs...");
        }
        // PAIR processing.
        for i in 0..WIDTH {
            g.for_iter(i);

            for gidx in 0..WIDTH - 1 {
                let gpos = g.0[gidx as usize];
                if self.possible[gpos as usize].count_set() == 2 {
                    // Found a pair
                    for fidx in gidx + 1..WIDTH {
                        let fpos = g.0[fidx as usize];
                        if self.possible[fpos as usize].count_set() == 2 {
                            // Ok, there's another pair
                            // if self.possible[gpos as usize].is_subset(&self.possible[fpos as usize])
                            if self.possible[gpos as usize] == self.possible[fpos as usize] {
                                // Ok, they have the same values!
                                // Ok, remove the items in the pair from the cell.
                                // Don't touch the gpos/fpos records.  Keep those!
                                let mut values: [u8; 2] = [0, 0];
                                let mut vpos = 0;
                                for z in self.possible[gpos as usize].iter() {
                                    values[vpos] = z;
                                    vpos += 1;
                                }

                                let mut pair_removed = false;

                                // Check to see if anything was removed.

                                for remove in 0..WIDTH {
                                    if (gidx == remove) || (fidx == remove) {
                                        continue;
                                    }
                                    // Ok, these aren't the ones to save, so:
                                    let rpos = g.0[remove as usize];
                                    if self.possible[rpos as usize].get(values[0]) {
                                        self.possible[rpos as usize].set(values[0], false);
                                        found_something = true;
                                        pair_removed = true;
                                    }

                                    if self.possible[rpos as usize].get(values[1]) {
                                        self.possible[rpos as usize].set(values[1], false);
                                        found_something = true;
                                        pair_removed = true;
                                    }
                                }

                                // Check the x's and y's to see if we can also process a row/column too.
                                if xy(gpos).0 == xy(fpos).0 {
                                    // Matching X - process column
                                    let column = xy(gpos).0;

                                    vpos = 0;
                                    for z in self.possible[gpos as usize].iter() {
                                        values[vpos] = z;
                                        vpos += 1;
                                    }
                                    for remove in 0..WIDTH {
                                        if (remove == xy(gpos).1) || (remove == xy(fpos).1) {
                                            continue;
                                        }

                                        if self.possible[pos(column, remove) as usize]
                                            .get(values[0])
                                        {
                                            self.possible[pos(column, remove) as usize]
                                                .set(values[0], false);
                                            found_something = true;
                                            pair_removed = true;
                                        }

                                        if self.possible[pos(column, remove) as usize]
                                            .get(values[1])
                                        {
                                            self.possible[pos(column, remove) as usize]
                                                .set(values[1], false);
                                            found_something = true;
                                            pair_removed = true;
                                        }
                                    }
                                }

                                if xy(gpos).1 == xy(fpos).1 {
                                    // Matching Y - process row
                                    let row = xy(gpos).1;

                                    vpos = 0;
                                    for z in self.possible[gpos as usize].iter() {
                                        values[vpos] = z;
                                        vpos += 1;
                                    }
                                    for remove in 0..WIDTH {
                                        if (remove == xy(gpos).0) || (remove == xy(fpos).0) {
                                            continue;
                                        }
                                        if self.possible[pos(remove, row) as usize].get(values[0]) {
                                            self.possible[pos(remove, row) as usize]
                                                .set(values[0], false);
                                            found_something = true;
                                            pair_removed = true;
                                        }

                                        if self.possible[pos(remove, row) as usize].get(values[1]) {
                                            self.possible[pos(remove, row) as usize]
                                                .set(values[1], false);
                                            found_something = true;
                                            pair_removed = true;
                                        }
                                    }
                                }

                                if pair_removed {
                                    if debug {
                                        println!(
                                            "Pair found! {} {}: {} {:?} and {} {:?} !",
                                            gidx,
                                            fidx,
                                            gpos,
                                            xy(gpos),
                                            fpos,
                                            xy(fpos)
                                        );
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        found_something
    }
}