This project of mine attempts to solve the game of sokoban. Here is an abstract:
Sokoban is a popular puzzle game implemented on almost all computer system. It is a true part of computer gaming folklore. The aim of the game is to move a person (Jap. Sokoban = pusher) around in a two-dimensional maze and to move a number of boxes into some designated storage positions. The pusher may only push one box at a time and he cannot drag boxes. If he manages to move each box to a target position (any box can move to any storage location) the game is solved. The main problem in solving a game is that wrong moves may place boxes in unrecoverable positions, eg. into a corner of the maze. The player then cannot move the box any further, because he cannot reach a position from where he can push the box. Since the player may only move one box at a time, boxes can also block each other, therefore the player has to consider the order in which he pushes the blocks.
It has been shown that solving arbitrary puzzles is a PSPACE--complete problem. Basically, it is possible to construct Sokoban puzzles that can simulate the execution of arbitrary Turing machines with finite tapes. Nevertheless, this construction yields enormously large and complex mazes, much unlike the relatively simple mazes that are used for play. So there is still hope for humble attempts to solve the game instead of the problem.
Download the complete paper here, either in dvi or in postscript format. A HTMLified version, hopefully, will come up soon.
Finally, the sources. Be warned, they are somwhat ... untidy. You need Sicstus prolog to run them, and you better try this on a unix system. However, the sokoban-playing mode for emacs alone make them worth downloading!