Home | SokoPlayer HTML5 | Competition | Level List | Post a Level | Forum | Log in or Register

Topic #54 : The Computational Complexity of a Sokoban Variant

I have just published an academic article on the computational complexity of a Sokoban variant, in the journal Theoretical Computer Science.

The paper can be downloaded for free in the first 50 days from the link below, until June 21, 2017.



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) , 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.

#0 Posted: 2017-05-03 10:39:08 (UTC) by chao

< >