sudoku-rust/sudoku/src/sudoku.rs

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

use strum::IntoEnumIterator;
use std::string::String;
extern crate rand_chacha;
use rand::seq::SliceRandom;
use rand_chacha::rand_core::SeedableRng;
use rand_chacha::ChaCha20Rng;

// For custom error
use std::error;
use std::fmt;

#[derive(Debug, Clone)]
struct GameLoadError {
    message: String,
}

impl fmt::Display for GameLoadError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Game load error: {}", self.message)
    }
}

impl error::Error for GameLoadError {}

// const DEBUG_OUTPUT: bool = false;

// Vec doesn't implement Copy ...
#[derive(Debug, Clone, Eq, PartialEq)]
pub struct AnyBoard {
    pub size: u8,
    pub width: u8,
    pub max_index: usize,
    pub board: Vec<u8>,
}

impl AnyBoard {
    pub fn new(board_size: u8) -> Self {
        if (board_size < 3) || (board_size > 5) {
            panic!("Board size must be 3-5.");
        }

        let n = board_size as usize;
        let s = AnyBoard {
            size: board_size,
            width: board_size * board_size,
            max_index: n * n * n * n,
            board: vec![0; n * n * n * n],
        };
        s
    }

    /// Clear out the board
    pub fn clear(&mut self) {
        self.board.fill(0);
    }

    pub fn copy(&mut self, copy_from: &Self) {
        debug_assert!(
            self.size == copy_from.size,
            "Can't copy size {} into size {}",
            copy_from.size,
            self.size
        );
        for i in 0..self.max_index {
            self.board[i] = copy_from.board[i];
        }
    }

    /// Calculate index position of (x,y)
    #[inline]
    pub fn pos(&self, x: u8, y: u8) -> usize {
        debug_assert!(
            x < self.width && y < self.width,
            "Expected ({}, {}) < {}",
            x,
            y,
            self.width
        );
        x as usize + y as usize * self.width as usize
    }

    /// Return (x,y) position for given index.
    #[inline]
    pub fn xy(&self, idx: usize) -> (u8, u8) {
        (
            (idx % self.width as usize) as u8,
            (idx / self.width as usize) as u8,
        )
    }

    /// Set a position in the board with a value
    pub fn set(&mut self, x: u8, y: u8, value: u8) {
        debug_assert!(
            x < self.width && y < self.width,
            "Expected ({}, {}) < {}",
            x,
            y,
            self.width
        );
        debug_assert!(
            value <= self.width,
            "Expected value for ({},{}) = {} < {}",
            x,
            y,
            value,
            self.width
        );
        let index = self.pos(x, y);
        assert!(index <= self.board.capacity());
        self.board[index] = value;
    }

    /// Get value at position (x,y)
    pub fn get(&self, x: u8, y: u8) -> u8 {
        debug_assert!(
            x < self.width && y < self.width,
            "Expected ({}, {}) < {}",
            x,
            y,
            self.width
        );
        let index = self.pos(x, y);
        assert!(index <= self.board.capacity());
        self.board[index]
    }

    /// Load from ksudoku file
    /// - uses load_from_tld
    pub fn load_ksudoku(&mut self, s: &str) -> Result<(), Box<dyn error::Error>> {
        self.load_from_tld('b', '_', s)
    }

    pub fn save_ksudoku(&self) -> String {
        self.save_to_tld('b', '_')
    }
    
    /// Load puzzle from string (top,left) going down.
    pub fn load_from_tld(
        &mut self,
        start_ch: char,
        blank: char,
        s: &str,
    ) -> Result<(), Box<dyn error::Error>> {
        self.clear();
        let mut x: u8 = 0;
        let mut y: u8 = 0;

        if s.len() != self.max_index {
            // self.size * self.size*self.size*self.size {
            return Err(Box::new(GameLoadError {
                message: format!(
                    "String ({}) exceeds expected length {}.",
                    s.len(),
                    self.width
                ),
            }));
        }

        for ch in s.chars() {
            if ch != blank {
                let value = (ch as u8 - start_ch as u8) + 1;
                if value == 0 || value > self.width {
                    return Err(Box::new(GameLoadError {
                        message: format!(
                            "String symbol ({}) represents value {}, expecting 1 to {}.",
                            ch, value, self.width
                        ),
                    }));
                }
                self.set(x, y, value);
            }
            y += 1;
            if y >= self.width {
                y = 0;
                x += 1;
            }
        }
        Ok(())
    }

    /// Save puzzle to a string (top,left) going down.
    pub fn save_to_tld(&self, start_ch: char, blank: char) -> String {
        let mut result = String::new();
        result.reserve(self.max_index);
        let start_ch = (start_ch as u8 - 1) as char;
        let mut x: u8 = 0;
        let mut y: u8 = 0;

        for _i in 0..self.max_index {
            let value = self.get(x, y);
            if value == 0 {
                result.push(blank);
            } else {
                result.push((start_ch as u8 + value) as char);
            }
            y += 1;
            if y >= self.width {
                y = 0;
                x += 1;
            }
        }
        result
    }

