// 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, } 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> { 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> { 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> { 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 { let mut result = Vec::::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) { let mut workset = self.clone(); let mut total_solutions: u16 = 0; let mut solutions: Vec = 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, 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>, } impl AnyPossible { pub fn new(board_size: u8) -> Self { let mut initial = GenBits::(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::(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 of each item formatted. /// - Return max length. pub fn pos_max(&self) -> (Vec, usize) { let mut pos = Vec::::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::(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 = 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 = HashSet::new(); let mut values = GenBits::(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 = HashSet::new(); let mut values = GenBits::(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 = 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 = 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 = 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; } */