The New Sudoku Players' Forum

[MadOverlord]

Now look at the messages for where it says the puzzle is invalid.

Ah, nice catch. When it was doing its validity checking, the app was only using the solved squares, and not taking into account any reductions you'd made.

So the invalid reductions you made were not triggering any warnings.

I have put in a fix; v2.0.4 will validity-check using any reductions you have made, and Recurse! will first try with reductions, and then with just solved squares, in order to give you better feedback.

2.0.4 will also contain some of the simpler versions of Unique Rectangles.

[ravivprasad]

I am writing a book on Sudoku geared for the teenage market in India (13-17 year olds) to get them interested in maths / comp science.

I request permission to quote this as the "hardest known puzzle" to date. Please can you give me this permission to quote this.

Also, can the solution be provided.

I do not intend to provide the reasoning for this solution, but give it to the kids as an exercise to solve on their own, but with the end solution. And get them to write their own solvers in VB, etc.

How would the posters on this topic like to be mentioned - their true names & affiliations.

Can anyone also suggest some difficult 17-clue puzzles for the kids to solve.

Many thanks to everyone.

Ravi Visvesvaraya Prasad

New Delhi, India

[MadOverlord]

I request permission to quote this as the "hardest known puzzle" to date. Please can you give me this permission to quote this.

I can't, since I didn't come up with it. I was given it by Douglas Bowman, and he found it on Vegard Hannsen's Menneske.no Sudoku archive.

http://www.menneske.no/sudoku/eng/showpuzzle.html?number=4061526

It may have been independently discovered before that; I have seen identical versions with the numbers shuffled.

[r.e.s.]

I request permission to quote this as the "hardest known puzzle" to date. Please can you give me this permission to quote this.

[...] I was given it by Douglas Bowman, and he found it on Vegard Hannsen's Menneske.no Sudoku archive. [...] It may have been independently discovered before that [...]

If anyone believes the puzzle in question is the "hardest known" sudoku, I suggest they explain why they think so, lest that description be meaningless.

[MadOverlord]

If anyone believes the puzzle in question is the "hardest known" sudoku, I suggest they explain why they think so, lest that description be meaningless.

It requires Trebor's Tables (with all the options turned on) or the latest Ultracoloring to complete, and size of the table of inferences at the "stick point" where those techniques come into play is larger than any other puzzle we've run into.

Obviously, difficulty metrics are somewhat subjective, but nothing I've run into so far comes close.

[r.e.s.]

If anyone believes the puzzle in question is the "hardest known" sudoku, I suggest they explain why they think so, lest that description be meaningless.

It requires Trebor's Tables (with all the options turned on) or the latest Ultracoloring to complete, and size of the table of inferences at the "stick point" where those techniques come into play is larger than any other puzzle we've run into.

Obviously, difficulty metrics are somewhat subjective, but nothing I've run into so far comes close.

Using Sudoku Susser 2.0.4, Trebor's Tables ("with all the options turned on") gives the following results for the total number of implications:

Code: Select all

                           Tabling only    Tabling preceded by standard methods   
                           ------------    ------------------------------------
MadOverlord's toughest      71,643         59,924
Nick70's toughest*          98,211         75,204

According to these results, by the metric you propose, the sudoku you're calling the "toughest known", isn't. This would seem to be the conclusion whether tabling is or is not preceded by standard methods (i.e. whether or not it begins only at the "sticking point" of these methods).

*Nick70's toughest:

Code: Select all

 . . 2 | . 9 . | 1 . 7 
 . 3 8 | 6 . . | . . . 
 4 . . | . . . | . . . 
 ------+-------+------
 . . . | . . 5 | . . . 
 . . 9 | . 1 . | 3 . . 
 . . . | 4 . . | . . . 
 ------+-------+------
 . . . | . . . | . . 4 
 . . . | . . 7 | 9 2 . 
 8 . 6 | . 3 . | 7 . . 


[MadOverlord]

According to these results, by the metric you propose, the sudoku you're calling the "toughest known", isn't.

Nick's is a tough puzzle, but with tabling at the standard settings (no aggressive forces and pins, non-exhaustive), it only requires 1 round of tabling and 35K inferences before enough is found to crack the puzzle.