    /// Load puzzle from string (top,left) going right.
    pub fn load_from_tlr(
        &mut self,
        start_ch: char,
        blank: char,
        s: &str,
    ) -> Result<(), Box<dyn error::Error>> {
        self.clear();

        if s.len() != self.max_index {
            // self.size * self.size*self.size*self.size {
            return Err(Box::new(GameLoadError {
                message: format!(
                    "String exceeds ({}) expected length {}.",
                    s.len(),
                    self.width
                ),
            }));
        }

        let mut i: usize = 0;

        for ch in s.chars() {
            if ch != blank {
                let value = (ch as u8 - start_ch as u8) + 1;
                if value == 0 || value > self.width {
                    return Err(Box::new(GameLoadError {
                        message: format!(
                            "String symbol ({}) represents value {}, expecting 1 to {}.",
                            ch, value, self.width
                        ),
                    }));
                }
                self.board[i] = value;
                i += 1;
            }
        }
        Ok(())
    }

    /// Save puzzle to a string (top,left) going right.
    pub fn save_to_tlr(&self, start_ch: char, blank: char) -> String {
        let mut result = String::new();
        result.reserve(self.max_index);
        let start_ch = (start_ch as u8 - 1) as char;

        for i in 0..self.max_index {
            let value = self.board[i];
            if value == 0 {
                result.push(blank);
            } else {
                result.push((start_ch as u8 + value) as char);
            }
        }
        result
    }

    /// Display board using unicode box characters.
    pub fn display(&self) {
        let line = "═".repeat(self.size as usize);
        let alpha_display = self.width >= 10;
        // println!("╔{}╦{}╦{}╗", line, line, line);

        // Top
        for i in 0..self.size {
            if i == 0 {
                print!("╔{}", line);
            } else {
                print!("╦{}", line);
            }
        }
        println!("╗");

        for y in 0..self.width {
            print!("║");
            for x in 0..self.width {
                let value = self.get(x, y);
                if value == 0 {
                    print!(" ");
                } else {
                    if alpha_display {
                        print!("{}", (value - 1 + 'A' as u8) as char);
                    } else {
                        print!("{}", value);
                    }
                }
                if x % self.size == self.size - 1 {
                    print!("║");
                }
            }
            println!("");
            if y % self.size == self.size - 1 {
                if y + 1 == self.width {
                    // Bottom
                    for i in 0..self.size {
                        if i == 0 {
                            print!("╚{}", line);
                        } else {
                            print!("╩{}", line);
                        }
                    }
                    println!("╝");

                    // println("╚═══╩═══╩═══╝");
                } else {
                    // Middle
                    for i in 0..self.size {
                        if i == 0 {
                            print!("╠{}", line);
                        } else {
                            print!("╬{}", line);
                        }
                    }
                    println!("╣");
                    // println("╠═══╬═══╬═══╣");
                }
            }
        }
    }

    /// Output board as strings.
    /// - Uses 1-9 (for 9x9), and A-? for others.
    /// - Used by tests to confirm the board is what we think it should be.
    pub fn to_strings(&self) -> Vec<String> {
        let mut result = Vec::<String>::new();
        let alpha_display = self.width >= 10;

        for y in 0..self.width {
            let mut line = String::new();
            line.reserve(self.width as usize);
            for x in 0..self.width {
                let value = self.get(x, y);
                if value == 0 {
                    line.push(' ');
                } else {
                    if alpha_display {
                        line.push((value - 1 + 'A' as u8) as char);
                    } else {
                        line.push((value + '0' as u8) as char);
                    }
                }
            }
            result.push(line);
        }
        result
    }

    /// Is the puzzle completed?
    /// Have all of the locations been filled with a value?
    /// - This does not validate that it is a correct puzzle.
    ///   It doesn't check for duplicate digits (for example).
    pub fn complete(&self) -> bool {
        for i in 0..self.max_index {
            if self.board[i] == 0 {
                return false;
            }
        }
        true
    }

    /// Solve by brute force
    /// - Returns up to max # of solutions.
    /// - Returns total solutions found, and vector of boards (up to max).
    /// - Uses brute_force (recursive function) to solve.
    pub fn brute_force_solver(&self, max: u16) -> (u16, Vec<AnyBoard>) {
        let mut workset = self.clone();
        let mut total_solutions: u16 = 0;
        let mut solutions: Vec<AnyBoard> = Vec::new();
        let groups = AnyGroup::new(workset.size);
        solutions.reserve(max as usize);

        workset.brute_force(&mut total_solutions, &mut solutions, &groups);
        (total_solutions, solutions)
    }

    /// Recursive brute force solver.
    fn brute_force(
        &mut self,
        total_solutions: &mut u16,
        solutions: &mut Vec<AnyBoard>,
        groups: &AnyGroup,
    ) -> bool {
        for idx in 0..self.max_index {
            if self.board[idx] == 0 {
                // Blank found
                let (x, y) = self.xy(idx);

                // println!("Blank ({},{})", x, y);

                'outer: for value in 1..=self.width {
                    // Check if it fits in the puzzle via group.
                    for clear in groups.row(y) {
                        if self.board[*clear] == value {
                            continue 'outer;
                        }
                    }
                    for clear in groups.column(x) {
                        if self.board[*clear] == value {
                            continue 'outer;
                        }
                    }
                    for clear in groups.cell(groups.which_cell(x, y)) {
                        if self.board[*clear] == value {
                            continue 'outer;
                        }
                    }

                    // Ok, this is possible move.
                    self.board[idx] = value;
                    // println!("Try ({},{}) = {}", x, y, value);
                    // self.display();

                    if self.complete() {
                        if *total_solutions < solutions.capacity() as u16 {
                            solutions.push(self.clone());
                        }
                        *total_solutions += 1;
                        break;
                    } else {
                        if self.brute_force(total_solutions, solutions, groups) {
                            return true;
                        }
                    }
                }
                // We failed to place a value -- return failure.
                // println!("rewind");
                self.board[idx] = 0;
                return false;
            }
        }
        false
    }
}

