Very interesting suggestions. Thanks for the feedback!
The rng one is challenging because the generator is tuned for solvability and the difficulty is incidental. I'll have to think about that one.
With Sudoku there's somewhat of an agreed tier list of techniques. A harder puzzle will usually require more/harder techniques to solve, but yeah it varies a lot and it's hard to make good difficulty algorithmic.