Struct quickbacktrack::EntropyBackTrackSolver

pub struct EntropyBackTrackSolver<T> where
    T: Puzzle,  {
    pub original: T,
    pub state: T,
    pub prevs: Vec<(T::Pos, T::Val, bool)>,
    pub choice: Vec<(T::Pos, Vec<T::Val>)>,
    pub start_choice: Vec<(T::Pos, Vec<T::Val>)>,
    pub weights: Vec<Vec<f64>>,
    pub settings: SolveSettings,
    pub entropy_settings: EntropySolveSettings,
}

Solves puzzles using minimum entropy search.

This solver learns from repeatedly attempting to solve the puzzle. The algorithm is inspired by WaveFunctionCollapse.

This solver is general and guaranteed to find a solution, if any. It also uses custom priority of choices in the initial attempts.

The search works by attempting normal backtrack solving, but increasing weights to choices each time they are made. When the algorithm is stuck, it minimizes entropy of common choices. At later attempts, the algorithm will try these common choices first.

When EntropySettings::noise is non-zero, the choices will occationally be shuffled. For more information, see EntropySolveSettings.

Fields

original: T

Stores the original state.

state: T

Stores the state.

prevs: Vec<(T::Pos, T::Val, bool)>

Stores the previous values of a position before making a choice. If the flag is true, the value was inserted due to a simple choice.

choice: Vec<(T::Pos, Vec<T::Val>)>

Stores the choices for the states.

start_choice: Vec<(T::Pos, Vec<T::Val>)>

The initial choices.

weights: Vec<Vec<f64>>

Stores weights of choices.

settings: SolveSettings

Stores solve settings.

entropy_settings: EntropySolveSettings

Stores entropy solve settings.

Implementations

impl<T> EntropyBackTrackSolver<T> where
    T: Puzzle, 

pub fn new(
    puzzle: T,
    start_choice: Vec<(T::Pos, Vec<T::Val>)>,
    entropy_settings: EntropySolveSettings,
    settings: SolveSettings
) -> Self

Creates a new collapse solver.

pub fn entropy(&self, i: usize) -> f64

Calculates the entropy of a choice.

pub fn min_entropy<G>(&self, g: &mut G) -> Option<(usize, T::Pos)> where
    G: FnMut(&T, T::Pos) -> Vec<T::Val>, 

Finds the position with least entropy.

pub fn observe(&mut self, pos: T::Pos, new_val: T::Val) where
    T::Pos: PartialEq, 

Increase weight of observed state.

pub fn solve<G>(&mut self, g: G) -> (u64, Option<Solution<T>>) where
    G: Copy + FnMut(&T, T::Pos) -> Vec<T::Val>,
    T::Pos: PartialEq, 

Attempts to solve puzzle repeatedly, using SolveSettings::max_iterations.

The solver learns by reusing weights from previous attempts.

pub fn solve_single_attempt<G>(&mut self, g: G) -> Option<Solution<T>> where
    G: FnMut(&T, T::Pos) -> Vec<T::Val>,
    T::Pos: PartialEq, 

Solves puzzle, using a closure for picking options in preferred order.

This can be called repeated times, limited by SolveSettings::max_iterations to reuse weights from previous attempts.