// Need to use u32, so 5*5=25, 25 bits can be accessed.
// u16 is fine for 3*3=9.

#[derive(Debug, Clone)]
pub struct AnyPossible {
    pub size: u8,
    pub width: u8,
    pub max_index: usize,
    pub possible: Vec<GenBits<u32>>,
}

impl AnyPossible {
    pub fn new(board_size: u8) -> Self {
        let mut initial = GenBits::<u32>(0);
        let width = board_size * board_size;
        initial.set_bits(0..width);

        Self {
            size: board_size,
            width: width,
            max_index: width as usize * width as usize,
            possible: vec![initial; width as usize * width as usize],
        }
    }

    pub fn clear(&mut self) {
        let mut initial = GenBits::<u32>(0);
        // let width = self.size * self.size;
        initial.set_bits(0..self.width);

        self.possible.fill(initial);

        // self.possible = vec![initial; self.max_index];
        // width as usize * width as usize];
    }

    pub fn copy(&mut self, copy_from: &Self) {
        debug_assert!(
            self.size == copy_from.size,
            "Can't copy size {} into size {}",
            copy_from.size,
            self.size
        );
        for i in 0..self.max_index {
            self.possible[i] = copy_from.possible[i];
        }
    }

    // NOTE: values range from 1..width. Bits range from 0..width-1

    #[inline]
    pub fn set(&mut self, index: usize, value: usize, state: bool) {
        debug_assert!(
            index < self.max_index,
            "Index {} >= {}",
            index,
            self.max_index
        );
        self.possible[index].set(value - 1, state);
    }

    #[inline]
    pub fn get(&self, index: usize, value: usize) -> bool {
        debug_assert!(
            index < self.max_index,
            "Index {} >= {}",
            index,
            self.max_index
        );
        self.possible[index].get(value - 1)
    }

    #[inline]
    pub fn pos(&self, x: u8, y: u8) -> usize {
        debug_assert!(
            x < self.width && y < self.width,
            "Expected ({},{}) < {}",
            x,
            y,
            self.width
        );
        x as usize + y as usize * self.width as usize
    }
    /// Return (x,y) position for given index.
    #[inline]
    pub fn xy(&self, idx: usize) -> (u8, u8) {
        debug_assert!(idx < self.max_index, "Index {} >= {}", idx, self.max_index);
        (
            (idx % self.width as usize) as u8,
            (idx / self.width as usize) as u8,
        )
    }

    /// Format all possible, finding max length.
    /// - Return vec<string> of each item formatted.
    /// - Return max length.
    pub fn pos_max(&self) -> (Vec<String>, usize) {
        let mut pos = Vec::<String>::new();
        pos.reserve(self.max_index);
        let mut max: usize = 0;

        for idx in 0..self.max_index {
            let s = self.possible[idx].display();
            if max < s.len() {
                max = s.len();
            }
            pos.push(s);
        }
        (pos, max)
    }

    /// Display Possible
    /// - Collect all of the possibles, with max length.
    /// - Display formatted (using max length).
    pub fn display(&self) {
        let pos_info = self.pos_max();

        for y in 0..self.width {
            for x in 0..self.width {
                let idx = self.pos(x, y);

                print!("({},{}):{:3$} ", x + 1, y + 1, pos_info.0[idx], pos_info.1);
            }
            println!("");
        }
    }
}

/*
An idea I have for AnySolver is to store the AnyPossible as
sections.  row/column/cell.
I think this would better allow me to judge how hard the puzzle
is.  If it can be solved by looking at just one section --
that would be one level.  If it takes 2, another level. All 3,
yet another.  I think that's how I mentally judge the puzzles.

"Not all hard puzzles are hard."

 */

#[derive(Debug, Clone)]
pub struct AnySolver {
    pub board: AnyBoard,
    pub possible: AnyPossible,
    pub group: AnyGroup,
}

impl AnySolver {
    /// Construct new solver from given board size. (3,4,5)
    pub fn new(board_size: u8) -> Self {
        let mut s = Self {
            board: AnyBoard::new(board_size),
            possible: AnyPossible::new(board_size),
            group: AnyGroup::new(board_size),
        };
        s.reset_possible();
        s
    }

    /// Construct new solver from given board.
    pub fn new_from(initial_board: &AnyBoard) -> Self {
        let mut s = AnySolver {
            board: initial_board.clone(),
            possible: AnyPossible::new(initial_board.size),
            group: AnyGroup::new(initial_board.size),
        };
        s.reset_possible();
        s
    }

    /// Clear out board and possible.
    /// - group is ok, unless they change the board size.
    pub fn clear(&mut self) {
        let board_size: u8 = self.board.size;
        self.board = AnyBoard::new(board_size);
        self.possible = AnyPossible::new(board_size);
        self.reset_possible();
    }

