Sokoban is PSPACE-complete

• Author(s) / Creator(s)

  • Culberson, Joseph

• 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

  • Sokoban
  • Turing Machine
  • Linear bounded automata
  • PSPACE

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3JM23K33

• License

  Attribution 3.0 International