The Hardest Sudoku Puzzle

Question

I was playing a casual game of Sudoku today when a friend came by and asked "What's the hardest game of Sudoku possible?"

My response: "A Sudoku puzzle with the minimal amount of starting numbers where the puzzle is still solvable."

However, I am not happy with this because I want to know the actual minimum to the amount of starting squares I can have. Of course, position matters as well, so I will assume you can place the numbers wherever for optimization.

The closest I can do is look at individual situations to see if they are solvable. But even when I do that, I don't know if there is a setup with even less starting numbers?

Q1: What is the least amount of starting numbers required for a game of Sudoku to be solvable?

Q2: How would you define the "hardest" game of Sudoku?

Answer 1

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}

Answer 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

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

Answer 3

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