| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4952095 | Theoretical Computer Science | 2017 | 10 Pages |
Abstract
Sokoban is one of the most studied combinatorial puzzle game in the literature. Its computational complexity was first shown to be PSPACE-complete in 1997. A new proof of this result was obtained by Hearn and Demaine (2005) [8], by introducing the Nondeterministic Constraint Logic (Ncl) problem. Since then, Ncl has been used to prove the PSPACE-completeness of several other puzzles including a few Sokoban variants, by many authors. In this paper, we show that Snowman, a new Sokoban-like puzzle game released in 2015, is PSPACE-complete by reduction from Ncl.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Weihua He, Ziwen Liu, Chao Yang,