    /// Process a move
    /// - Remove value from rows, columns, and cells.
    /// - Clear possibles from (x,y) position, it's filled.
    pub fn process_move(&mut self, x: u8, y: u8, value: u8) {
        debug_assert!(
            x <= self.board.width && y <= self.board.width,
            "Expected ({}, {}) <= {}",
            x,
            y,
            self.board.width
        );
        debug_assert!(
            value <= self.board.width,
            "Expected value {} < {}",
            value,
            self.board.width
        );

        let mut g = self.group.row(y);
        let val: usize = value as usize;
        for g in g {
            self.possible.set(*g, val, false);
        }
        g = self.group.column(x);
        for g in g {
            self.possible.set(*g, val, false);
        }
        g = self.group.cell(self.group.which_cell(x, y));
        for g in g {
            self.possible.set(*g, val, false);
        }
        let idx = self.possible.pos(x, y);
        self.possible.possible[idx] = GenBits::<u32>(0); // .clear();
        self.board.board[idx] = value;
    }

    /// Validate the board
    /// Reuse reset_possible code, verify the values are possible.
    /// - This does not check if the board is completed.
    /// - It does check that blanks have possible values.
    pub fn validate_board(&mut self) -> bool {
        let mut has_blanks = false;

        self.possible.clear();
        for y in 0..self.board.width {
            for x in 0..self.board.width {
                let value = self.board.get(x, y);

                if value != 0 {
                    if !self.possible.get(self.possible.pos(x, y), value as usize) {
                        // I was going to reset_possible, but the board is broken!
                        // Leave in a broken state.

                        // log (maybe)
                        // println!("Invalid at ({},{}) can't place {}.", x + 1, y + 1, value);
                        // self.board.display();
                        return false;
                    }
                    self.process_move(x, y, value);
                } else {
                    has_blanks = true;
                }
            }
        }
        // Ok, the pieces given fit correctly with the sudoku constraints.

        if has_blanks {
            // Verify that the remaining value == 0 positions have possibles.
            // - If they are blank, then it isn't a valid puzzle!
            for y in 0..self.board.width {
                for x in 0..self.board.width {
                    let value = self.board.get(x, y);
                    if value == 0 {
                        let count = self.possible.possible[self.possible.pos(x, y)].count_set();
                        if count == 0 {
                            // log (maybe)
                            // println!("Invalid ({},{}) = no values possible.", x + 1, y + 1);
                            // self.board.display();
                            return false;
                        }
                    }
                }
            }
        }
        true
    }

    /// Reset the possible
    /// - For when a new puzzle has been loaded.
    /// - When something has changed, and the possibles are out of sync.
    pub fn reset_possible(&mut self) {
        self.possible.clear();
        for y in 0..self.board.width {
            for x in 0..self.board.width {
                let value = self.board.get(x, y);
                if value != 0 {
                    self.process_move(x, y, value);
                }
            }
        }
    }

    /// set (x,y) to value.
    /// - This updates the board.
    /// - This updates all the possibles (row,column,cell).
    /// - Clears the possible for (x,y) [See process_move].
    pub fn set(&mut self, x: u8, y: u8, value: u8) {
        debug_assert!(
            x < self.board.width && y < self.board.width,
            "Expected ({}, {}) < {}",
            x,
            y,
            self.board.width
        );
        debug_assert!(
            value < self.board.width + 1,
            "Expected value {} < {}",
            value,
            self.board.width + 1
        );

        self.board.set(x, y, value);
        if value != 0 {
            self.process_move(x, y, value);
        }
    }

    /// Make completed board.
    /// - uses fill_board (recursive)
    pub fn make(&mut self) {
        let mut rng = ChaCha20Rng::from_entropy();
        self.reset_possible();
        self.fill_board(&mut rng);
    }

    /// Recursively completely fill the board.
    /// This takes - quite a bit of time - for a 25x25 board.
    fn fill_board(&mut self, rng: &mut ChaCha20Rng) -> bool {
        let backup = self.clone();
        let max_index = self.board.max_index;
        let width = self.board.width;

        for idx in 0..max_index {
            if self.board.board[idx] == 0 {
                let (x, y) = self.board.xy(idx);
                let mut available: Vec<u8> = Vec::new();
                available.reserve(width as usize);

                for t in self.possible.possible[idx].iter() {
                    available.push(t + 1);
                }
                if available.len() == 0 {
                    return false;
                }

                // print!("{:?}", available);
                // Randomize the possible items.
                available.shuffle(rng);
                // available.as_mut_slice().shuffle(rng);

                // print!("{:?}", available);
                for value in available.into_iter() {
                    assert!(value != 0);

                    self.set(x, y, value);
                    // self.board.display();
                    // self.possible.display();

                    // I can't validate board, it might be invalid!
                    // Really!
                    /*
                    if ! self.validate_board() {
                        panic!("Whaaaat?!");
                    }
                    */

                    if self.fill_board(rng) {
                        return true;
                    }
                    // Failure
                    self.board.copy(&backup.board);
                    self.possible.copy(&backup.possible);
                }

                // We've run out of possible.
                return false;
            }
        }
        // We've visited everything, and it isn't 0.
        true
    }

    fn logic_pass1(&mut self) -> bool {
        // Pass 1: Look for singles in the possible sets.
        let mut pass1 = false;

        // Repeat pass 1 until all have been found.
        let mut pass1_again = true;

        while pass1_again {
            // Pass 1 - look for singles.
            pass1_again = false;
            let mut found_something = false;

            for i in 0..self.possible.max_index {
                if self.board.board[i] != 0 {
                    // Skip, if position already filled.
                    continue;
                }

                if self.possible.possible[i].count_set() == 1 {
                    // Get value
                    let value = self.possible.possible[i].iter().next().unwrap() + 1;
                    let pos = self.board.xy(i);
                    // println!("SET {}({},{})={}", i, pos.0 + 1, pos.1 + 1, value);
                    self.set(pos.0, pos.1, value);
                    found_something = true;
                }
            }

            if found_something {
                // We found something on this pass, so:
                // - Try it again.
                // - Record that we did something.
                pass1 = true;
                pass1_again = true;
            }
        }
        pass1
    }

