10
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ It's actually known that the least amount of starting numbers is 17, I'm not sure however, how one would define hard, it could be such a sudoku that is solvable only if one uses one particular method. And that has to be one hard method.. $\endgroup$ – windircurse May 31 '16 at 20:13
  • 8
    $\begingroup$ It has been proved, massive computations involved, that 17 squares are required to force there to be only one solution. Such puzzles are usually not very difficult, however. Difficult is entirely relative to the collection of methods an individual person has learned. Meanwhile, every puzzle can be solved by computer "backtracking" $\endgroup$ – Will Jagy May 31 '16 at 20:16
  • 1
    $\begingroup$ I should take back what I said partially, what I'm not happy with is the question itself. It only makes sense if one can formalize "harder" here. If one does it, maybe it's even trivial to answer. Without defining it, the question is merely a senseless string of words. $\endgroup$ – Git Gud May 31 '16 at 20:28
  • 2
    $\begingroup$ I should emphasize that people have invented many, many strategies for solving, the more responsible authors trying to stick to something a human being might do. In all cases, no collection of human-reasonable strategies can solve all puzzles. As I said, backtracking can solve all of them, and an article appeared in the Notices that adapted backtracking for humans using colored pencils. For me, not much fun, though. $\endgroup$ – Will Jagy May 31 '16 at 20:41
  • 1
    $\begingroup$ @SimpleArt "Hard" and "hardest/harder" are two very different concepts. The former is an adjective. There's little hope of anyone ever being able to give a mathematical definition that properly encompasses it. The latter is (or rather hopes to be) a partial order and even though it is not as hard to formalize as "hard", its formalization still looks bleak. In your question you asked about "hardest". "Hardest" is the maximum of the partial order to be "harder" and it has nothing to do with the adjective "hard". $\endgroup$ – Git Gud May 31 '16 at 22:06
2
$\begingroup$

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}

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ I was obsessed with sodoku right around the year that paper came out, various web forums had many users developing very advanced methods at the time. $\endgroup$ – jdods May 31 '16 at 23:28
  • $\begingroup$ Another article is from the ams notices (also free). $\endgroup$ – Michael Burr Feb 15 '17 at 2:12
2
$\begingroup$

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

$\endgroup$

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.