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.