    fn logic_pass2(&mut self) -> bool {
        let mut found_something = false;

        let mut pass2 = false;
        let mut pass2_again = true;

        let width = self.group.width;
        let grp = self.group.clone();

        while pass2_again {
            pass2_again = false;

            // let mut values = Bits(0); // HashSet<u8> = HashSet::new();
            let mut values = GenBits::<u32>(0);

            let mut group_process = |this: &mut Self, grp: &[usize]| {
                // 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.possible[grp[gidx as usize]].iter() {
                        values.set(v as usize, 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() {
                    // println!("Check Value: {}", v);

                    let mut count = 0;
                    let mut pos = 0;

                    for gidx in 0..width {
                        if this.possible.possible[grp[gidx as usize]].get(v as usize) {
                            // if this.possible[grp.0[gidx as usize] as usize].contains(&v) {
                            count += 1;
                            pos = grp[gidx as usize];
                            if count > 1 {
                                break;
                            } else {
                                // print!(" IDX {} POS {} ", gidx, pos);
                            }
                        }
                    }
                    if count == 1 {
                        // don't need this, it was v!
                        // let value = this.possible[pos as usize].iter().next().cloned().unwrap();
                        let xy = this.board.xy(pos);
                        // this.possible.display();
                        // this.board.display();
                        this.set(xy.0, xy.1, v + 1);
                        // println!("SET {} ({},{}) = {}", pos, xy.0 + 1, xy.1 + 1, v+1);

                        found_something = true;
                    }
                }
            };

            for gr in Groups::iter() {
                for i in 0..width {
                let g = grp.group(gr, i);
                    group_process(self, g);
                }
            }
            /*
            // Change to 0..WIDTH ...  Keep it simple.
            for i in 0..width {
                // println!("Column {i}:");
                let mut g = grp.column(i);
                group_process(self, g);
                // println!("Row {i}:");
                g = grp.row(i);
                group_process(self, g);
                // println!("Cell {i}:");
                g = grp.cell(i);
                group_process(self, g);
            }
            */

            if found_something == true {
                // Ok, pass 2 found something.
                pass2 = true;
                found_something = false;
                pass2_again = true;
                // continue;
            }
        }
        pass2
    }

    /// Solve by logic alone.
    /// - Returns true if solved.
    /// - It might not be solved (if guessing is required).
    pub fn solve_logic(&mut self) -> bool {
        // self.reset_possible(); // destroys anything pass3 accomplishes ...

        // self.board.display();
        // self.possible.display();

        let mut found_more = true;

        while found_more {
            found_more = false;

            let mut result1 = true;
            // Pass 1: Look for singles in the possible sets.
            while result1 {
                result1 = self.logic_pass1();
                if result1 {
                    println!("Pass1");
                };
            }

            let mut result2 = true;
            while result2 {
                result2 = self.logic_pass2();
                if result2 {
                    println!("Pass2");
                    found_more = true;
                };
            }

            /*
            // Pass 2: Is the same as Pass 1!
            // We just look in groups, instead of all the indexes.

            let mut found_something = false;
            let mut pass1 = false;

            // Repeat pass 1 until all have been found.
            let mut pass1_again = true;

            let width = self.group.width;
            let grp = self.group.clone();
            let mut pass2 = false;

            while pass1_again {
                // Pass 1 - look for singles.

                for i in 0..self.possible.max_index {
                    if self.board.board[i] != 0 {
                        // Skip, if position already filled.
                        continue;
                    }

                    if self.possible.possible[i].count_set() == 1 {
                        // Get value
                        let value = self.possible.possible[i].iter().next().unwrap() + 1;
                        let pos = self.board.xy(i);
                        // println!("SET {}({},{})={}", i, pos.0 + 1, pos.1 + 1, value);
                        self.set(pos.0, pos.1, value);
                        found_something = true;
                    }
                }

                if found_something {
                    // We found something this pass.
                    // - set pass1 to true (pass 1 found something)
                    // - reset found_something so we can try again.
                    pass1 = true;
                    found_something = false;
                    continue;
                } else {
                    // Nothing found with this run of pass 1.

                    // Pass 2 - Look for singles within the groups.

                    // Are we done?
                    /*
                    if self.board.complete() {
                        return false;
                    }
                    // We're getting stuck in pass 2 ...
                    // not anymore.  ;)
                    println!("Pass 2:");
                    self.board.display();

                    */

                    found_something = false;

                    // let mut values = Bits(0); // HashSet<u8> = HashSet::new();
                    let mut values = GenBits::<u32>(0);

                    let mut group_process = |this: &mut Self, grp: &[usize]| {
                        // 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.possible[grp[gidx as usize]].iter() {
                                values.set(v as usize, 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() {
                            // println!("Check Value: {}", v);

                            let mut count = 0;
                            let mut pos = 0;

                            for gidx in 0..width {
                                if this.possible.possible[grp[gidx as usize]].get(v as usize) {
                                    // if this.possible[grp.0[gidx as usize] as usize].contains(&v) {
                                    count += 1;
                                    pos = grp[gidx as usize];
                                    if count > 1 {
                                        break;
                                    } else {
                                        // print!(" IDX {} POS {} ", gidx, pos);
                                    }
                                }
                            }
                            if count == 1 {
                                // don't need this, it was v!
                                // let value = this.possible[pos as usize].iter().next().cloned().unwrap();
                                let xy = this.board.xy(pos);
                                // this.possible.display();
                                // this.board.display();
                                this.set(xy.0, xy.1, v + 1);
                                // println!("SET {} ({},{}) = {}", pos, xy.0 + 1, xy.1 + 1, v+1);

                                found_something = true;
                            }
                        }
                    };

                    // Change to 0..WIDTH ...  Keep it simple.
                    for i in 0..width {
                        // println!("Column {i}:");
                        let mut g = grp.column(i);
                        group_process(self, g);
                        // println!("Row {i}:");
                        g = grp.row(i);
                        group_process(self, g);
                        // println!("Cell {i}:");
                        g = grp.cell(i);
                        group_process(self, g);
                    }

                    if found_something == true {
                        pass2 = true;
                        // Ok, pass 2 found something.
                        found_something = false;
                        continue;
                    }

                    //
                    // - If pass1 set, reset the found_something (because it
                    //   did find something)
                    // - Clear the pass1_again flag, we're done with pass 1.
                    if pass1 {
                        pass1_again = false;
                        found_something = true;
                    } else {
                        // Ok, we didn't find anything.
                        // Break out of loop, get unstuck.
                        break;
                    }
                }
            }

            // Pass 3:
            // - Find pairs & remove those numbers from corresponding group.

            let grp = self.group.clone();

            println!("Pass 3:");
            self.board.display();
            self.possible.display();

            assert_eq!(self.board.width, self.possible.width);

            // Pair processing.
            for i in 0..width {
                let mut g = grp.cell(i);
                println!("Cell {}: {:?}", i, g);

                for gidx in 0..WIDTH - 1 {
                    let gpos = g[gidx as usize];
                    if self.possible.possible[gpos].count_set() == 2 {
                        // Found a pair

                        for fidx in gidx + 1..width {
                            let fpos = g[fidx as usize];
                            if self.possible.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.possible[gpos] == self.possible.possible[fpos] {
                                    // 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!

                                    // This looks .. WRONG!  only z+1 when using set(value)!

                                    let mut values: [u8; 2] = [0, 0];
                                    let mut vpos = 0;
                                    for z in self.possible.possible[gpos].iter() {
                                        values[vpos] = z;
                                        vpos += 1;
                                    }

                                    // Ok, other then being off by 1 (because x,y starts at 0 not 1),
                                    // This is, at least, displaying the information properly.

                                    self.possible.display();
                                    println!(
                                        "Pairs {gpos}({},{}) and {fpos}({},{}) {:?}",
                                        self.possible.xy(gpos).0 + 1,
                                        self.possible.xy(gpos).1 + 1,
                                        self.possible.xy(fpos).0 + 1,
                                        self.possible.xy(fpos).1 + 1,
                                        values
                                    );

                                    let mut pair_removed = false;

                                    // Check to see if anything was removed.

                                    for remove in 0..width {
                                        if (gidx == remove) || (fidx == remove) {
                                            // Skip the found pair indexes.  Don't remove those!
                                            continue;
                                        }

                                        // Ok, these aren't the ones to save, so:
                                        let rpos = g[remove as usize];
                                        if self.possible.possible[rpos].get(values[0] as usize) {
                                            self.possible.possible[rpos].set(values[0] as usize, false);
                                            found_something = true;
                                            pair_removed = true;
                                            println!("Removed {} from {}({},{})", values[0], rpos, self.possible.xy(rpos).0, self.possible.xy(rpos).1);
                                        }

                                        if self.possible.possible[rpos].get(values[1] as usize) {
                                            self.possible.possible[rpos].set(values[1] as usize, false);
                                            found_something = true;
                                            pair_removed = true;
                                            println!("Removed {} from {}({},{})", values[1], rpos, self.possible.xy(rpos).0, self.possible.xy(rpos).1);
                                        }
                                    }

                                    if pair_removed {
                                        println!("pair removed...");
                                        println!(
                                            "--> Pairs {gpos}({},{}) and {fpos}({},{}) {:?}",
                                            self.possible.xy(gpos).0 + 1,
                                            self.possible.xy(gpos).1 + 1,
                                            self.possible.xy(fpos).0 + 1,
                                            self.possible.xy(fpos).1 + 1,
                                            values
                                        );
                                    }

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

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

                                            let pos = self.possible.pos(column, remove);

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

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

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

                                        vpos = 0;
                                        for z in self.possible.possible[gpos].iter() {
                                            values[vpos] = z + 1;
                                            vpos += 1;
                                        }
                                        for remove in 0..width {
                                            if (remove == self.possible.xy(gpos).0)
                                                || (remove == self.possible.xy(fpos).0)
                                            {
                                                continue;
                                            }
                                            let pos = self.possible.pos(remove, row);

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

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

                                    if pair_removed {
                                        if true {
                                            println!(
                                                "Pair found! {} {}: {} {:?} and {} {:?} !",
                                                gidx,
                                                fidx,
                                                gpos,
                                                self.board.xy(gpos),
                                                fpos,
                                                self.board.xy(fpos)
                                            );
                                            self.possible.display();
                                            // panic!("... We're lost ...");
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            println!("Pass 3 - Ending...");
            found_something
            */
        }
        self.board.complete()

    }
}

#[cfg(test)]

mod tests {
    use crate::sudoku::*;

    #[test]
    fn display_board() {
        let mut board = AnyBoard::new(3);
        let result = board.load_from_tld(
            'b',
            '_',
            "__c_____e_h__cb___bd___ei_ch_jb__d___________i_eh__b__dg___ij_f_i__jg_____b_____g",
        );
        assert!(result.is_ok());
        let strings = board.to_strings();
        assert_eq!(
            strings,
            vec![
                "  17 83  ",
                " 73   68 ",
                "2  9 4  1",
                "   1 7   ",
                " 2     9 ",
                " 14   86 ",
                "  83 19  ",
                "         ",
                "4 2   5 6"
            ]
        );

        // board.display();
        let mut solver = AnySolver::new_from(&board);
        assert!(solver.validate_board());

        solver.reset_possible();

        if solver.solve_logic() {
            solver.board.display();
        }

        assert!(solver.validate_board());
        assert!(solver.board.complete());

        board = AnyBoard::new(4);
        let result = board.load_from_tld('b', '_', "_bo_j_m_f__dp__ge_h_pcfdo___q__n___qio______df___f__l___hpnm_i___obig_p_qhl__k_m_dq_cn______o_g_p_____bi_kc__jn______fo____gi______eb____jd______jk__ml_bn_____i_m_b______oq_nj_d_n__jck_m_fgbq___i_medp___n__b___dg______qjk___j__p___fgohl_d_qo__mq__g_d_p_le_");
        assert!(result.is_ok());
        let strings = board.to_strings();
        assert_eq!(
            strings,
            vec![
                " D    O    C  IN",
                "A  ENC   IL     ",
                "NG  AP   J MHC  ",
                "  P H   D A  FOL",
                "IOHKFB  A   L  P",
                " BN  M E L ID   ",
                "LE  O AN K BC   ",
                " C    H    JO EF",
                "EN GP    A    F ",
                "   OG J IM L  NC",
                "   MK B C N  PG ",
                "C  L   F  PEMIKO",
                "OPC  N H   F J  ",
                "  EHJ I   MA  CK",
                "     FM   IPA  D",
                "FM  L    H    P "
            ]
        );
        // board.display();

        let mut solver = AnySolver::new_from(&board);
        assert!(solver.validate_board());
        solver.board.display();

        if solver.solve_logic() {
            solver.board.display();
        }

        assert!(solver.validate_board());
        solver.board.display();
        assert!(solver.board.complete());

        let mut board: AnyBoard = AnyBoard::new(5);
        let result = board.load_from_tld('b', '_', "_m_kzg____h_s_n____ftd_u_u_dh_____f_b_t_w_____yg_c_rl_o_tdhy__m__uvig_w_sk_eg___p_q_jikouys_r_d___mlq_t_sb_emcwg_dlzyo_kp_i_ng__ir_b_fp_vhz_ce_y_jm__w__m__o_k_xul_qbt_d_s__e____otv_dhegn___mfkpz_blr____s_dv_n_mjx_ckg_w_bo_p___kqyelwjcz_____nxumoisdh_z__fp_vbi_______dkx_eg__r_y_mlwf_u__q_i__o_chdv_j_i_he_r_____________p_zl_k_d_vbjh_y__e_p__s_tguc_q_s__qj_kpn_______ufw_hx__i_hvntirfxw_____lbckympjg___u_kz_m_bfn_yvx_h_ir_o____rgm_otlnx___ipfes_kwc____p__c_v_ugh_krj_m_w__x__x__ci_j_qk_mpo_dr_u_zb__ht_i_qe_wjvcy_bhkzx_ng_u_syv___u_c_hsfrlqo_t_e___pj_cn_h_slzr__j__mqgp_y_vd_m_bs_____t_o_n_h_____ez_f_e_ufd____p_g_z____cqr_x_");
        assert!(result.is_ok());
        // board.display();
        let strings: Vec<String> = board.to_strings();
        assert_eq!(
            strings,
            vec![
                " T DPF    Y H R    WSX L ",
                "L QF     J X C G     UB D",
                " CK S LNRP  G  UTQO H MA ",
                "JG   H S XELDUPM F B   RT",
                "Y N RQ UCDOK AISJL HP G E",
                "F  OA N UK VQI HY B DT  C",
                "  S  A C VUE GJQ N I  R  ",
                "  CPD JGMIA   OELSU VBK  ",
                "  G LE D BHT XMW K PI Y  ",
                " EXIBOWFLY     VAMTJUGQS ",
                "G  HV TMI       EWF BR  O",
                " A JFUK W  P D  M GLXE N ",
                "R LN G             O QI F",
                " S TCYP B  H O  X JNAK M ",
                "M  XK ALJ       UHQ GP  Y",
                " VTRYBSEFM     KWOICJNLG ",
                "  U XD J WCN RTA E QY P  ",
                "  HQN COVTJ   EBGDL WSF  ",
                "  F  X Y LWB SVJ R T  O  ",
                "E  CJ R AN GOF XH V MD  B",
                "S V OI ANHDC TGLQJ YF X P",
                "CX   L K RFUYBWO V A   DQ",
                " FR H DQOC  K  INBW T UY ",
                "T JL     G I P F     OC W",
                " B KMV    Q J H    GRI E "
            ]
        );
        let mut solver = AnySolver::new_from(&board);
        assert!(solver.validate_board());
    }

    #[test]
    fn solve_board() {
        let mut board = AnyBoard::new(3);
        let result = board.load_from_tld(
            'b',
            '_',
            "__c_____e_h__cb___bd___ei_ch_jb__d___________i_eh__b__dg___ij_f_i__jg_____b_____g",
        );
        assert!(result.is_ok());
        assert_eq!(3, board.size);
        assert_eq!(9, board.width);
        assert_eq!(81, board.max_index);

        // board.display();
        let strings: Vec<String> = board.to_strings();
        assert_eq!(
            strings,
            vec![
                "  17 83  ",
                " 73   68 ",
                "2  9 4  1",
                "   1 7   ",
                " 2     9 ",
                " 14   86 ",
                "  83 19  ",
                "         ",
                "4 2   5 6"
            ]
        );

        let mut solver = AnySolver::new_from(&board);
        assert!(solver.validate_board());
        let solutions = solver.board.brute_force_solver(2);
        assert!(solutions.0 == 1, "Expected 1 solution, got {}", solutions.0);
        let strings: Vec<String> = solutions.1[0].to_strings();
        assert_eq!(
            strings,
            vec![
                "541768329",
                "973512684",
                "286934751",
                "869157243",
                "325486197",
                "714293865",
                "658341972",
                "197625438",
                "432879516",
            ]
        );

        // 4x4 board takes 40 minutes

        if false {
            board = AnyBoard::new(4);
            let result = board.load_from_tld('b', '_', "_bo_j_m_f__dp__ge_h_pcfdo___q__n___qio______df___f__l___hpnm_i___obig_p_qhl__k_m_dq_cn______o_g_p_____bi_kc__jn______fo____gi______eb____jd______jk__ml_bn_____i_m_b______oq_nj_d_n__jck_m_fgbq___i_medp___n__b___dg______qjk___j__p___fgohl_d_qo__mq__g_d_p_le_");
            assert!(result.is_ok());
            board.display();

            let mut solver = AnySolver::new_from(&board);
            assert!(solver.validate_board());
            let solutions = solver.board.brute_force_solver(2);
            assert!(solutions.0 == 1);
        }
    }

    #[test]
    fn make_board() {
        // Making a 4x4 board varies (0.3-60 seconds).
        // Maybe we don't want to do this in a test, because of the randomness involved.

        let mut solver = AnySolver::new(3);
        solver.make();
        solver.board.display();
        assert!(solver.validate_board());
    }

    #[test]
    fn validated_board() {
        // Create an invalid board. Position (5,9) can't possibly hold any value.

        let mut board = AnyBoard::new(3);
        board.set(4, 0, 1);
        board.set(4, 1, 2);
        board.set(4, 2, 3);
        board.set(4, 3, 4);
        board.set(4, 4, 5);
        board.set(4, 5, 6);
        board.set(0, 8, 7);
        board.set(1, 8, 8);
        board.set(2, 8, 9);
        // board.display();

        let mut solver = AnySolver::new_from(&board);
        assert!(!solver.validate_board());

        // Invalid board: Has two 1's in same column & cell.
        let mut board = AnyBoard::new(3);
        board.set(4, 0, 1);
        board.set(4, 1, 1);
        // board.display();

        let mut solver = AnySolver::new_from(&board);
        assert!(!solver.validate_board());

        // Invalid board: Has two 1's in same row & cell.
        let mut board = AnyBoard::new(3);
        board.set(4, 0, 1);
        board.set(5, 0, 1);
        // board.display();

        // Invalid board: Has two 1's in same column.
        let mut board = AnyBoard::new(3);
        board.set(4, 0, 1);
        board.set(4, 4, 1);
        // board.display();

        let mut solver = AnySolver::new_from(&board);
        assert!(!solver.validate_board());

        // Invalid board: Has two 1's in same row.
        let mut board = AnyBoard::new(3);
        board.set(4, 0, 1);
        board.set(7, 0, 1);
        // board.display();
        let mut solver = AnySolver::new_from(&board);
        assert!(!solver.validate_board());

        // Invalid board: Has two 1's in same cell.
        let mut board = AnyBoard::new(3);
        board.set(4, 0, 1);
        board.set(5, 1, 1);
        // board.display();

        let mut solver = AnySolver::new_from(&board);
        assert!(!solver.validate_board());
    }
}

/* 
    /// Puzzle generation
    /// - Removes a number, tests to see if the puzzle can still be solved by logic.
    /// - Returns true when still a valid, solvable puzzle.
    /// - Otherwise, restores number and returns false.
    pub fn remove(&mut self) -> bool {
        // Find a number, remove it. Save position.
        let mut rng = ChaCha20Rng::from_entropy();
        let puzrange = Uniform::new(0, WIDTH);
        let mut x = 0;
        let mut y = 0;
        let mut value: u8 = 0;

        while value == 0 {
            x = puzrange.sample(&mut rng);
            y = puzrange.sample(&mut rng);
            value = self.get(x, y);
        }

        self.set(x, y, 0);

        // Clone, and solve by logic.
        let mut puzcopy = self.clone();

        puzcopy.reset_possible();
        /*
        puzcopy.display();
        puzcopy.display_possible();
         */
        // If solvable, return true.
        while puzcopy.solve(false) {}

        /*
        puzcopy.display();
        puzcopy.display_possible();
        */

        if puzcopy.puzzle_complete() {
            return true;
        }

        // If not solvable, restore number, return false.
        self.set(x, y, value);
        return false;
    }
*/