stratadox / puzzle-solver
A generic puzzle solving package, capable of solving a wide variety of puzzles.
Requires
- php: >=7.2
- stratadox/immutable-collection: ^1.1
Requires (Dev)
- ext-json: *
- ext-readline: *
- phpunit/phpunit: ^8.5
- roave/security-advisories: dev-master
README
A generic puzzle solving package, capable of solving a wide variety of puzzles.
Examples
Some examples of puzzles it can solve:
- Mazes
- The Wolf-Goat-Cabbage problem
- Network navigation puzzles
- N-Queens problem
- Sliding Crates puzzle
- Sliding Puzzles
- Sudoku puzzles
Motivation
People kept asking me to implement a solver for this puzzle or that puzzle. This time, instead of just solving one puzzle, I figured I'd make a universal puzzle solver that would simply solve all of those puzzles and all puzzles to come, in one swift strike. Plus, this way, the algorithms can be re-used for different purposes, such as AI for video games or a solver for some real-life problem. Who knows what the future brings!
Basic usage
There are two "ways" to use this package: the Universal Solver, an informed "swiss army knife" approach, or the Brute Solver... what's in a name.
Universal Solver
The Universal Solver is like a swiss army knife for puzzle solvers.
Feed it with some information on what you're looking for, and receive a solver for your puzzle. All the puzzles that are implemented as examples, as well as many puzzles that don't have an example implementation, can be given efficient solvers using this approach.
5-queens problem with universal solver
Solving a 5-queens problem:
<?php use Stratadox\PuzzleSolver\Find; use Stratadox\PuzzleSolver\Puzzle\NQueens\NQueensPuzzle; use Stratadox\PuzzleSolver\UniversalSolver; $solver = UniversalSolver::forAPuzzle() ->withGoalTo(Find::allBestSolutions()) ->whereMovesEventuallyRunOut() ->select(); $solutions = $solver->solve(NQueensPuzzle::forQueens(5)); assert(count($solutions) === 10);
Sliding puzzle with universal solver
Solving a sliding puzzle:
<?php use Stratadox\PuzzleSolver\Find; use Stratadox\PuzzleSolver\Puzzle\SlidingPuzzle\LevenshteinHeuristic; use Stratadox\PuzzleSolver\Puzzle\SlidingPuzzle\SlidingPuzzle; use Stratadox\PuzzleSolver\UniversalSolver; $solver = UniversalSolver::aimingTo(Find::aBestSolution()) ->withHeuristic(new LevenshteinHeuristic()) ->select(); $puzzle = SlidingPuzzle::withPieces( [2, 4, 1], [8, 5, 7], [3, 0, 6] ); $solution = $solver->solve($puzzle)[0]; assert(count($solution->moves()) === 25);
Brute Solver
On the to-do list.
Available Algorithms
Rather than providing a set number of algorithms, this package provides a composable algorithm.
The solver itself can be of one of two flavours, with one of three basic search strategies which in turn can be refined with a number of decorators.
Flavours
The basic solver comes in two flavours: eager or lazy.
Eager
Eager puzzle solvers will search for the first valid solution. Eager solvers will stop after finding a single solution, making them neat for puzzles that can have only one possible solution, or require only a single solution.
Lazy
Lazy puzzle solvers will continue to look for solutions until they've found all valid solutions. Lazy solvers can be used for puzzles that require more than one solution.
Search Strategies
There are three main search strategies available: depth-first, breadth-first and best-first.
Depth-first
Depth-first searches continuously follow the first option, until it turns out the branch does not lead to a solution, at which point it tracks back to the first next available option.
Breadth-first
Breadth-first searches continuously explore all available options, before passing into the options available after those.
Best-first
Best-first searches enqueue newly encountered nodes by order of quality. The move that is most likely to lead to the desired outcome is considered first. In order to determine the quality of a move, the best-first strategy can be provisioned with a heuristic.
Decorators
In order to optimise the search, and/or to not get stuck in eternal loops, a search strategy will typically be wrapped in at least one decorator.
Visited Node Skipper
Visited Node Skipper keeps a list of puzzle states that have already been encountered during the search to skip candidates when they are about to be considered for a second time.
Visited Node Cost Checker
Visited Node Cost Checker keeps a record of the cost of reaching each considered candidate. When a candidate is encountered that already has a recorded cost, the cost of the newly discovered path to reach the same state as before is compared with the previously recorded cost. If the cost is lower than before, the record gets updated and the new candidate is considered. In case the cost is equal or higher than previous paths to the same goal, the candidate is discarded.
Worse-Than-Best Solution Skipper
The Worse-Than-Best Solution Skipper keeps track of the lowest cost of the solutions that have been found during the search. Each time a node is encountered of which the path cost is more than the cost of the cheapest solution that has already been found, the node is skipped.
Duplicate Node Skipper
Duplicate Node Skipper prevents paths from getting into loops. Before considering a new candidate, all previous puzzle states are compared with the new state. If the new puzzle state was already reached on this very path, the candidate is considered a loop and gets rejected.
Iteration Limiter
Iteration Limiter aborts the search when the amount of considered candidates exceeds a set limit.
Debug Logger
Debug Logger is a visualiser for the puzzle solver. Each time a new candidate is taken under consideration, the debug logger logs it to the output stream.
To-do
-
A "Brute Solver": given an iteration limit, try all* configurations of solvers.
- Start with the lazy searches, then move to eager.
- Try a solver, catch OutOfIterations and attempt the next.
(*) Maybe not all, but a bunch of sensible ones..
-
A neat (and extensible) console app to solve puzzles with. The current
samples
directory is a bit primitive.- PuzzleFactory interface and a factory per puzzle, to streamline loading puzzle input and enhance extensibility.
- SolutionRenderer
- Symfony console Application? (To decide: do we want that dependency in a utility repo)
-
Website version (Or rather, the link to a future repository for that)
- Easy-to-use way to add new puzzles? (Can that be done?)