* Made progress using Trebor's Tables to find inferences about the puzzle. A total of 35348 implications about the puzzle were generated and examined in order to find these inferences - you'd run through several pencils working them out by hand!

The "toughest known puzzle", at the same settings, requires multiple rounds of tabling and bowman bingo. So from a practical standpoint, it's probably tougher.

Quite frankly, any puzzle that requires techniques like tabling or ultracoloring is so difficult as to be unratable as anything other than "ballbuster" (or to be fair to the ladies, a "titwringer").

Hopefully, analysis of these pathological puzzles will help us find new patterns that can be used to solve them "humanely".

[Sue De Coq]

Would it be possible to obtain human-readable output from Trebor's Tables?

[MadOverlord]

Would it be possible to obtain human-readable output from Trebor's Tables?

If you get a puzzle to the point where tabling is required, you can manually table the entire puzzle (1 round) by pressing "a". If you press "A", you'll get verbose output of the results of the tabling. You can repeatedly press "A" to do additional rounds of tabling until you get sufficient solves.

You can also table a single square by mousing over it and pressing "t" (or "T" to get verbose output).

Tabling will generate a LOT of output.

[stuartn]

Again, with Nick's toughie it comes down to two cells. After the initial 8 straightforward moves, a 3 in R4C4 and a 6 in R7C6 blows it wide open - but what forces the 3 and 6?

stuartn

[DanO]

In Nicks puzzle there are a large number of Magic Squares where an initial guess in any one of them blows the whole thing wide open. The Toughest known puzzle has only 1 such Magic Square. (and of course it was the last 1 I tested ).

[r.e.s.]

According to these results, by the metric you propose, the sudoku you're calling the "toughest known", isn't.

Nick's is a tough puzzle, but with tabling at the standard settings (no aggressive forces and pins, non-exhaustive), it only requires 1 round of tabling and 35K inferences before enough is found to crack the puzzle.

Wait a minute! ... that's "changing the rules in the middle of the game". I was responding to your choice of metric described as using tabling with all the options turned on (not what you're now calling "standard settings"). Of course, for any puzzle the metric can always be changed to give it a harder or easier rating.

[r.e.s.]

Again, with Nick's toughie it comes down to two cells. After the initial 8 straightforward moves, a 3 in R4C4 and a 6 in R7C6 blows it wide open - but what forces the 3 and 6?

Actually, in Nick70's toughie there is at least one cell of the kind I'll call a "basic magic cell" (or "basic key cell") at r8c5 -- the correct guess in such a cell leads to the solution using only naked- & hidden-singles.

In Nicks puzzle there are a large number of Magic Squares where an initial guess in any one of them blows the whole thing wide open. The Toughest known puzzle has only 1 such Magic Square. (and of course it was the last 1 I tested ).

Well, in Nick70's toughie there are a large number of cells which if guessed correctly lead to the solution using coloring or other somewhat-nonbasic moves. But true, there is at least one basic key cell as described above.

In the so-called Toughest Known sudoku, if I recall correctly, there are no basic key cells, but r9c7 comes close (it leads to naked pairs and locked candidates), and so does r8c7 (it leads, additionally, to naked triples, x-wings, and xy-wing). So on this basis, it does rank harder than Nick70's.

[MadOverlord]

Of course, for any puzzle the metric can always be changed to give it a harder or easier rating.

Absolutely -- and the problem is, people can honestly disagree about the "right" metric to use, and their opinions of what is correct can evolve.

I am not in any way "married" to the Toughest Known Puzzle (tm). I just haven't seen another candidate that impresses me as being significantly more difficult. An example might be a puzzle that required aggressive forces and pins (which is an option that a human solver would have a tough time doing by hand) in order to make any progress.

We should probably just sidestep the issue and say that any puzzle that requires tabling or ultracoloring is a "Pedantically Pathological Puzzle."

[DanO]

Another way is instead of declaring that guessing is somehow unacceptable, define the cost of a guess to include the average cost of all the blind allies that guessing could lead you down. If a guess has an equal probability of being right or wrong the cost of the guess would be 1/2 of the cost of solving the puzzle down the wrong path until a conflict is reached. If the cost of a guess is expected to be less than the cost for tabling or super coloring wouldn't the logical choice be to guess?

This also opens up a whole new field of educated guessing to keep the researchers busy.