JSoko Solver
From Sokoban Wiki
JSoko solver
This article is a technical description of my solver.
The JSoko solver is part of my program JSoko.
It's written in Java. The source code is available as the whole JSoko project is open source.
Contents |
Limits of the solver
The solver inherits the limits of JSoko.
This means in can only be used for levels not larger than 70*70 squares.
The solver only tries to find any solution regardless of the number of moves or pushes needed to solve the level.
The solver can only be used as part of JSoko, since there is no stand-alone version.
JSoko overall structure
Search algorithm
The main search is an A* search. The solver only uses forward searching. However, if the level is considered a goal room level then a packing order algorithm calculates a packing order for filling the goals first.
Heuristic score
The A* search calculates the minimum perfect bipartite matching of the boxes' distances to the goals after every push. This pushes lower bound is enhanced by adding a penalty for simple linear conflicts.
Transposition table
All board positions are stored in a hash table. The player player is normalized to the top-left position reachable in the current board position before the board positions are stored in the hash table.
Deadlock detection
JSoko can detect all deadlocks described in the Deadlocks article. Neither a precalculation of deadlocks nor a deadlock database is used.
PI-Corral pruning
The solver uses the PI-Corral pruning developed by Brian Damgaard and me to reduce the search tree.
