A Solver for Puzzle Quest and Aurora Feint

Puzzle Quest and Aurora Feint are two very similar games. In both, you have to match three or more square blocks with the same color horizontally or vertically by exchanging two neighboring blocks. Those matched blocks are then eliminated from the board and the blocks above them fall down to take their place. Both games have special pre-built maps which challenge the player to clear all blocks. In Puzzle Quest the difficulty is that only moves which result in matched blocks are permitted, whereas Aurora Feint requires that the challenge be completed with a certain number of moves or less.

Being too lazy to think for myself I wrote a program to solve those maps for me. I have set up a public Mercurial repository for it at http://hg.13thfloor.at/hg/puzzlequest/.

Here’s how to solve an Aurora Feint puzzle with a maximum of two moves:

$ ./puzzlequest -a -d2 <af-puzzles/fall_rain.2
. . . . . .
. . . . . .
. . . . . .
. . . g . .
. . b g . .
. g b b . .
 
2,1 -> 3,1
 
. . . . . .
. . . . . .
. . . . . .
. . . g . .
. . g b . .
. g b b . .
 
3,0 -> 4,0
 
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

Coordinates are given in the form column,row, with the lower left block as the origin (0,0).

The program is written in Haskell. It’s only my second program written in that language, and it shows: it’s neither elegant nor efficient. My first Haskell program was an interpreter of a small subset of Scheme, which I’ve made a point of implementing as the first thing in any new programming language I learn, a practice I can highly recommend. Here are interpreters I’ve written in Forth and O’Caml.

3 thoughts on “A Solver for Puzzle Quest and Aurora Feint

  1. Hey Schani! I’m one of the developers of Aurora Feint. I gotta say, this is pretty slick. I was just checking out the Haskell source — it’s pretty nutty. Good job with it though!

    Have you played Aurora Feint II: Tower Puzzles? It’s a whole game with just these kinds of puzzles that we launched earlier this week. I wonder if your solver will work on the last puzzle… ;)

    Happy Holidays
    – Jason

  2. Hey Jason!

    Thanks for checking it out! No, I wasn’t aware of Tower Puzzles, but rest assured that I’ll give it a try as soon as possible. In fact, it’s downloading right now :-)

    Mark

  3. Hello Mark,
    From the repository it looks like this was last updated 2 months ago. Even so, if you have a moment to send me an email, I’d love to hear the general flow and what kind of optimizations you put into it. I checked the Haskell code but couldn’t make out even the general flow of the program :/ Sorry for my lame text based programming skills. I’m programming in LabVIEW.

    Background: I’ve made a solver that works in-game and in realtime by taking a screenshot, converting it to a board, solving the board, and speaking the results. It has a mode for opponents and one for alone types (like capture as you have done). The solver works very quickly for opponent mode, even checking against the opponents next possible moves. However, the alone mode generates so many results with my method that it just takes FOREVER.

    In case you prefer to see what I’ve done first, this is the general flow for alone mode:

    *Generate all meaningful swaps for a given board
    *Queue them up for processing
    *Execute the boards as the game would
    *Only for meaningful results:
    –add them to a results tree
    –queue them up for further processing (FILO to get depth first behavior)
    *Repeat
    *Analyze all the tree’s leaves to find the best path (it short-circuits if it finds an empty board)

    Various optimizations are in there, but the biggest one is searching the existing results to make sure only unique results are added to the tree. With that optimization or without it, I’ve never seen my program end on one of the capture boards :) although it does work on a test board.

Comments are closed.