Hey.

I was making up my mind about this topic these days. I think you all know the Game Bejeweled or one of its clones. In Bejeweled, you have a squared field, filled with Gems, each one colored in one of 6 or 7 possibilities. The idea is to swap two neighbours and thus reach at least 3 stones in a row, colored the same way, that way the match and new stones come from the top.

I was thinking, that they had to program a smart initializer method, so that the initial field, when created by starting the game, would

a) have not 3 or more matching stones - that way the user would have to be wondering, why anything was going on while he/she hadnt done a thing

b) have at least (!) one possibility of finding a matching triple - otherwise the game would be over.....


I couldnt come up with a method other than brute force:

create a field, put new stone in, give it a color, check that there is no matching, when finished, find a random spot and create a possibility for the user to make a matching.


That can't be the way, can it? I mean, i don't like to solve stuff brute force. I would want some smart, elegant way to initialize the field.

Have you ever tried something like that ?

Greetz.

I guess I wouldn't try to be too smart about it. Fill it with random values. Look for a match, replace one of the matched colors with a different color. Repeat until there are no matches and be done. I would guess that the chances of not having any moves available at the beginning of the game is astronomically small given a random playing field. Otherwise the game would have to make sure that there are lots of matches and to add matchable pieces when inserting replacements.

It's a game of odds and random chances, people like those. I would guess that not all Solitaire games and variants are provably solvable, and people play those all the time.

Another solution, which might or might not be applicable, is to do it backwards. Take a 4x4 sliding puzzle - there are many unsolvable starting positions. (http://en.wikipedia.org/wiki/Fifteen_puzzle#Solvability) The best way to make sure that you find a solvable start is to start with the solved puzzle, and then apply a number of random moves.

In effect, this means that the computer plays the game "backwards" at first, and the player is asked to reverse the sequence of moves.

A Bejeweled version, heck, I don't know. Perhaps start with an empty field, add in three adjacent jewels and then apply 2-3 random moves. Add in another three, jumble the gems a bit, and repeat. After you can't fit in any more "threes", fill the remaining spaces with adjacent colors and jumble them a bit.

This would give a provably solvable starting state, although it would have to be a bit more sophisticated to spit out interesting states...

I like the idea of starting with a solved solution. It gives me the feeling, I have stuff under control. It can always happen that if u gamble around and never do the counter-check, bad situations occur.

In an initial state, a field should be flawless. This cannot be solved without checking for it.

Yeah, "provably solvable" is a mantra that keeps puzzle designers (e.g. me) soundly asleep at night... Let me know how you move forward, I'd be intrigued to hear your solution.

Another example: how I proved Galder instances to be solvable. After trying the above "backwards" approach, I realized that all that I needed to prove was that it was possible to get two of each color into the innermost ring - which I could construct from the get-go. So I put two red, green, blue and black stones into the innermost, shuffled it, and then randomized the rest of the field.

Fenris Wrote:Another solution, which might or might not be applicable, is to do it backwards. Take a 4x4 sliding puzzle - there are many unsolvable starting positions. (http://en.wikipedia.org/wiki/Fifteen_puzzle#Solvability) The best way to make sure that you find a solvable start is to start with the solved puzzle, and then apply a number of random moves.

In effect, this means that the computer plays the game "backwards" at first, and the player is asked to reverse the sequence of moves.

A Bejeweled version, heck, I don't know. Perhaps start with an empty field, add in three adjacent jewels and then apply 2-3 random moves. Add in another three, jumble the gems a bit, and repeat. After you can't fit in any more "threes", fill the remaining spaces with adjacent colors and jumble them a bit.

This would give a provably solvable starting state, although it would have to be a bit more sophisticated to spit out interesting states...

I did this to initialize mahjong solitaire boards. Works great, if your game works this way.

to hear from me. It's just that I need to focus on some other methods first.
So far, I have helped out myself with an algorithm I had in use already.

The field is generated randomly with a different color a piece.
I then brute-force check each tile for being in a match-3 or greater situation - if it is, i change the color to the next one (i.e. add 1, since i reference the colors by numbers).

Thats it, works great, and so far there are nearly no initial match-3 situations (except for rare occurences) and - dont ask me why - but I always had at least 1 , usually averagely 5-6 possible situations to create a match-3.

That sufficed so far, since I just needed this for testing. I guess I'll start working on a better algo next week. I'll update this here.

So long.