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.

https://authors.elsevier.com/a/1U~4b15DaHuwaY

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

< >