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; 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::::new()) .collect(); let arr: [Vec; 10] = [(); 10].map(|_| Vec::with_capacity(100)); */ impl Sudoku { pub fn new() -> Self { // let b : HashSet = 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 = 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 } }