News for hackers. Stuff that matters.
Re:Game about squares by thomasahle on Sunday July 27, 2014 @11:59AM (#8093080)
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.

Re:Game about squares by Strilanc on Sunday July 27, 2014 @01:33PM (#8093357)
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.

Re:Game about squares by Zimmux on Sunday July 27, 2014 @04:40PM (#8093901)
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

Re:Game about squares by Hello71 on Sunday July 27, 2014 @05:22PM (#8094016)
not quite right; some levels like 18 have loops, so some paths have no end state.
Re:Game about squares by Zimmux on Sunday July 27, 2014 @06:21PM (#8094181)
Should be fixed now.
Re:Game about squares by zwegner on Sunday July 27, 2014 @02:01PM (#8093432)
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).