Take the 2-minute tour ×

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.

share|improve this question
add comment

5 Answers

up vote 2 down vote accepted

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)

share|improve this answer
Great! Thanks :) –  Lucas Gabriel Sánchez Jun 10 '09 at 17:34
add comment

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!)

share|improve this answer
The first approach was to build the board backwards as you say, but I have encountered many error on that approach. And the games I've seen just use random (Same GNOME is one of them) –  Lucas Gabriel Sánchez Jun 10 '09 at 15:13
Perhaps having a solvable grid isn't necessarily something you should be aiming for. Same GNOME gives you a bonus for clearing but they also use an exponential scoring scale (eg 2 points for 2 at once, 4 for 3 at once, 8 for 4, 16 for 5, etc). That adds a strategy that the user has to choose: either aim to complete or aim to score high enough to not have to. –  Oli Jun 10 '09 at 15:18
Yes, you're right, but tell that to my boss. :( –  Lucas Gabriel Sánchez Jun 10 '09 at 15:24
Haha! I'd love to. I find finding-the-addictive-factor of games a fascinating subject. There are merits to all methods. Completable games are a nice challenge but so is beating a high-score or a timed-game... The latter two working slightly better in an online world where you're competing against other users. I certainly think you should at least make sure your boss can see the benefits of each approach. –  Oli Jun 10 '09 at 16:03
add comment

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.

share|improve this answer
The algorithm to know if its solvable is not a problem, the problem is to create a puzzle that can be solvable (if I just fill the board at random and run the "verification" algorithm this will take more much time that I wan't to compute) –  Lucas Gabriel Sánchez Jun 10 '09 at 15:16
you don't need to be completely random, be random in a controlled way. when you build the board backwards, randomly decide if the color should match the adjacent left/right/bottom, etc. based on what will work for a solvable game. –  KM. Jun 10 '09 at 15:36
add comment

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.

share|improve this answer
add comment

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).

share|improve this answer
add comment

Your Answer


