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.
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.
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
This makes the solver wait one second (1000 milliseconds) before continuing to the next step.
Solves puzzles using back tracking.
Solves puzzles using minimum entropy search.
Stores settings for entropy solver.
Solves puzzle using multiple strategies at the same time. Each strategy is evaluated one step by turn until a solution is found.
Stores settings for solver.
Implemented by puzzles.
Combines multiple priority lists together.