# [−][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 2*1:N*M.
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. |