Hacker News Reader

Comment by tobias2014 | Hacker News Reader

tobias2014

It should be possible to write a solver for this with a "decision tree". There are decisions where the blocks run out of the screen - you ignore these. You only take into account "sensible" decisions (this has to be formalized). When there are multiple possible "sensible" decisions you branch. One decision consists of an action "click x times on block X and y times on block Y …"

View on HN

Should be far easier to create a heuristic search solution. Very naively you could probably get good results by exploring nodes in order by sum of distances from blocks to colour points if blocks could move in any direction. You'll eliminate most of the move away and out of screen behaviours naturally and by preventing the exploration of a previously explored state. You could explore better heuristics but given that the branching factor is only n where n is the number of blocks, most puzzles are solved in under 50 moves and most solutions get pruned quickly both position duplication or bad solutions quickly mangling the heuristic. The hard problems for this program are ones where you have to make a whole sequences of moves away from the objective in order to get a key directional move that accomplishes it.

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.

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.

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).

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

not quite right; some levels like 18 have loops, so some paths have no end state.

Should be fixed now.

Reply on news.ycombinator.com