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
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2020 at 6:31 | comment | added | Per Alexandersson | Instead of BFS, one can use A*, which is like BFS, but with a heuristic. One can certainly cook up some reasonable heuristics for this game (number of chips in final position, etc) | |
| Feb 19, 2013 at 21:27 | answer | added | Günter Rote | timeline score: 1 | |
| Feb 17, 2013 at 8:01 | answer | added | Roland Bacher | timeline score: 1 | |
| Feb 16, 2013 at 10:44 | history | edited | Alexander Chervov | CC BY-SA 3.0 |
added 48 characters in body
|
| Feb 16, 2013 at 10:29 | history | edited | Alexander Chervov | CC BY-SA 3.0 |
added 329 characters in body; edited tags; edited title
|
| Feb 15, 2013 at 20:46 | answer | added | Günter Rote | timeline score: 6 | |
| Feb 15, 2013 at 13:24 | answer | added | Dima Pasechnik | timeline score: 1 | |
| Feb 15, 2013 at 11:56 | answer | added | Dima Pasechnik | timeline score: 3 | |
| Feb 15, 2013 at 11:29 | history | edited | Gerry Myerson | CC BY-SA 3.0 |
vertexes -> vertices
|
| Feb 15, 2013 at 9:45 | comment | added | Alexander Chervov | It seems alternative strategy to be "deapth-first" - e.g. determine whether "chipN" can be moved to position "FinalN", if NOT - then problem solved - answer is NO. If yes we need to search for solution which will satisfy CONTSTRAINT say for pairs of "chips", then for triples of "chips" and so on... However it is not clear for me how to do this... and whether we will get some significant complexity gain at least on some "random" graphs ? | |
| Feb 15, 2013 at 9:41 | comment | added | Alexander Chervov | @Dima thank you for the comments ! You are welcome to edit the question. | |
| Feb 15, 2013 at 8:38 | comment | added | Dima Pasechnik | yes, chip="фишка" | |
| Feb 15, 2013 at 8:32 | comment | added | Alexander Chervov | @Dima do you mean the name "chip" is better than "marker" ? (по русски "фишки" стоят в вершинах - what should be translation of "фишка" ? "chip" ? | |
| Feb 15, 2013 at 8:30 | comment | added | Dima Pasechnik | It seems to be a computationally hard problem, in the sense that every algorithm will need time exponential in $m$. | |
| Feb 15, 2013 at 8:26 | comment | added | Dima Pasechnik | IMHO it's better to formulate this in terms of $m$ chips placed on nodes of your digraph $G$, at most one chip on a node, and each move in this game, with the goal is to place chips on a fixed subset of "final" nodes, is to move a chip on a node $v$ to the other end $u$ of an arc $vu$, without violating the condition that there is at most one chip on a node. | |
| Feb 15, 2013 at 8:02 | comment | added | Alexander Chervov | One "MOVE" - moves ONLY ONE marker. Is the description clear now ? @Dima Thank you for you comment ! | |
| Feb 15, 2013 at 7:56 | comment | added | Dima Pasechnik | it's not clear what are moves allowed. Are you moving the 'init_j' vertices at the same time? By the way, "wave algorithm" seems to be what is called "breadth-first search" in English. | |
| Feb 15, 2013 at 7:03 | history | asked | Alexander Chervov | CC BY-SA 3.0 |