# Random generation of interesting puzzle levels?

I'm making a Sokoban-like game i.e. there's a grid that has some crates on it you can push and you have to get the crates on crosses to win the level (although I'm going to add some extra elements to it). Are there any general algorithms or reading material I can look at for how I could go about generating interesting (as in, not trivial to solve) levels for this style of game? I'm aware that random level generators exist for Sokoban but I'm having trouble finding the algorithm descriptions.

I'm interested in making a game where the machine can generate lots of levels for me, sorted by difficulty. I'm even willing to constrain the rules of the game to make the level generation easier (e.g. I'll probably limit the grid size to about 7x7). I suspect there are some general ways to do level generation here as I've seen e.g. Traffic Jam-like games (where you have to move blocks around the free some block) with 1000s of levels where each one has a unique solution.

One idea I had was to generate a random map in its final state (i.e. where all crates are on top of their crosses) and then the computer would pull (instead of push) these crates around to create a level. The nice property here is that we know the level is solvable. However, I'd need some heuristics to ensure the level was interesting.

• That idea you have for generating levels is very interesting. Honestly I'd just go ahead and try that, rather than waiting for discussion about it. I'm guessing you could tune the difficulty of the generated levels by setting the number of pulls, and one heuristic you'd probably want is to distribute the pulls over multiple crates, both so that every crate is moved a fair amount, but also so that the player sometimes has to go back and forth between crates (I'm guessing that sort of intertwining logic is more interesting than one-crate-at-a-time). Commented Sep 24, 2014 at 13:31