3 ms·
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
by 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 agoShouldn'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 agoI'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