Sokoban: Reversed Solving
Frank W. Takes · 2008
This article describes a new method for attempting to solve Sokoban puzzles by means of an efficient algorithm, a task which has proven to be extremely difficult because of both the huge search tree depth and the large branching factor. We present a way of solving Sokoban puzzles that, using several heuristics, starts from the final state of a puzzle, and from there works its way back to the initial state. This method makes the timeconsuming checking for a large portion of the undesired deadlocks unnecessary, giving some interesting results. for this interest comes from the fact that humans can often solve these puzzles in a few minutes doing several hundreds of moves. However, solving a Sokoban puzzle by means of an efficient algorithm has turned out to be very hard, because of both the huge search tree depth and the large branching factor. 1