4 ms·

Any solution is on the form 12232322... where the number expresses what square to click. It's pretty easy to brute force the game from there. Sure, you can use

Any solution is on the form 12232322... where the number expresses what square to click. It's pretty easy to brute force the game from there. Sure, you can use tree search and prune the search a bit, but it's still brute force and may take exponential time for tough levels. You can also look into some of the research that has been done on Sokoban AI's.

Strilanc 12y ago
There's no need to search all move sequences, because so many of them end up in the same game state (a game state is a combination of positions and orientations of arrows, with a cut off on positions because far away ones because don't affect whether there's a solution or not). Of the levels I saw (up to 31), the relevant board area was never more than 20x20 and there were never more than 4 arrows. So the state space had size 16(2020 choose 4) ~= 17 billion. Of course most of those states won't be reachable from the starting state... so the actual number of states you need to explore is probably more like a million or even a thousand. I think a program could solve all of the game's puzzles in under a second.
- zwegner 12y ago
  Shouldn't that 16 be a 256? 4 squares with 4 orientations each = 4^4 = 256. But yeah, definitely pretty doable with a brute-force memoized search. I imagine a lot of state space could be pruned by doing some analysis of when squares can only move further away from their home dots (and not be turned around or pushed back or anything).
- Zimmux 12y ago
  I've written a solver that does exactly that here, it prunes positions whose blocks are too far outside the bounding rectangle: https://gist.github.com/Zimmux/c0fdb3ddad654b6b0ae2 https://gist.github.com/Zimmux/c0fdb3ddad654b6b0ae2
  - Hello71 12y ago
    not quite right; some levels like 18 have loops, so some paths have no end state.
    - Zimmux 12y ago
      Should be fixed now.

Strilanc 12y ago

There's no need to search all move sequences, because so many of them end up in the same game state (a game state is a combination of positions and orientations of arrows, with a cut off on positions because far away ones because don't affect whether there's a solution or not). Of the levels I saw (up to 31), the relevant board area was never more than 20x20 and there were never more than 4 arrows. So the state space had size 16(2020 choose 4) ~= 17 billion. Of course most of those states won't be reachable from the starting state... so the actual number of states you need to explore is probably more like a million or even a thousand. I think a program could solve all of the game's puzzles in under a second.

zwegner 12y ago
Shouldn't that 16 be a 256? 4 squares with 4 orientations each = 4^4 = 256. But yeah, definitely pretty doable with a brute-force memoized search. I imagine a lot of state space could be pruned by doing some analysis of when squares can only move further away from their home dots (and not be turned around or pushed back or anything).
Zimmux 12y ago
I've written a solver that does exactly that here, it prunes positions whose blocks are too far outside the bounding rectangle: https://gist.github.com/Zimmux/c0fdb3ddad654b6b0ae2 https://gist.github.com/Zimmux/c0fdb3ddad654b6b0ae2
- Hello71 12y ago
  not quite right; some levels like 18 have loops, so some paths have no end state.
  - Zimmux 12y ago
    Should be fixed now.