JSoko Solver

From Sokoban Wiki

Revision as of 22:59, 28 January 2017

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.

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.