How to build a solvable level of Same Game (aka. Chain-Shot, aka. Clickomania)

Question

I'm building a game such as Same Game, when I have to create a new level I've just run an algorithm to fill the board with N colors, this algorithm fills the board at random, but obviously the levels generated this way are not all has a solution.

I have to make a function to resolve this problem, so the game can be played by a perfect player for ever.

I have a maximum of 6 color and a minimum of 2 and the board has a reasonable size (14x12) but can be modified.

The language is irrelevant.

EDIT: I don't need to solve the puzzle, I need to create levels that has at least one solution.

Answer 1

One method, which, I'll add, is rarely the most efficient, is to build the level in reverse.

It's fairly simple to do in this case though. You just start with nothing and add clickable groups with some randomness... I say some randomness, as you may need to add extra blocks to make sure all columns are filled.

But thinking about it, even then there's a possibility two clickable groups you add will touch each other and cause an unforeseen collapse, resulting in an unfinishable game. So this method wouldn't guarantee a solvable game.

You could have a look at the source for an open source version like Same GNOME and see how they do it (if they do it at all!)

Answer 2

create a "solved" board, and then change it using N valid but random backwards moves. After adding each backward move, you could run the moves forward (on a temp board) to verify a solvable puzzle.

Answer 3

If you can't run a verification algorithm, because of time constraints, perhaps what you need to work with is a library of puzzles. You can have a background thread generating new random puzzles all the time, and running a verification algorithm on them to check if they are valid. When a valid puzzle is found, it is added to your library of puzzles (assuming the same puzzle doesn't already exist).

Then your game just loads randomly from the library. This allows you to ensure you always have valid puzzles, but still allows you to randomly generate them and verify them without slowing down the puzzle-loading.