ERA is in the process of being migrated to Scholaris, a Canadian shared institutional repository service (https://scholaris.ca). Deposits to existing ERA collections are frozen until migration is complete. Please contact erahelp@ualberta.ca for further assistance
- 1712 views
- 1239 downloads
Sokoban is PSPACE-complete
-
- Author(s) / Creator(s)
-
Technical report TR97-02. 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 θ (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. | TRID-ID TR97-02
-
- Date created
- 1997
-
- Subjects / Keywords
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International