Skip to main content
9 events
when toggle format what by license comment
Feb 19, 2013 at 22:09 comment added Günter Rote SOKOBAN is even PSPACE-complete, see J. Culberson, in: Proc. Int. Conf. on FUN with Algorithms, pp. 76-74, 1999) webdocs.cs.ualberta.ca/~joe/Preprints/Sokoban/index.html
Feb 16, 2013 at 14:52 comment added Dima Pasechnik if the chip $i$ must go the final vertex $v_i$, it's completely different story, for which Gunter's procedure certainly doesn't work.
Feb 16, 2013 at 10:08 comment added Alexander Chervov Thank you very much for your answer ! It is wonderful to know relation with Sokaban ! Still there are some differences 1) Gunter Rote mentioned 2) It implies (but not equivalent) that at least graph for Sokoban should be directed - cause boxes in the corners cannot be pushed (as far as I understand - I also never played it) 3) In Sokoban it seems chips are identical while in my question they are "marked".
Feb 16, 2013 at 9:44 history edited Dima Pasechnik CC BY-SA 3.0
added 58 characters in body
Feb 16, 2013 at 2:58 history edited Dima Pasechnik CC BY-SA 3.0
fixed the 2nd reference
Feb 16, 2013 at 2:37 comment added Dima Pasechnik I'll blame my wife - I never played Sokoban myself ;)
Feb 15, 2013 at 20:46 comment added Sam Hopkins It might also be worth looking for a connection to sandpile models on digraphs, which also involve the movement of chips from node to node.
Feb 15, 2013 at 19:38 comment added Günter Rote I don't think so. In Sokoban, you cannot freely move any chip as you like (as in the Question). You must go there and push from a free square on the opposite side. In the Question, the only constraint is that the chips cover distinct positions. (I am not sure if the question is polynomially solvable.)
Feb 15, 2013 at 13:24 history answered Dima Pasechnik CC BY-SA 3.0