How do I find out if this particular puzzle can still be solved?

Question

A while ago, I made a simple game that involved swapping birds to combine them and release them to create points. The idea is that eventually, the birds would get stuck and your game is over, but I found it tremendously hard to think of a way to detect a game-over, so I published it without such an algorithm and just hoped people would see it for themselves. However, I'm still very interested in a solution and hoped someone could help me.

The game works as follows:

• 6 different kinds of birds are distributed over an n x n (usually 4 x 4) grid.

• For every two birds of the same type, if they would form a perfect rectangle together, they merge into one bigger bird of the same type. This means you can have birds that are, for example, 4 x 1 or 3 x 2.

• Birds that are big enough can be removed from the grid, generating points. What's 'big enough' depends on the type of bird, some only need to cover 1 square on the grid, others 2 or 3.

• Empty squares on the grid will get filled up with new, random birds falling from above. That is, of course, as long as other birds don't block the way. All birds always fall down when they can, and moving a bird upwards is therefore impossible (though, swapping upwards is allowed).

• Two birds can swap places if they are of the same width when swapping vertically, or of the same height when swapping horizontally, but only when they are aligned perfectly. A bird can always move to an empty spot, given that its new position would be large enough to contain it and that the new spot wouldn't deny gravity.

• Eventually, groups of 2 tall/wide birds will prevent anymore progress. Some birds can still be swapped, and maybe some would even become big enough to be removed when combined with certain others, but they will never get near each other, resulting in a game over.

I'm not too sure whether this is clear enough. I don't really want to post a link to the game here because I'm really only interested in the algorithm, not new downloads. Also I'm not too sure if I'm allowed to, as it could be seen as an advertisement. But please request more clarity where needed!

Answer 1

I think starting from a brute force solution is fine here, as the search space is relatively small.

At the start of every turn, recursively look at all the moves that can be made, storing the layouts that you've looked at already to avoid repeating yourself. If you can find a series of moves that lead to merging birds, in a reasonable time, stop; the puzzle isn't stuck yet.

For example, given this example grid:

+-+---+
|A| B |
+-+---+
|B|A|B|
+-+-+-+

We could swap the birds on the top row:

                 v v
+-+---+       +---+-+
|A| B |       | B |A|
+-+---+  -->  +-+-+-+
|B|A|B|       |B|A|B|
+-+-+-+       +-+-+-+

Next, we don't swap the top row again because that would repeat the first grid. Instead, we could swap the last column:

                 v v
+-+---+       +---+-+       +---+-+
|A| B |       | B |A|       | B |B|<
+-+---+  -->  +-+-+-+  -->  +-+-+-+
|B|A|B|       |B|A|B|       |B|A|A|<
+-+-+-+       +-+-+-+       +-+-+-+

...which results in pairs of birds that can be merged:

                 v v                         v
+-+---+       +---+-+       +---+-+       +-----+
|A| B |       | B |A|       | B |B|<      |  B  |
+-+---+  -->  +-+-+-+  -->  +-+-+-+  -->  +-+---+
|B|A|B|       |B|A|B|       |B|A|A|<      |B| A |
+-+-+-+       +-+-+-+       +-+-+-+       +-+---+
                                              ^

And we're done.

If we've exhausted the search space without finding pairs that can be merged, the game is stuck. It's also possible that we can't find a result in a reasonable amount of time, but this is very unlikely given the limited bird types (6) and grid size (4x4 and larger). You could add a heuristic to improve your search strategy, favouring moves that bring similar bird types closer together, if the search is too slow.

This is not a perfect solution, as it's possible that despite there being merges available, the game will eventually get stuck anyway. I don't think you'll need such a good solver though; most puzzle games make do with a simple no-moves-available-now simple solver like this one.