Detecting possible moves in a swap-match game

Question

I've been coming up with ideas for how I would go about programming a Bejeweled-like minigame. After some deep thought, I've managed to figure out how to detect matches (including special bonus cases like 4 in a row, 5 in a row, intersections...) without any real issue.

However, one major issue I'm struggling with is this: how do I detect possible moves, and influence the dispensing of new tiles in light of them?

Specifically, I need to be able to:

• Detect that there are no moves possible on the board

A legal move consists swapping two adjacent tiles in order to create a match of at least three in a row.

• Ensure that there are no moves on the starting board layout

This could be a simple case of "generate a board, check if there are any matches, try again until there aren't" but this seems messy.

• Ensure that there is at least one valid move on the starting board

Again, can be achieved by generating boards until true, but anything with more finesse than brute force would be nice.

• Optionally (based on game mode) ensure that tiles fall such that there is always at least one valid move on the board.

Once again, brute force simply says "pick some tiles to drop in, check there's a valid move, if there isn't then drop some different ones in until there is".

Ultimately almost all of these can be done through brute force, but I'm sure there must be a better way. At the core, however, I really need help with figuring out how to detect potential moves on the board...

Answer 1

Even though I think your best bet is to brute force it, I have a suggestion for another way to get this done. Keep in mind that this is purely speculative, I have not tried it.

Considering that each turn looks like this:

1. Player swaps two gems, forming a match
2. The matched gems are removed from the board, revealing a gap
3. The gems above the gap fall to fill it, revealing another gap on the top
4. Gem appear from the top to fill the top gap
5. IF there are new matches on the board GOTO 2

I think that it is possible to work in reverse to create a board where specific matches are possible:

1. Generate a board where there are no current matches
2. Pick a match "signature" (eg 3-in-a-row)
3. Pick a random space for that match
4. Move all gems above that space upwards to create a gap for that match
5. Place gems from a single color into that gap
6. Swap one of the newly placed gems so that there is no current match
7. GOTO 2

By taking care to not accidentaly create more matches than the ones you insert and by adding variety with combos and different signatures, you can create a level for someone to play.

Pros:

• Level can be customized based on difficulty factors
• Levels are always solvable

Cons:

• You need to know in advance the number of steps/moves to generate
• There will always be only one possible move

In short, by brute forcing it, you create levels with a wide possibility space while by designing it from the finish to start, you create levels with a linear progression.