sudoku-rust/src/sudoku.rs

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

use std::collections::HashSet;

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

#[derive(Debug)]
pub struct Sudoku {
    pub board: [u8; MAX_SIZE as usize],
    pub possible: [HashSet<u8>; 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))
}

/*
(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 s = Sudoku {
            board: [0; MAX_SIZE as usize],
            possible: [(); MAX_SIZE as usize].map(|_| HashSet::from_iter(1..=9)),
            // possible: [HashSet::from_iter(1..=9); MAX_SIZE as usize],
            // possible: [[0; SIZE as usize]; MAX_SIZE as usize],
            // possible: [(0..MAX_SIZE).map( |_| (1..=9).collect())],
            // possible: [(1..=9).map(|_| HashSet::new()).collect(); MAX_SIZE as usize],
        };
        s
    }

    pub fn clear(&mut self) {
        for x in 0..MAX_SIZE {
            self.board[x as usize] = 0;
            self.possible = [(); MAX_SIZE as usize].map(|_| HashSet::from_iter(1..=9));
            /*
            self.possible[x as usize].clear();
            for i in 1..=9 {
                self.possible[x as usize].insert(i);
            }
            */
            // self.possible[x as usize] = [1, 2, 3, 4, 5, 6, 7, 8, 9];
        }
    }

    pub fn load_xsudoku(&mut self, s: &str) {
        self.clear();
        let mut x: u8 = 0;
        let mut y: u8 = 0;
        for ch in s.chars() {
            if ch >= 'b' {
                self.set(x, y, ch as u8 - 'a' as u8);
                // self.board[pos(x, y) as usize] = ch as u8 - 'a' as u8;
            };
            y += 1;
            if y >= WIDTH {
                y = 0;
                x += 1;
            }
        }
    }

    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.items {
            // remove value from these sets.
            self.possible[g as usize].take(&value);
        }
        g = for_column(x); 
        // g.for_column(x, y);
        for g in g.items {
            // remove value from these sets.
            self.possible[g as usize].take(&value);
        }
        g = for_cell(which_cell(x,y)); 
        // g.for_block(x, y);
        for g in g.items {
            // remove value from these sets.
            self.possible[g as usize].take(&value);
        }
        self.possible[pos(x, y) as usize].clear();
    }

    pub fn set2(&mut self, x: u8, y: u8, value: u8) {
        self.board[pos(x, y) as usize] = value;
        // Ok, update the possible
        let mut g = Group::new();
        g.for_row(x, y);
        for g in g.items {
            // remove value from these sets.
            self.possible[g as usize].take(&value);
        }
        
        g.for_column(x, y);
        for g in g.items {
            // remove value from these sets.
            self.possible[g as usize].take(&value);
        }
        
        g.for_block(x, y);
        for g in g.items {
            // remove value from these sets.
            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 {
                let mut possible = String::new();

                for p in self.possible[pos(x, y) as usize].iter() {
                    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 solve(&mut self) -> 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].len() == 1 {
                // Get the value
                let value = self.possible[i as usize].iter().next().cloned().unwrap();
                // Found one!
                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: 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]);
                values.extend(&this.possible[grp.items[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.items[gidx as usize] as usize].contains(&v) {
                        count += 1;
                        pos = grp.items[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();
                    println!("Set2 {:?} to {}", xy(pos), v);
                    this.set(xy(pos).0, xy(pos).1, *v);
                    found_something = true;
                }
            }
        };

        // Change to 0..SIZE ...  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);
        }

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

            for gidx in 0..WIDTH - 1 {
                let gpos = g.items[gidx as usize];
                if self.possible[gpos as usize].len() == 2 {
                    // Found a pair
                    for fidx in gidx + 1..WIDTH {
                        let fpos = g.items[fidx as usize];
                        if self.possible[fpos as usize].len() == 2 {
                            // Ok, there's another pair
                            if self.possible[gpos as usize].is_subset(&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;

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

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

                                // 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]
                                            .take(&values[0])
                                            .is_some()
                                        {
                                            found_something = true;
                                        };
                                        if self.possible[pos(column, remove) as usize]
                                            .take(&values[1])
                                            .is_some()
                                        {
                                            found_something = 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]
                                            .take(&values[0])
                                            .is_some()
                                        {
                                            found_something = true;
                                        };
                                        if self.possible[pos(remove, row) as usize]
                                            .take(&values[1])
                                            .is_some()
                                        {
                                            found_something = true;
                                        };
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        found_something
    }
}