The New Sudoku Players' Forum

[darq]

Probably you're right. It's like making a correct guess first, and then applying a strong tool to solve the rest. Even with weaker tools it's already hard to find a sudoku having uniqe solution that wouldn't have any key cells. Possibly 16x16 or 25x25 would make a diffrerence here.

[Sue De Coq]

The Puzzle Gallery at act365.com/sudoku/gallery is a work-in-progress that already features some very challenging puzzles. All the puzzles are graded according to difficulty. Here's a taster of the toughest category:

Code: Select all

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


The gallery has plenty of straightforward puzzles suitable for human solvers.

[MadOverlord]

The current record-holder for psychotic toughness is this puzzle:

Code: Select all

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


It can be deductively solved using the Tabling algorithm; a complete expansion of the tables when it tabling becomes necessary requires 59924 implications.

TILPs toughest puzzle "only" requires 42936 implications to solve. But either will put a human player into a mental institution.... ;^)

[r.e.s.]

The current record-holder for psychotic toughness is this puzzle:

Code: Select all

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


It can be deductively solved using the Tabling algorithm; a complete expansion of the tables when it tabling becomes necessary requires 59924 implications.

TILPs toughest puzzle "only" requires 42936 implications to solve. But either will put a human player into a mental institution.... ;^)

I'm trying to reproduce your results, but your Sudoku Susser 1.3.1 reports the following:

Code: Select all

                                   
                             total #implications by tabling
                             ------------------------------                               
TILPS toughest               13604 (= 5042+8562)
sudoku posted above          28002 (= 5970+6887+5752+9393)     
sudoku by Nick70**           32462 (= 17847+14615)
sudoku by Rubylips***        32922 (= 5393+27529)

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

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


Am I misreading something?

[MadOverlord]

Am I misreading something?

Do you have all the options on, especially exhaustive table generation? Unless you exhaustively table, you might get lucky and get a crack early in the tabling process.

Exhaustive tabling generates a better idea of how complex the puzzle is, IMHO, but the best "metric" for puzzle complexity is a matter of some debate. Bottom line, all the super-toughs are psychotic puzzles.

[Wolfgang]

... 59924 implications...
... 42936 implications...

I came to similar results when i compared the 2 puzzles at the state when my solver got stuck without guessing (elimination is done by "trying" the candidate and then using simple techniques up to pairs and xwings)
"toughest":
204 candidates, 50 to eliminate, 1 guess solves, 3 cells unique (after the 50 eliminations)
TIPLS 1mio:
172 candidates, 68 to eliminate, 5 guesses solve, 16 cells unique

[udosuk]

The current record-holder for psychotic toughness is this puzzle:

Code: Select all

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

Scanning for key cells from the top left corner, for a moment I thought this must be the one without any... then to my disappointment there is indeed one, in R9C7. In fact, choosing the correct entry for that cell will make the puzzle collapse spectacularly, with all the remaining cells solved in no time using techniques no more than naked pairs. So the complexity of this puzzle must be lying on the proving of solution uniqueness, not finding the correct answer...

Seeing everybody using this "implications count" method, just curious has somebody try that on the one posted by Sue De Coq (the "taster")? How does it compare to our "record-holder"?

[darq]

Seeing everybody using this "implications count" method, just curious has somebody try that on the one posted by Sue De Coq (the "taster")? How does it compare to our "record-holder"?

Rated high - 53126. Also the puzzle I posted a month ago got some nice score (44211). But what about the super hard puzzle from menneske? Generates 82954 implications, but otherwise solved with Nishio. Should it be the hardest? IMO not.

Code: Select all

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

[Moschopulus]

>TILPS toughest 13604 (= 5042+8562)
>sudoku posted above 28002 (= 5970+6887+5752+9393)
>sudoku by Nick70** 32462 (= 17847+14615)
>sudoku by Rubylips*** 32922 (= 5393+27529)

But on the other hand, the Sadman program reports that the Rubylips puzzle can be solved by forcing chains, and does not require T&E. It is rated hard. The others cannot be solved by forcing chains, and are rated diabolical.

[MadOverlord]

But on the other hand, the Sadman program reports that the Rubylips puzzle can be solved by forcing chains, and does not require T&E.

Right. To be in the running for a psycho-tough puzzle, it's got to be something that requires Tabling to solve!

[gsf]

http://www.research.att.com/~gsf/sudoku/FNBTXZ-2-constrained.dat.gz
contains 1453 minimal 2-constrained (2 magic/key cells to solve w/o coloring) puzzles

[darq]

To be in the running for a psycho-tough puzzle, it's got to be something that requires Tabling to solve!

But this definition is a bit incomplete, as the meaning of 'requires' will change if a new solving method is invented. Perhaps it would be better to specify a list of methods that are considered "non-psychotic"?

[darq]

http://www.research.att.com/~gsf/sudoku/FNBTXZ-2-constrained.dat.gz
contains 1453 minimal 2-constrained (2 magic/key cells to solve w/o coloring) puzzles

Very good compilation!

My favourites are:

#0729 (where numbering starts from #0000)

Code: Select all

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

#0732

Code: Select all

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

#1307

Code: Select all

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

[Moschopulus]

Ok, I'll bite. Why are they your favourites?

[darq]

Ok, I'll bite. Why are they your favourites?

Once I've started a project to find shortest proofs by contradiction for hardest sudokus. Have not finished it (lost interest at some point), but I'm still using the partial program to get a kind of my private evaluation. For #0729 and #1307 no unbranched proofs were found, and all proofs for #0732 need 4 consecutive steps (#0426 falls into this category as well). Also table sizes generated by MadOverlord's susser are big ( > 53000).