Usage
  • 73 views
  • 77 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
  • DOI
    https://doi.org/10.7939/R3JM23K33
  • License
    Attribution 3.0 International