The Hardest Sudoku Puzzle

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$.

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

We conclude that these nonlocal rules significantly reduced the number of unsolvable puzzles

The book from 2005 that told me about the article has been re-issued as BOOK

One potential way to define "hard" would be in terms of how long it takes a particular Sudoku-solving algorithm takes to solve the puzzle. If we wanted to make it less method dependent, we could use an average over all Sudoku algorithms which meet certain criteria {e.g. all algorithms with optimal average-case time complexity}