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