Some Basic Analysis of Bejeweled Blitz (or How To Think Too Much About A Flash Game)

So I've been playing a lot of this game called Bejeweled Blitz lately. It's a pretty simple but addicting flash game, that looks like this:

You can click on adjacent gems to switch them, so long as you end up with a set of three gems of the same color in a row. For example, look at yellow diamond four from the bottom and two from the right. You could swap it with the brown gem below it to make a line of three yellows, but not with the purple triangle to the right, because that wouldn't make any sets of three. After you do that, the three (or more) same-colored gems that you've lined up will disappear, and the remaining gems will fall into the empty space they leave, with new gems coming in from the top so that there's always a full grid.

Now, I first played this game years ago, in a version with no time limit. You just made match after match, and when there were no possible moves left, you lost. This newer version that I'm playing now uses the same gameplay, but now you have one minute to make as many matches as you can, and interestingly, it never gets stuck. Obviously the computer is being intelligent about new gems it drops in from the top, so that you always have a move available, but is that always possible? I decided to fiddle around and see if I could prove anything about it.

For simplicity's sake, let's start by thinking about what happens when you line up just three gems (it turns out that the case of four or five ends up being solved when you solve the three case, but that's I'm getting ahead of myself), and let's line them up horizontally. So, someone has just lined up three similar gems in a horizontal line, they've disappeared, and the existing gems have all fallen down to fill the space. Let's also assume that that didn't cause any additional matches to be made, so now we've got three blank spots at the top waiting to be filled in by the computer, looking like this (where the letters represent gems):

We're only considering a small slice of the board because it's all that matters, new pieces in one part of the board can only influence so much of the board. Now, we could have the computer do something obvious, like drop in 3 of the same gem, but that leaves us in the same place we started, so it should be our goal to cause some change in the rest of the board. Well, there's one simple option that's always available to us:

The X is irrelevant, the point is that we can now swap the black A and B to give us this board

where the computer has to once again place three new gems. However, even before that step, we've opened up a number of new possibilities. I've marked the B and X in blue because they're in new places, and can now influence more of the board. If there are more gems to the left of this view, we might be able to make a match with that B that we couldn't make before, and it's possible that, e.g., X, J, and Q are all the same and we can now make a match there.

Now, that's all well and good for the top row, but there are enough different gems in Bejeweled Blitz (7 total) that we can make a pattern like this where there's no easy way to make any change in the second row down:

However, even then you can always make some clever choices to make some changes in the lower rows.

In fact, all of X, Y, alpha, beta, and gamma (sorry, I was running out of letters) can be whatever gems you like, so you can pick them in order to maximize the number of potential moves you get as a result. No matter how antagonistically we try to arrange the board, it's always possible for the computer to pick the new gems wisely enough to "unstick" the board.

Now, let's start tackling all those assumptions I made earlier and see what kind of general result we can get out of this. First off, some nice symmetry means that pretty much all the stuff we just did with horizontal sets of three also applies to veretical sets of three. Even better, we don't need to worry at all about what happens when you clear a set of four or five, or a stranger shape by getting a long string of completions from just one move. Think about it this way - any clearing you do, no matter how complex, has to have a row or column of three in it somewhere. If you clear four in a row, that's really three in a row plus one on the end. If you get five in an L shape, that's really two (overlapping) sets of three. Thus, any case we try ends up reducing to the one we just solved, with the addition of some free extra gems that we get to make whatever we want.

Of course, that's not all there is to say about this topic. You could probably do some interesting research into the most efficient way to open up the board given a situation like this. For example, in the second picture in my last example, I could also have swapped the E and B to the left of the red B; if you follow that choice through, you end up in the same position I ended in with the five arbitrary gems, but the B and E are switched. Depending on what exists outside of this small slice of the game board, switching that B and E might end up being a good idea, or it might not. How can you tell?

These are the kind of questions I ask myself when I'm bored, but I've satisfied my boredom for now by answering my initial question. I started learning some interesting things while making these graphics in Mathematica, though, so maybe I'll make some code to mess around with this later.