Draft

** 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].

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

- Introduction
- Basic Forbidden Configurations and Elementary Devices
- The Turing Machine Emulator
- The Planar Crossover Construction
- Summary
- References
- About this document ...

Thu Apr 3 11:48:56 MST 1997