Timeline for Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
Current License: CC BY-SA 3.0
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 |