A Sokoban solver

A Sokoban solver in Python.

The codes can be found in https://github.com/smsxgz/dailyprogrammer/tree/master/puzzlerama/sokoban.

In following, we introduce some details in our implement of Sokoban solver.

Normalized player position

Consider that two states is equivalent if the boxes are at the same positions and the player positions are in the same player access area, so we can only store normalized player position. We use positions of boxes and top-left reachable position as our state to reduce the number of states in the search tree.

Deadlocks

We only consider the simple deadlocks from which a box never can be pushed to a goal, no matter where the other boxes are located in the board. Once we push a box into a square which is a deadlock, the state becomes unsolvable immediately.

We detect the simple deadlocks by searching all squares where we can pull a box from one of the goals to. A simple breadth-first-searching is enough.

A* search algorithm

We use a Fibonacci heap for the priority queue required in A* search algorithm. For each state, we store the information, including box positions, normalized player position, reachable position, available moves, f-score, g-score, in a node of the heap and employ a dictionary to record corresponding pointer to the corresponding node.

It worth noting that standard binary heap, leftist heap and binomial heap are not qualified for the work here. In standard leftist heap or binomial heap, if we decrease value of a node, we may need to swap the value of some nodes instead of nodes themselves to fix the heap. Of course we can modify standard leftist heap or binomial heap to reach our needs, for example we can apply doubly linked list instead of singly linked list in standard binomial heap to make exchange nodes directly possible.

A Sokoban solver

Contents

Normalized player position

Deadlocks

A* search algorithm

Reference