The Hardest Sudoku Puzzle

Solution 1:

What about this paper : arXiv:1208.0370v1 ?

The authors Maria Ercsey-Ravasz and Zoltan Toroczkai made a study on how to classify sudoku problems relatively to a Richter-type scale. They express the problem in term of the time used by a k-SAT deterministic continuous time solver to solve the problem.

To enter a bit into detail, in fact they show that such problems (k-SAT) solving time grow exponentially with the number of variables and that the dynamic of the solver evolves to a chaotic system if the logical clause cannot be statified.

Since sudoku have always a solution, the solver escape chaos at some point and converges to a solution. This is precisely this escape-rate from chaotic state which is used as a measure of the difficulty of the puzzle.

According to their measure, the subjectively difficult puzzles known so far [there is a list of some in the bibliography of this paper] are actually receiving a high score from this measure, so making them also objectively difficult in some sense.

The scale range from $0$ to $4$, with $[0,1]$ being the easy sudokus, $[1,2]$ medium ones, $[2,3]$ hard ones and finally above $3$ the top hard problems. The high score presented in the paper is around $3.6$.

Solution 2:

There is at least one very good article introducing a technique, ARTICLE by David Eppstein, pdf free. One of the, well, professional features is Section 3.6 on pdf page 16, called "Experimental Results," including