I've found the best way to rate and generate puzzles of a certain perceived difficulty is to have a solver that works the way a human does.

So if you have a puzzle that can be solved using only techniques that interested people can come up with fairly readily/intuitively and apply without a lot of ceremony, then that would be, perhaps, very easy. The more advanced techniques (for humans) needed to solve the puzzle, the harder it would be rated.

You can also feed these techniques into the generation so that you can guide the difficulty as it's being generated (the way I did it, I found it would still fall into puzzles that are easier than the target, or get stuck on puzzles that are too hard, but applying adjustments to backtracking and forward progress based on heuristics observed in "stuck" scenarios seemed to do the trick.