next up previous
Next: Introduction

Sokoban is PSPACE-complete
Draft

Joseph Culberson
University of Alberta

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 tex2html_wrap_inline722 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, solving the open problem stated in [1].



This paper is also available in postscript (417K).



& Culberson
Thu Apr 3 11:48:56 MST 1997