It worth noting that standard binary heap, leftist heap and binomial heap are not qualified for the work here. 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. We use a Fibonacci heap for the priority queue required in A* search algorithm. A simple breadth-first-searching is enough. We detect the simple deadlocks by searching all squares where we can pull a box from one of the goals to. Once we push a box into a square which is a deadlock, the state becomes unsolvable immediately.

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. We use positions of boxes and top-left reachable position as our state to reduce the number of states in the search tree. Normalized player positionĬonsider 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. In following, we introduce some details in our implement of Sokoban solver.

Online sokoban solver