Well, land obstacles could be generated first. Then you can start Lolo by the goal, and work your way back from there. Monsters, boulders, and other things of that nature could be added as you backtrack.

Say there is a monster that is generated at a certain location. When it is generated, it is generated at the pass or in the case of the skull the seek state. A boulder or other obstacle such as a frozen enemy must be generated to allow Lolo to pass the creature. Either that, or there must be A way to pass the creature even if it is just distance and the player's ability to cross the creature without getting zapped.

Difficulty could be measured by the amount of successive acts that need to be accomplished in order to do something such as pass a monster.

Several thoughts:

Yes it would be nice if the computer could show how to solve the puzzle - this is actualy simpler than it seems because you dont have to have a perfect solver nor does the solver have to solve every solvable puzzle/map thrown at it. You can reject maps the solver cant solve in a reasonable amount of time and never present those puzzles to the user.

You can then rank the puzzles based on how long it takes your solver to solve it.

Another idea is to do that slow-as-hell perfect solver and only proof them at development time - shipping the seeds that generate the puzzles/maps instead of the actual maps. You could ship thousands of seeds very compactly and distribute new seeds as upgrades.