Randomly generating levels for Sokoban game?

I'm making a Sokoban style game (i.e. it's not exactly the same as Sokoban so I can't use existing levels) and would like to create random levels on it so a player could keep playing it and always have levels to try. Are there any ways I can get the computer to generate levels for me automatically or semi-automatically (by semi, I mean I could give it the initial map perhaps but without the crate positions)?

One idea开发者_如何转开发 I had was to randomly generate a map, place the crates in their finishing state (i.e. on the crosses) and then randomly move the crates as if they were being pulled by the game character. This guarantees me that the level should be solvable. However, the main problem would be how to know if the level is easy/hard and interesting/boring? For example, Sokoban is NP-hard so I couldn't realistically ask the machine to then check if there was an easy solution.

I know it would be hard to create random levels that would compete with human experts but I'm just looking for something that is decent.

Edit: By the way, I would be more interested in generating small but interesting Sokoban-like levels e.g. 5x5 levels instead of 50x50 levels. This may make things more computationally feasible.

This site has a number of Sokoban level generators: http://www.erimsever.com/sokoban7.htm

You may find it useful to look at how they work.