In between beach trips and bike rides, I whiled away more than a few summer hours on puzzles I found in the various AirBNBs we rented. Returning home, I rediscovered a sliding tile puzzle with a twist called Asteroid Escape, where embedded asteroids prevent certain tiles sliding past each other in certain configurations.
With 60 challenges from Starter to Wizard level, I was musing about generating the catalogue of challenges automatically. I’ve enjoyed automating puzzle solutions since brute-forcing Instant Insanity with BASIC in my teens (the code is long lost). While Starter puzzles may only require 6 moves, Wizard may require as many as 109 moves. I decided I would particularly enjoy avoiding the gentle frustration of manually solving so many variants of Asteroid Escape if I were to use an automated solver.
I built a solver in Python with numpy for working with grids of numbers. If automating puzzles is your thing too, check out the source code and read on for a summary of the approach. To execute the proposed solution, I printed out the moves and crossed them off with a pencil as I made them. There’s a lot that could be more elegant or efficient, but it gets the job done!
Solver evolution
Define a simple sliding tile board. Elements of a 2D array hold the indexes of the tile pieces at each location (numbered 1..8 for a 3×3 board). The tiles can be reordered through a sequence of moves of the “hole”, that is the space with no tile (numbered 0). The available moves depend on the hole location – four options from the centre but only two from the corners.
Solve the board. Find sequences of moves of the hole that reconfigure the board into a target arrangement of tiles. This I treated as a queue-based breadth-first graph search, with arrangements of pieces being the nodes of a graph, and moves being the edges. However the specific constraints of Asteroid Escape aren’t captured at this point; all tiles are interchangeable in their movements.
Model the blockers that prevent certain tile arrangements. I quickly realised I would miss edge cases if I tried to list permitted arrangements of tiles, and instead defined the “blockers” on each piece with reference to a 4×4 grid. The grid had one cell margin around the outside of the piece to model projecting outer blockers, and 4 positions inside the piece that could carry blockers. A grid cell would be assigned 1 if there was a blocker or 0 otherwise. For a proposed board arrangement, the piece grids could be offset to their location and superposed onto a larger 8×8 board grid by adding piece cell values. A resultant value greater than 1 would mean that two or more blockers were interfering, so the board arrangement was not actually possible.
Solve the board while respecting blocked arrangements. The breath-first search identifies the neighbours – reachable in one move – from each arrangement of pieces. Any neighbours that would result in interfering blockers are now excluded from the search. The target state also only requires that the spacecraft piece should be in the exit position. Both of these constraints were captured as functions passed to the solver. This worked well for a Starter puzzle I tested, but failed on a Wizard puzzle, because it failed to capture piece interference that only occurs when moving pieces.
Model the blockers that prevent certain tile moves. In particular, the nose of the spacecraft doesn’t interfere with the protruding corner blocker on one asteroid tile in static arrangements, but there are scenarios where the tiles can’t be moved past on another. To model this, I increased the piece grid to 5×5 (now 9 interior positions) to capture the previously ignored spacecraft nose, and when assessing a move, I shifted the tile by one grid cell at a time so that each move assessed interference at start and end, and two intermediate positions.
Solve the board while respecting blocked arrangements and blocked moves. Update the neighbour search to exclude moves to neighbours that would result in blocker interference during the move. Update the target state to avoid any interference in sliding the spacecraft off the board.
Of course, the solver didn’t go off without a hitch when I tried it in the real world. I failed to specify a clear exit was required at first, and failed to specify it properly the second time, but third time was a charm (as above).
Conclusion
From a cursory inspection, the Wizard level 60 solution in the notebook and animated above looks the same as the solution provided with the puzzle (so I didn’t really need a solver at all!) However, this solver can also find multiple other (longer) solutions to each challenge. It could also be used to generate and solve more variants at each level of difficulty, extending the catalogue of puzzles. Improvements can wait, however, as it’s time to enjoy the bike or the beach once more.