7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For a non-statistical approach you'd need some idea of what this "hardness" is resp. which parameters of the puzzle it is tied to (and how). $\endgroup$ – Raphael Aug 22 '14 at 8:47
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a very interesting approach, thanks for the reference. I don't understand why it should work so well, and it's also not clear to me how hard it is to calculate the escape rate (except maybe estimation by simulation), but I'll take a look at the reference and maybe it will come together. $\endgroup$ – user2566092 Aug 22 '14 at 16:52
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This seems like a good approach if the 15 or so inference rules used by humans could be assigned a hardness score based on training data of humans solving puzzles, and then the puzzle difficulty could either be the sum or the maximum of the hardness for the sequence of rules required to solve the puzzle. The hard part to me seems to be how do you infer the hardness score for each individual inference rule given solution times for entire puzzles when humans solve them. Also some rules should have variable hardness, like "alternating inference chain" where it gets harder the longer the chain is. $\endgroup$ – user2566092 Aug 22 '14 at 17:00
  • $\begingroup$ "Sudoku as a Constraint Problem" by Helmut Simonis (4c.ucc.ie/~hsimonis/sudoku.pdf) is an article that grades Sudoku puzzles based on the inferences needed to solve the puzzles without search. $\endgroup$ – Zayenz Aug 27 '14 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.