I've often wondered if you could create the grid by some method (brute force, trial-and-error) then overlay a mask from some other puzzle (or randomly pick X% of squares), then adapt one of the 'solver' algorithms to determine it's solvability.

For example, if the solver ony ever uses just a basic single-link solution, then you call it 'basic' and store it someplace. Next if it uses only a few two-link lookups, call it 'easy', and so on. Basically once you have a puzzle, the solver is used to categorise it.

Of course this doesn't really answer how to generate a 'simple' vs 'difficult' puzzle on the fly, but it would give you a method to provide pre-set puzzles ... and it gives a way to categorize them without human intervention.