Sokoban is PSPACE-complete

Joseph C. Culberson

University of Alberta Technical Report TR97-02 1996

Abstract

It is shown that the popular puzzle Sokoban can be used to emulate a linear bounded automata (finite tape Turing Machine (TM)). In particular, a construction is given that has a solution if and only if the corresponding Turing Machine on its input halts in the accept state. Further, if the TM halts and accepts, then the pusher will make $\Theta(n+t(n))$ moves and pushes, where $n$ is the number of symbols on the input tape, and $t(n)$ is the number of transitions made by the TM during its computation. This construction shows that the puzzles are PSPACE-complete.

Paper available here (postscript)

Also available via ftp ftp://ftp.cs.ualberta.ca/pub/TechReports/1997/TR97-02/
or here:
as html.

joe@cs.ualberta.ca