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.

Answer 4

I've just check out about five different versions of the game on Ubuntu and I've found an answer you can pillage from!

Simon Tatham's Portable Puzzle Collection

I play about five of his games incessantly but preferred Same GNOME. I just loaded up his Same Game and it has the option to ensure solubility when creating custom games. Even has a customisable scoring system. It's all awfully advanced.

An exe and source code is available from the above link.

And the license is MIT (meaning you can use it freely in commercial games - but please donate something to him if you can afford it)

Answer 5

I think the best way is, if you generate a level randomly, I mean add 1 or more blocks at the same time to the same column, so you're gonna have some connecting blocks. Then you write a simple solving algorithm, which just solves the board till there is no more possible moves. Then you just simply try to complete the remaining part, just pushing some blocks from the top so that you have some more blocks to vanish. You continue till you finish the board. You store the pieces you added in another matrix. After that you just have to add the 2nd matrix to the 1st from the top. If the board is not full, you simply complete the board with blocks to start with(connecting blocks).