Joseph Culberson
University of Alberta
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 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].