Snowman is PSPACE-complete

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.

Authors

• Weihua He
• Ziwen Liu
• Chao Yang School of Computer Science, Hubei University

Keywords

• Combinatorial puzzles
• Computational complexity
• PSPACE-complete
• Sokoban
• Nondeterministic constraint logic