use crate::constraint::Constraint;
use crate::solver::strategy::{Strategy, SudokuInfo};
use crate::util::USizeSet;
use std::collections::HashSet;
#[derive(Clone)]
pub struct NakedSingleStrategy;
impl Strategy for NakedSingleStrategy {
fn apply(&self, sudoku_info: &mut SudokuInfo<impl Constraint + Clone>)
-> bool {
let size = sudoku_info.size();
let mut changed = false;
for row in 0..size {
for column in 0..size {
let options = sudoku_info.get_options(column, row).unwrap();
if sudoku_info.get_cell(column, row).unwrap() == None &&
options.len() == 1 {
let option = options.iter().next().unwrap();
sudoku_info.enter_cell_no_update(column, row, option).unwrap();
changed = true;
}
}
}
sudoku_info.invalidate();
changed
}
}
#[derive(Clone)]
enum Location {
None,
One(usize, usize),
Multiple
}
impl std::fmt::Display for Location {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Location::None => f.write_str("None"),
Location::One(a, b) => f.write_str(format!("One({}, {})", a, b).as_str()),
Location::Multiple => f.write_str("Multiple")
}
}
}
impl Location {
fn union(&self, column: usize, row: usize) -> Location {
match self {
Location::None => Location::One(column, row),
Location::One(_, _) => Location::Multiple,
Location::Multiple => Location::Multiple
}
}
}
#[derive(Clone)]
pub struct OnlyCellStrategy;
impl Strategy for OnlyCellStrategy {
fn apply(&self, sudoku_info: &mut SudokuInfo<impl Constraint + Clone>)
-> bool {
let size = sudoku_info.size();
let grid = sudoku_info.sudoku().grid();
let groups = sudoku_info.sudoku().constraint().get_groups(grid);
let mut changed = false;
for group in groups {
if group.len() < size {
continue;
}
let mut locations = vec![Location::None; size + 1];
for (column, row) in group {
if sudoku_info.get_cell(column, row).unwrap().is_some() {
continue;
}
let options = sudoku_info.get_options(column, row).unwrap();
for option in options.iter() {
let location = &locations[option];
locations[option] = location.union(column, row);
}
}
for (number, location) in locations.into_iter().enumerate() {
if let Location::One(column, row) = location {
sudoku_info.enqueue_enter_cell(column, row, number)
.unwrap();
changed = true;
}
}
}
sudoku_info.invalidate();
changed
}
}
#[derive(Clone)]
pub struct TupleStrategy<F: Fn(usize) -> usize> {
max_size_computer: F
}
impl<F: Fn(usize) -> usize> TupleStrategy<F> {
pub fn new(max_size_computer: F) -> TupleStrategy<F> {
TupleStrategy {
max_size_computer
}
}
}
#[derive(Clone)]
struct Tuple {
cells: HashSet<(usize, usize)>,
options: USizeSet
}
impl Tuple {
fn new(size: usize) -> Tuple {
Tuple {
cells: HashSet::new(),
options: USizeSet::new(1, size).unwrap()
}
}
fn add_cell(&mut self, options: &USizeSet, column: usize, row: usize) {
self.cells.insert((column, row));
self.options |= options;
}
fn is_full(&self) -> bool {
let options_len = self.options.len();
options_len >= 2 && options_len <= self.cells.len()
}
}
fn find_tuples_rec(sudoku_info: &SudokuInfo<impl Constraint + Clone>,
group_rest: &[(usize, usize)], max_size: usize, mut curr_tuple: Tuple,
accumulator: &mut Vec<Tuple>) {
if curr_tuple.options.len() > max_size {
return;
}
if curr_tuple.is_full() {
accumulator.push(curr_tuple);
return;
}
if let Some((next_column, next_row)) = group_rest.iter().cloned().next() {
let next_options =
sudoku_info.get_options(next_column, next_row).unwrap();
let next_rest = &group_rest[1..];
if next_options.len() > 1 {
find_tuples_rec(sudoku_info, next_rest, max_size,
curr_tuple.clone(), accumulator);
curr_tuple.add_cell(next_options, next_column, next_row);
find_tuples_rec(sudoku_info, next_rest, max_size, curr_tuple,
accumulator);
}
else {
find_tuples_rec(sudoku_info, next_rest, max_size, curr_tuple,
accumulator);
}
}
}
fn find_tuples(sudoku_info: &SudokuInfo<impl Constraint + Clone>,
group: &[(usize, usize)], max_size: usize) -> Vec<Tuple> {
let mut result = Vec::new();
find_tuples_rec(&sudoku_info, group, max_size,
Tuple::new(sudoku_info.size()), &mut result);
result
}
impl<F: Fn(usize) -> usize> Strategy for TupleStrategy<F> {
fn apply(&self, sudoku_info: &mut SudokuInfo<impl Constraint + Clone>)
-> bool {
let mut changed = false;
let grid = sudoku_info.sudoku().grid();
let groups = sudoku_info.sudoku().constraint().get_groups(grid);
let max_size = (self.max_size_computer)(sudoku_info.size());
for group in groups {
let tuples = find_tuples(&sudoku_info, &group, max_size);
for tuple in tuples {
for (column, row) in group.iter().cloned() {
if sudoku_info.get_cell(column, row).unwrap() == None &&
!tuple.cells.contains(&(column, row)) {
let mut cell_options =
sudoku_info.get_options_mut(column, row).unwrap();
let before_len = cell_options.len();
cell_options -= &tuple.options;
changed |= before_len != cell_options.len();
}
}
}
}
changed
}
}
#[derive(Clone)]
pub struct BoundedOptionsBacktrackingStrategy<FO, FA, S>
where
FO: Fn(usize) -> usize,
FA: Fn(usize) -> Option<usize>,
S: Strategy
{
max_options_computer: FO,
max_applications_computer: FA,
continuation_strategy: S
}
impl<FO, FA, S> BoundedOptionsBacktrackingStrategy<FO, FA, S>
where
FO: Fn(usize) -> usize,
FA: Fn(usize) -> Option<usize>,
S: Strategy
{
pub fn new(max_options_computer: FO, max_applications_computer: FA,
continuation_strategy: S)
-> BoundedOptionsBacktrackingStrategy<FO, FA, S> {
BoundedOptionsBacktrackingStrategy {
max_options_computer,
max_applications_computer,
continuation_strategy
}
}
}
fn apply_continuation(max_applications: Option<usize>,
continuation_strategy: &impl Strategy,
sudoku_info: &mut SudokuInfo<impl Constraint + Clone>) {
match max_applications {
None => {
while continuation_strategy.apply(sudoku_info) { }
},
Some(max) => {
for _ in 0..max {
if !continuation_strategy.apply(sudoku_info) {
break;
}
}
}
}
}
fn collapse_results<C: Constraint + Clone>(sudoku_info: &mut SudokuInfo<C>,
results: Vec<SudokuInfo<C>>) -> bool {
if results.is_empty() {
return false;
}
let mut results_iter = results.into_iter();
let first = results_iter.next().unwrap();
let union = results_iter.fold(first,
|mut acc, x| {
acc.union_assign(&x).unwrap();
acc
});
sudoku_info.intersect_assign(&union).unwrap()
}
impl<FO, FA, S> Strategy for BoundedOptionsBacktrackingStrategy<FO, FA, S>
where
FO: Fn(usize) -> usize,
FA: Fn(usize) -> Option<usize>,
S: Strategy
{
fn apply(&self, sudoku_info: &mut SudokuInfo<impl Constraint + Clone>)
-> bool {
let size = sudoku_info.size();
let max_options = (self.max_options_computer)(size);
let max_applications = (self.max_applications_computer)(size);
let mut changed = false;
for column in 0..size {
for row in 0..size {
if sudoku_info.get_cell(column, row).unwrap().is_some() {
continue;
}
let options = sudoku_info.get_options(column, row).unwrap();
if options.len() > max_options {
continue;
}
let mut results = Vec::new();
for option in options.iter() {
let mut sudoku_info = sudoku_info.clone();
sudoku_info.enter_cell(column, row, option).unwrap();
apply_continuation(max_applications,
&self.continuation_strategy, &mut sudoku_info);
results.push(sudoku_info);
}
changed |= collapse_results(sudoku_info, results);
}
}
changed
}
}
#[derive(Clone)]
pub struct BoundedCellsBacktrackingStrategy<FC, FA, S>
where
FC: Fn(usize) -> usize,
FA: Fn(usize) -> Option<usize>,
S: Strategy
{
max_cells_computer: FC,
max_applications_computer: FA,
continuation_strategy: S
}
impl<FC, FA, S> BoundedCellsBacktrackingStrategy<FC, FA, S>
where
FC: Fn(usize) -> usize,
FA: Fn(usize) -> Option<usize>,
S: Strategy
{
pub fn new(max_cells_computer: FC, max_applications_computer: FA,
continuation_strategy: S)
-> BoundedCellsBacktrackingStrategy<FC, FA, S> {
BoundedCellsBacktrackingStrategy {
max_cells_computer,
max_applications_computer,
continuation_strategy
}
}
}
impl<FC, FA, S> Strategy for BoundedCellsBacktrackingStrategy<FC, FA, S>
where
FC: Fn(usize) -> usize,
FA: Fn(usize) -> Option<usize>,
S: Strategy
{
fn apply(&self, sudoku_info: &mut SudokuInfo<impl Constraint + Clone>)
-> bool {
let size = sudoku_info.size();
let max_cells = (self.max_cells_computer)(size);
let max_applications = (self.max_applications_computer)(size);
let mut changed = false;
let grid = sudoku_info.sudoku().grid();
let groups = sudoku_info.sudoku().constraint().get_groups(grid);
for group in groups {
if group.len() < size {
continue;
}
let mut number_locations: Vec<Vec<(usize, usize)>> =
vec![Vec::new(); size + 1];
for (column, row) in group {
if sudoku_info.get_cell(column, row).unwrap().is_some() {
continue;
}
let options = sudoku_info.get_options(column, row).unwrap();
for option in options.iter() {
number_locations[option].push((column, row));
}
}
let number_locations_iter = number_locations.into_iter().skip(1);
for (number, locations) in number_locations_iter.enumerate() {
let number = number + 1;
if locations.is_empty() || locations.len() > max_cells {
continue;
}
let mut results = Vec::new();
for (column, row) in locations {
let mut sudoku_info = sudoku_info.clone();
sudoku_info.enter_cell(column, row, number).unwrap();
apply_continuation(max_applications,
&self.continuation_strategy, &mut sudoku_info);
results.push(sudoku_info);
}
changed |= collapse_results(sudoku_info, results);
}
}
changed
}
}
#[derive(Clone)]
pub struct NoStrategy;
impl Strategy for NoStrategy {
fn apply(&self, _: &mut SudokuInfo<impl Constraint + Clone>) -> bool {
false
}
}
pub struct CompositeStrategy<S1: Strategy, S2: Strategy> {
s1: S1,
s2: S2
}
impl<S1: Strategy, S2: Strategy> CompositeStrategy<S1, S2> {
pub fn new(s1: S1, s2: S2) -> CompositeStrategy<S1, S2> {
CompositeStrategy {
s1,
s2
}
}
}
impl<S1: Strategy, S2: Strategy> Strategy for CompositeStrategy<S1, S2> {
fn apply(&self, sudoku_info: &mut SudokuInfo<impl Constraint + Clone>)
-> bool {
self.s1.apply(sudoku_info) | self.s2.apply(sudoku_info)
}
}
impl<S1: Strategy + Clone, S2: Strategy + Clone> Clone for CompositeStrategy<S1, S2> {
fn clone(&self) -> Self {
CompositeStrategy::new(self.s1.clone(), self.s2.clone())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::Sudoku;
use crate::constraint::DefaultConstraint;
use crate::solver::strategy::SudokuInfo;
fn apply<C: Constraint + Clone, S: Strategy>(strategy: S,
sudoku_info: &mut SudokuInfo<C>, apply_once: bool) {
while strategy.apply(sudoku_info) {
if apply_once {
break;
}
}
}
fn test_strategy_stronger_and_sound<C, W, S>(sudoku: Sudoku<C>,
weak_strategy: W, strong_strategy: S, apply_once: bool,
test: impl Fn(&SudokuInfo<C>) -> bool)
where
C: Constraint + Clone,
W: Strategy,
S: Strategy
{
let mut sudoku_info = SudokuInfo::from_sudoku(sudoku.clone());
apply(weak_strategy, &mut sudoku_info, apply_once);
assert!(!test(&sudoku_info));
let mut sudoku_info = SudokuInfo::from_sudoku(sudoku);
apply(strong_strategy, &mut sudoku_info, apply_once);
assert!(test(&sudoku_info));
assert!(sudoku_info.sudoku().is_valid());
}
#[test]
fn naked_single_strategy_finds_digit() {
let sudoku = Sudoku::parse("2x2;\
1, , , ,\
, , ,2,\
, , , ,\
,3, , ", DefaultConstraint).unwrap();
let mut sudoku_info = SudokuInfo::from_sudoku(sudoku);
assert!(NakedSingleStrategy.apply(&mut sudoku_info));
assert_eq!(Some(4), sudoku_info.get_cell(1, 1).unwrap());
}
#[test]
fn only_cell_strategy_finds_digits() {
let sudoku = Sudoku::parse("2x2;\
1, , , ,\
, , ,2,\
, , , ,\
,3, , ", DefaultConstraint).unwrap();
let mut sudoku_info = SudokuInfo::from_sudoku(sudoku);
assert!(OnlyCellStrategy.apply(&mut sudoku_info));
assert_eq!(Some(1), sudoku_info.get_cell(2, 1).unwrap());
assert_eq!(Some(1), sudoku_info.get_cell(1, 2).unwrap());
assert_eq!(Some(2), sudoku_info.get_cell(1, 0).unwrap());
assert_eq!(Some(3), sudoku_info.get_cell(0, 1).unwrap());
}
#[test]
fn tuple_strategy_helps_naked_single_strategy() {
let sudoku = Sudoku::parse("3x3;\
, ,3,4,5,6,7,8,9,\
, ,9,1,2,3,4,5,6,\
, , , , , , , , ,\
, ,4, , , , , , ,\
, ,5, , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ", DefaultConstraint).unwrap();
let weak_strategy = NakedSingleStrategy;
let strong_strategy = CompositeStrategy::new(
TupleStrategy::new(|_| 2), NakedSingleStrategy);
test_strategy_stronger_and_sound(sudoku, weak_strategy,
strong_strategy, false, |s| s.get_cell(2, 2).unwrap() == Some(6));
}
#[test]
fn tuple_strategy_does_not_consider_too_large_tuples() {
let sudoku = Sudoku::parse("3x3;\
, , ,4,5,6,7,8,9,\
, , ,1,2,3,4,5,6,\
, , , , , , , , ,\
, ,4, , , , , , ,\
, ,5, , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ", DefaultConstraint).unwrap();
let weak_strategy = CompositeStrategy::new(
TupleStrategy::new(|_| 2), NakedSingleStrategy);
let strong_strategy = CompositeStrategy::new(
TupleStrategy::new(|_| 3), NakedSingleStrategy);
test_strategy_stronger_and_sound(sudoku, weak_strategy,
strong_strategy, false, |s| s.get_cell(2, 2).unwrap() == Some(6));
}
#[test]
fn bounded_options_backtracking_deduces_impossible_option() {
let sudoku = Sudoku::parse("3x3;\
1, ,2,3,4,5,6, ,7,\
, , , , , , , , ,\
, , , , , , , , ,\
2,3, , , , , , , ,\
4, ,1, , , , , , ,\
5,6,7, , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ", DefaultConstraint).unwrap();
let strategy =
BoundedOptionsBacktrackingStrategy::new(|_| 2, |_| Some(1),
OnlyCellStrategy);
let mut sudoku_info = SudokuInfo::from_sudoku(sudoku);
assert!(strategy.apply(&mut sudoku_info));
assert!(!sudoku_info.get_options(7, 3).unwrap().contains(8));
assert!(!sudoku_info.get_options(7, 3).unwrap().contains(9));
}
fn has_option<C: Constraint + Clone>(sudoku_info: &SudokuInfo<C>,
column: usize, row: usize, option: usize) -> bool {
sudoku_info.get_options(column, row).unwrap().contains(option)
}
#[test]
fn bounded_options_backtracking_respects_application_limit() {
let sudoku = Sudoku::parse("3x3;\
1, ,2,3,4,5,6, ,7,\
, , , , , , , , ,\
, , , , , , , , ,\
2,1, , , , , , , ,\
3, ,6, , , , , , ,\
4,5,7, , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ", DefaultConstraint).unwrap();
let weak_strategy =
BoundedOptionsBacktrackingStrategy::new(|_| 2, |_| Some(1),
NakedSingleStrategy);
let strong_strategy =
BoundedOptionsBacktrackingStrategy::new(|_| 2, |_| Some(2),
NakedSingleStrategy);
test_strategy_stronger_and_sound(sudoku, weak_strategy,
strong_strategy, true, |s|
!has_option(s, 7, 3, 9) && !has_option(s, 7, 3, 9))
}
#[test]
fn bounded_options_backtracking_respects_option_limit() {
let sudoku = Sudoku::parse("3x3;\
1, ,2,3, ,4,5, ,6,\
, , , , , , , , ,\
, , ,7, , ,8, , ,\
2, , ,1, , , , , ,\
3, ,1,4, ,5, , , ,\
4, ,5,2, ,3, , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ", DefaultConstraint).unwrap();
let weak_strategy =
BoundedOptionsBacktrackingStrategy::new(|_| 2, |_| None,
OnlyCellStrategy);
let strong_strategy =
BoundedOptionsBacktrackingStrategy::new(|_| 3, |_| None,
OnlyCellStrategy);
test_strategy_stronger_and_sound(sudoku, weak_strategy,
strong_strategy, true, |s| !has_option(s, 7, 3, 9));
}
#[test]
fn bounded_cells_backtracking_detects_impossible_option() {
let sudoku = Sudoku::parse("3x3;\
, , , ,5, , , , ,\
1,2,3, , , , , , ,\
4, , , , , , , , ,\
2, , , , , , , , ,\
3,1,4, , , , , , ,\
, , , , ,5, , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ", DefaultConstraint).unwrap();
let strategy =
BoundedCellsBacktrackingStrategy::new(|_| 2, |_| Some(0),
NoStrategy);
let mut sudoku_info = SudokuInfo::from_sudoku(sudoku);
assert!(strategy.apply(&mut sudoku_info));
assert!(!sudoku_info.get_options(6, 2).unwrap().contains(5));
assert!(!sudoku_info.get_options(6, 3).unwrap().contains(5));
}
#[test]
fn bounded_cells_backtracking_respects_application_limit() {
let sudoku = Sudoku::parse("3x3;\
, , , ,5, , , , ,\
1,2,3, , , , , , ,\
4, , , , , , , , ,\
2, , , , , , , , ,\
3,1,4, , , , , , ,\
, , , , ,5, , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ", DefaultConstraint).unwrap();
let weak_strategy =
BoundedCellsBacktrackingStrategy::new(|_| 2, |_| Some(0),
OnlyCellStrategy);
let strong_strategy =
BoundedCellsBacktrackingStrategy::new(|_| 2, |_| Some(1),
OnlyCellStrategy);
test_strategy_stronger_and_sound(sudoku, weak_strategy,
strong_strategy, true, |s|
!has_option(s, 1, 6, 5) && !has_option(s, 2, 6, 5));
}
#[test]
fn bounded_cells_backtracking_respects_cell_limit() {
let sudoku = Sudoku::parse("3x3;\
, , , ,5, , , , ,\
1,2,3, , , , , , ,\
4, , , , , , , , ,\
2,1, , , , , , , ,\
3, , , , , , , , ,\
, , , , ,5, , , ,\
, , , , , , , , ,\
, , , , , , , , ,\
, , , , , , , , ", DefaultConstraint).unwrap();
let weak_strategy =
BoundedCellsBacktrackingStrategy::new(|_| 2, |_| Some(1),
OnlyCellStrategy);
let strong_strategy =
BoundedCellsBacktrackingStrategy::new(|_| 3, |_| Some(1),
OnlyCellStrategy);
test_strategy_stronger_and_sound(sudoku, weak_strategy,
strong_strategy, true, |s| !has_option(s, 2, 6, 5));
}
}