JSoko Solver

From Sokoban Wiki

Revision as of 23:26, 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.

Packing sequence

A packing sequence is calculated for some levels:
The solver counts the "connected goals".
The definition of "connected goal" is:

1. The goal has one or more neighboring goals
2. When the neighboring goal is located at one axis, there must be a neighboring position along the other axis, which either is a goal too, or a wall

If the number of connected goals is higher than 8 the level is classified as packing sequence level.
The packing sequence is calculated by performing a backward search:
all boxes are placed on goals and the search tries to remove one box at a time. The box positions at the start of the level are considered backward goals during the search.
If a box can be pulled to a backward goal then it is removed from the board.
If none of the boxes can be pulled to any backward goal anymore the boxes are pulled one position to any direction and then it's checked again if any of the boxes can now reach a backward goal.
if all boxes have reached a goal then a packing sequence has been found.
This push sequence is then used by the forward search to push the boxes to the goals.