So most resources providing Sudoku puzzles assign a difficulty category to each puzzle, even some I've seen with 15 or more difficulty categories. But what is a good way to assign these difficulty categories? If enough human puzzle solvers were used, the average time for a human to complete a puzzle and the percentage of people who successfully solved the puzzle could be computed for the human sample, and difficulty categories assigned accordingly. But it seems like there should be predictable scenarios that keep appearing as various puzzles are being solved that affect the average human difficulty, which could be automatically detected as a computer solves the puzzle and then these patterns could be assembled into a predicted average difficulty for humans. Are there / what are good techniques to do this? Maybe machine learning with enough training data of human performance on sample puzzles?
There are have been many such attempts. Most of them try to derive deduction rules which humans seem to use to solve Sudoku puzzles.
My money is on this approach:
Mária Ercsey-Ravasz & Zoltán Toroczkai (2012), The Chaos within Sudoku, Scientific Reports 2:75, Nature.
The idea is based around the notion of transient chaos in a dynamical system.
In dynamical systems, when you change the state, there is often a period of time where a transient signal dominates, before the system manages to get itself into a steady state solution. If the dynamical system is nonlinear, the transient may be chaotic.
This is different from a chaotic attractor (e.g. the Lorentz attractor), in that the steady state that the system is eventually drawn to isn't chaotic, just the transients.
The time that the system takes for the transients to die down is called the escape rate. What the authors found is that if you turn the puzzle into a SAT problem, and then turn that into an equivalent dynamical system (where the attractor of the dynamical system is the solution to the SAT problem), the escape rate of the system correlates quite well with how Sudoku puzzles are rated for hardness.
The interesting thing about this approach is that it's independent of Sudoku. Any puzzle which can be turned into a SAT problem fairly directly (the SAT problem and the puzzle can't diverge too far) can be analysed in the same way.
If you want to measure the hardness of a puzzle "for a human", a typical approach is the inference techniques needed to complete the puzzle. For instance, you can categorize inference strategies as basic, intermediate, and expert.
These methods can all be implemented on a computer. If the computer can solve the puzzle with just basic methods, the puzzle is easy. If intermediate techniques are needed, the puzzle is medium. Otherwise, the computer needs expert strategies, and the puzzle is hard. I have seen a program that classifies puzzles based on this approach, but can't seem to recall the exact reference.
All the puzzles that can be solved with just inference (no guessing needed), will be easy for a computer. If you are interested in puzzles hard for a computer, one basic rule is that they need to resort to guessing at some point. Generation of hard Sudoku puzzles (for a computer) have been investigated too, and you can easily find relevant papers.