[][src]Crate quickbacktrack

Library for back tracking with customizable search for possible moves.

Back tracking is a general algorithm to find solution for constraint satisfaction problems.

The performance of finding a solution can vary greatly with the algorithm used to look for the best position to set a value next. For example, a sodoku puzzle with many missing numbers can take 59 iterations when picking an empty slot with minimum number of options, but it takes 295 992 iterations to solve when looking for the first empty slot.

One can explain this difference in performance using probability theory. If a slot can contain 2 correct out of N possible values, the odds are 2:N. When this slot is tangled through constraints with another slot with odds 1:M, the total odds become 21:NM. To maximize the chance of finding a correct solution, one must maximize the odds for the remaining moves or fail to satisfy the constraints as early as possible. Fewer choices reduces the chances of being wrong, increases the chance of failing constraints early and therefore increases the chance of finding a solution more quickly.

By making the search customizable, one can easier experiment with different algorithms to pick the next best guess and see which has the best performance on a given problem. This library is designed to assist with this kind of exploration.

Solving simple moves

In some constraint problems, there are lots of steps that are trivial once a choice is made. For example, in Sudoku a lot of numbers can be filled in once a number is selected for a slot.

By solving simple moves separately, one can improve performance and reduce the debugging output significantly.

Debugging

The relationship between the structure of a puzzle and an efficient algorithm to pick the next best guess can be non-trivial, so understanding what happens is essential for finding an efficient algorithm.

When the setting SolveSettings::debug(true) is enabled, the solver prints out the steps to standard output while solving.

The solver prints "Guess" when making a new move, and "Try" when changing an earlier move. Number of iterations are printed at the end when the puzzle is solved.

You can slow down the solving by setting SolveSettings::sleep_ms(1000). This makes the solver wait one second (1000 milliseconds) before continuing to the next step.

Structs

BackTrackSolver

Solves puzzles using back tracking.

EntropyBackTrackSolver

Solves puzzles using minimum entropy search.

EntropySolveSettings

Stores settings for entropy solver.

MultiBackTrackSolver

Solves puzzle using multiple strategies at the same time. Each strategy is evaluated one step by turn until a solution is found.

Solution

Contains solution.

SolveSettings

Stores settings for solver.

Traits

Puzzle

Implemented by puzzles.

Functions

combine

Combines multiple priority lists together.