sudoku-rust/src/main.rs

use serde_derive::{Deserialize, Serialize};
use serde_xml_rs::{from_reader, from_str, to_string};

use clap::Parser;

use std::fmt;
use std::fs::File;

use std::collections::HashSet;

#[derive(Debug, Serialize, Deserialize, PartialEq)]
struct Graph {
    order: i32,
    #[serde(rename = "type")]
    game_type: String,
    #[serde(rename = "specific-type")]
    specific_type: String,
}

#[derive(Debug, Serialize, Deserialize, PartialEq)]
struct Puzzle {
    graph: Graph,
    values: String,
    solution: String,
}

#[derive(Debug, Serialize, Deserialize, PartialEq)]
struct Game {
    #[serde(rename = "had-help")]
    help: i16,
    #[serde(rename = "msecs-elapsed")]
    elapsed: u32,
    puzzle: Puzzle,
}
#[derive(Debug, Serialize, Deserialize, PartialEq)]
struct Ksudoku {
    game: Game,
}

const SIZE: u8 = 9;
const MAX_SIZE: u8 = 81;

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

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

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

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

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

*/

impl Sudoku {
    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
    }

    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];
        }
    }

    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 >= SIZE {
                y = 0;
                x += 1;
            }
        }
    }

    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 = 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();
    }

    fn display(&self) {
        println!("╔═══╦═══╦═══╗");
        for y in 0..SIZE {
            print!("║");
            for x in 0..SIZE {
                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 == SIZE {
                    println!("╚═══╩═══╩═══╝");
                } else {
                    println!("╠═══╬═══╬═══╣");
                }
            }
        }
    }

    fn display_possible(&self) {
        for y in 0..SIZE {
            for x in 0..SIZE {
                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!("");
        }
    }

    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..SIZE {
                // 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..SIZE {
                    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..SIZE {
            g.for_column(i, 1);
            group_process(self, &g);
            g.for_row(1, i);
            group_process(self, &g);
            g.for_iter(i);
            group_process(self, &g);
        }

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

            for gidx in 0..SIZE - 1 {
                let gpos = g.items[gidx as usize];
                if self.possible[gpos as usize].len() == 2 {
                    // Found a pair
                    for fidx in gidx + 1..SIZE {
                        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!
                                println!(
                                    "Pair found! {} {}: {} {:?} and {} {:?}",
                                    gidx,
                                    fidx,
                                    gpos,
                                    xy(gpos),
                                    fpos,
                                    xy(fpos)
                                );
                                // 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;
                                }

                                for remove in 0..SIZE {
                                    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;
                                    };
                                    if self.possible[rpos as usize].take(&values[1]).is_some() {
                                        found_something = 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..SIZE {
                                        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..SIZE {
                                        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
    }
}

// #[derive(Debug)]
struct Group {
    items: [u8; SIZE as usize],
}

impl fmt::Debug for Group {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if f.alternate() {
            write!(f, "Group {{ {}[{},{}], {}[{},{}], {}[{},{}], {}[{},{}], {}[{},{}], {}[{},{}], {}[{},{}], {}[{},{}], {}[{},{}] }}",
                self.items[0], xy(self.items[0]).0, xy(self.items[0]).1,
                self.items[1], xy(self.items[1]).0, xy(self.items[1]).1,
                self.items[2], xy(self.items[2]).0, xy(self.items[2]).1,
                self.items[3], xy(self.items[3]).0, xy(self.items[3]).1,
                self.items[4], xy(self.items[4]).0, xy(self.items[4]).1,
                self.items[5], xy(self.items[5]).0, xy(self.items[5]).1,
                self.items[6], xy(self.items[6]).0, xy(self.items[6]).1,
                self.items[7], xy(self.items[7]).0, xy(self.items[7]).1,
                self.items[8], xy(self.items[8]).0, xy(self.items[8]).1,
            )
        } else {
            f.debug_struct("Group").field("items", &self.items).finish()
        }
    }
}

impl Group {
    fn new() -> Self {
        Group {
            items: [0; SIZE as usize],
        }
    }

    fn for_column(&mut self, x: u8, _y: u8) {
        for y in 0..SIZE {
            self.items[y as usize] = pos(x, y);
        }
    }
    fn for_row(&mut self, _x: u8, y: u8) {
        for x in 0..SIZE {
            self.items[x as usize] = pos(x, y);
        }
    }
    fn for_block(&mut self, x: u8, y: u8) {
        // Find starting block positions
        let sb_x = x - (x % 3);
        let sb_y = y - (y % 3);
        for i in 0..SIZE {
            let ix = i % 3;
            let iy = i / 3;
            // println!("i = {}, sb.x = {} sb.y = {}, ix = {} iy = {}", i, sb_x, sb_y, ix, iy);
            self.items[i as usize] = pos(sb_x + ix, sb_y + iy);
        }
    }

    fn for_iter(&mut self, i: u8) {
        let sb_x = (i % 3) * 3;
        let sb_y = (i / 3) * 3;
        self.for_block(sb_x, sb_y);
    }

    fn display(&self) {
        for i in 0..SIZE {
            let v = self.items[i as usize];
            print!("{} [{},{}] ", v, xy(v).0, xy(v).1);
        }
        println!("");
    }
}

// Command line arguments - via clap

#[derive(Parser)]
struct Cli {
    /// The path to the file to read
    filename: std::path::PathBuf,
}

fn main() {
    let args = Cli::parse();

    let filename = args.filename; // "../puzzle1";
    let fh = File::open(filename).unwrap();
    let puzzle: Ksudoku = from_reader(fh).unwrap();
    println!("Puzzle: {:?}", puzzle);

    let mut s = Sudoku::new();
    s.load_xsudoku(&puzzle.game.puzzle.values);
    s.display();
    s.display_possible();

    while s.solve() {
        println!("Try it again...");
        s.display();
        s.display_possible();
    }

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

    /*
    let mut g = Group::new();
    g.for_row(1, 1);
    print!("Row: ");
    println!("{:?}", g);
    println!("{:#?}", g);
    // g.display();
    print!("Col: ");
    g.for_column(1, 1);
    println!("{:?}", g);
    // g.display();
    println!("Blk testing output: ");

    for i in 0..SIZE {
        g.for_block(i, i);
        println!("({},{} {:#?})", i, i, g);
        // g.display();
    }
    */
}