Struct sudoku_variants::solver::strategy::impls::BoundedCellsBacktrackingStrategy

pub struct BoundedCellsBacktrackingStrategy<FC, FA, S> where
    FC: Fn(usize) -> usize,
    FA: Fn(usize) -> Option<usize>,
    S: Strategy,  { /* fields omitted */ }

A Strategy which looks for groups in which some number can only occur in a limited number of cells (up to a specified maximum) and tries all of them. It then uses a wrapped strategy to find deductions in all paths. If any of those deductions hold for all options, they are stored in the metadata.

As an example, consider the following situation:

╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║   │   │   ║   │ 5 │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 1 │ 2 │ 3 ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 4 │   │   ║   │   │   ║ X │   │   ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║ 2 │   │   ║   │   │   ║ X │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │ 5 ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 3 │ 1 │ 4 ║   │   │   ║   │   │   ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │ Y │ Y ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ Y │ Y ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ Y │ Y ║   │   │   ║   │   │   ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

In this configuration, a bounded cells backtracking strategy without any wrapped stratey (i.e. a NoStrategy) with a maximum of 2 cells to consider would find that the cells marked with X cannot be a 5. This is because both in the top-left and the top-central box, there are two places for 5s each, both in the same rows, thus excluding a 5 from the X-cells. Furthermore, if an OnlyCellStrategy with at least 1 application is used as the continuation strategy, the bounded cells backtracking strategy would be able to deduce that fives must always be in columns 2 and 3 in the top-left and top-central box and thus all cells marked with Y cannot be a 5.

Note that this strategy contains some common strategies with different names. For example a bounded cells backtracking strategy with a limit of 2 cells and an OnlyCellStrategy with 1 application would find X-Wings.

Implementations

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>

Creates a new bounded cells backtracking strategy.

Arguments

• max_cells_computer: A closure that, given the grid size, computes the maximum number of cells in a group in which a number can be for this strategy to consider all of them.
• max_applications_computer: A closure that, given the grid size, computes the maximum number of times the continuation strategy may be applied for each considered cell before no further inference is done. If no limit is desired, this may return None.
• continuation_strategy: The Strategy with which each considered cell is developed to find any inferences.

Trait Implementations

impl<FC: Clone, FA: Clone, S: Clone> Clone for BoundedCellsBacktrackingStrategy<FC, FA, S> where
    FC: Fn(usize) -> usize,
    FA: Fn(usize) -> Option<usize>,
    S: Strategy, 

fn clone(&self) -> BoundedCellsBacktrackingStrategy<FC, FA, S>

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

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

Applies this strategy to the given Sudoku. The strategy may rely on and modify the information in the given sudoku_info. This instance is given to other strategies that participate in the solution and/or future iterations of the same strategy. It can thus be used to communicate insights.