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 .

Abstract We determine that the connectivity and the edge‐connectivity of the Cartesian product G1 × G2 of two strongly connected and finite digraphs G1 and G2 are equal to min{n1κ2,n2κ1,δ + δ , δ + δ } and min{n1λ2,n2λ1, δ + δ , δ + δ }, respectively, where ni, κi, λi, δ , δ are the order, the connectivity, the edge‐connectivity, the minimum out‐degree and the minimum in‐degree of Gi, respectively, for i = 1, 2. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008