Is puzzle solver a must for random level generation?

[acme_pjz]

I had cloned a puzzle game http://code.google.com/p/turningpolyhedron and wrote a puzzle solver and a random level generator. The random level generator first create a bunch of complete random levels, then run genetic algorithm on them. Each time the generator runs solver on them to calculate fitness function, then choose some best levels to mutate and reproduce.

It works not bad, but when adding new puzzle elements to the game mechanics, the solver get slower and slower, due to expanded possible game states. Moreover, the possible level elements combination is also grow up, so the random level generator is very slow and couldn't produce good results.

My question: Is puzzle solver a must for random level generation in puzzle games? Are there any other ways/algorithms to generate random level? And what do you think about random level generation in puzzle game? Suggestions are welcome

[andrewj]

Naturally a random level generator needs to create levels which are solvable (unless you have a game where the user expects some combinations to be unsolvable -- e.g. various solitaire games).

Your approach seems to be: first generate something, then test if it is solvable. And you've discovered that such an approach doesn't scale as the game gets more and more complex.

So you should be looking at finding generating algorithms where you always get solvable puzzles, i.e. the way the algorithm works guarantees solvability. One way to do this is a function which takes a puzzle you know is solvable, and modifies or extends it in a way that keeps the result solvable, and repeat this process many times.

I think random generation can add a lot to a game, but if the game has many users willing to make levels then it is not so important.

[dusted]

I agree with andrewj,

It would be better to have a generator that is unable to generate unsolvable levels by algorithm, not by chance.

I do not think a solver is necessary, but it is indeed a nice feature, and it could be used for other things, like detecting if the player have made brought the puzzle into an unsolvable state, or to (very naively) quantify the difficulty of a given puzzle or (if the solver is well made), provide the player with "best possible solution" information or use it for a "I'm stuck here, give me a hint!" function.

I wanted to write a solver for Wizznic, but I deem the task too complex now, as it would have to take into consideration movement, teleporting, transportation, boolean logic tricks and switches =(