Randomly generates levels for the game Sokoban?

Question

I am making a game in the Sokoban style (i.e. it is not quite the same as Sokoban, so I cannot use the existing levels) and would like to create random levels on it so that the player can continue to play and always have levels to try. Are there any ways to make the computer generate levels for me automatically or semi-automatically (by gender, I mean that I could give it the original map, perhaps, but without the box positions)?

One of my ideas was to randomly create a map, place the boxes in their final state (i.e. on crosses), and then randomly move the boxes as if they were being pulled by a game character. This ensures that the level must be solvable. However, the main problem is how to find out if the level is easy / difficult, interesting / boring? For example, Sokoban NP-hard, so I could not realistically ask the car to check if there was a simple solution.

I know that it would be difficult to create random levels that could compete with human experts, but I'm just looking for something worthy.

Edit: By the way, I would be more interested in creating small, but interesting Sokoban-like levels, for example. 5x5 instead of 50x50 levels. This can make things more computationally possible.

Answer 1

There are several Sokoban level generators on this site: http://www.erimsever.com/sokoban7.htm

You might find it helpful to see how they work.