13
$\begingroup$

NOTE: This is in reference to an existing question which I feel is poor and off-topic. In the spirit of "shaping the site while in private beta", I wanted show how the question can be re-phrased and "fixed" in order to be more on-topic here.

There is a specific Sudoku puzzle presented by the mathematician who discovered it as "the most difficult Sudoku in the world". It looks like this:

8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..

Why is this Sudoku puzzle considered to be so difficult? Can it be solved through strategy alone, or is brute-forcing it required?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Brute force is a strategy. Since there is no objective definition of hardness, only the claimant can know why he considers it “the most difficult”. (It would actually be possible to quantify hardness, e.g. based on the number of required computation steps in a particular computation model — but this would vary depending on the computation model.) $\endgroup$
    – Gilles 'SO- stop being evil'
    May 21, 2014 at 4:59
  • 1
    $\begingroup$ It cannot be solved by searching all squares to find one with only one possible number. it needs very complicated strategies.I'm testing different strategies on it to find that it has only one answer or more and if its one, how to find it. $\endgroup$
    – mpower
    May 21, 2014 at 6:37
  • 1
    $\begingroup$ That depends on the criteria we use to determine the difficulty of a Sudoku as well. $\endgroup$
    – SQB
    May 21, 2014 at 11:18
  • $\begingroup$ You could, of course, edit my post. That is entire philosophy of being able to suggest edits to other's posts $\endgroup$
    – durron597
    May 21, 2014 at 13:36
  • 2
    $\begingroup$ @durron597 I thought about that, but I was worried the edit would be too substantial to be approved. I prefer editing for small changes such as fixing grammar and formatting of questions, not changing the question itself. $\endgroup$
    – IQAndreas
    May 21, 2014 at 17:46

2 Answers 2

Reset to default
16
$\begingroup$

The claim that this is the world's hardest sudoku puzzle was actually made by the author, and popularized by the media. There is nothing to suggest that this is the singular hardest puzzle in existence, however, it's still a pretty dern difficult puzzle.

To quote the author of the puzzle:

"Normal sudoku puzzle logic eliminates the possibilities for each box in two or three steps, but this one requires puzzlers to think ahead eight or nine steps at a time - making very long deductions to eliminate the possible candidates for each box." (source)

That is what makes this puzzle difficult: the number of steps one has to look ahead in order to reduce away clues. The solver on SudokuWiki can't get it because it would simply take too long to do in Javascript, and it's not programmed to look to a depth of nine. Performing an exhaustive search at that depth would take an inconceivable amount of time.

As this is the furthest depth we know of, and the only puzzle of this depth known, it currently takes top spot as the computationally hardest Sudoku.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The incredible amount of time is only required for a depth-first exhaustive search. There are other methods, which can be used, even in Javascript. Notably my own IDDFS concoction (sw-amt.ws/sudoku/worlds-hardest-sudoku) that does not exceed a search depth of 3. In its current unoptimized form it needs a couple of minutes maximum. A couple of seconds on average. $\endgroup$
    – wolfmanx
    Jan 28, 2015 at 1:49
  • $\begingroup$ @wolfmanx Fascinating. It makes sense that a breadth-oriented searching algorithm would be faster. Is IDDFS a standard way of approaching puzzles, or is it relatively original in this regard? $\endgroup$
    – user20
    Jan 28, 2015 at 1:53
  • $\begingroup$ Well, I cannot speak for others :) Since I am a programmer, I do have the tendency to use whatever computer algorithms are available (and feasible for mostly manual application). So to me this comes naturally. But it seems, that IDDFS is usually not applied in this context at all. I came up with the idea on my own, when I observed the effects on random SAT problems, which appeared untractable with a depth-first search, but fell apart, when adding one or two levels of IDDFS lookahead with backpropagation. $\endgroup$
    – wolfmanx
    Jan 29, 2015 at 2:43
0
$\begingroup$

Javascript - 461ms using 4 layers of heuristics derived from easier sudoku and then depth first search with back tracking if an inconsistent node was reached. Probably could be done much quicker even in javascript.

Original puzzle is hard because the setter has taken care that none of the easy solving tricks work. This is basically due to the fact that the cardinality of the union set of the possible values within uncertain cells in any block , row or column of the puzzle equals the number of uncertain cells put into the union. This means that any simple strategy will fail. If the cardinality of the union set is less than the number of cells in the union then some form of elimination of possible values can occur. It might be possible to adapt the 8 queens puzzle to do a test for how values fit into the global grid across multiple rows etc. but I haven't tried this. Current strategy is to generate both possible grids for cells with a binary choice of values. 5 layers of such choices later - the simpler methods final kick in and allow the problem to be solved conventionally. Current code - with consistency checking etc is 5000 lines plus - object oriented - so not easy to follow at all.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.