The hardest sudokus (new thread)

Everything about Sudoku that doesn't fit in one of the other sections

Re: The hardest sudokus (new thread)

Postby mith » Thu Mar 25, 2021 4:20 am

Thanks, I'll take a look and let you know if I have any questions.

I made a small update to the files I just posted. A while back, I had found some puzzles with high q1/q2 which did not match anything in my database, but eventually I realized that some of these were already known. Some are probably not in the database because the SER is too low, but perhaps a few were just overlooked.

Anyway, I updated my local database with the correct attribution, but because they were generated by my scripts first they got flagged as new since the last update and included in this one. I've removed those puzzles, but thought I would post the originals here in case they need to be added to your database:

Code: Select all
........6..2....4..1...798....79.....8..5......3..8.1...6....2..9...51..4.......8   10.5   1.2   1.2   tarek   tarx0010   HardestSudokusThread-00021   21
........2..1...7...3..5..9......6.4...3.4.8...4.5.9....9..6..3...2...1..7....3...   10.6   1.2   1.2   tarek   -tarx0006Trompe_loeil   HardestSudokusThread-00047   21
........91......35..9.3.8....3.5...67....2......4.......6.8..9..2.7..6..4.....1..   10.3   10.3   10.2   coloin   weekender1   HardestSudokusThread-00066   21
........8..3.9.4..6....7.1....5.97...3.....2...74........7....6..4.5.3..81.......   10.4   1.2   1.2   tarek   tarx0007   HardestSudokusThread-00038   21
........2..8..91..5......4....9.7.....7.3.8.....8.1.3..4..6...5..97..3..2........   10.2   1.2   1.2   tarek   tarx0052   HardestSudokusThread-00015   21
.......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...   10.6   1.2   1.2   coloin   Platinum_Blonde   HardestSudokusThread-00078   21
.......8...6.8.1..7....3..4.47..5...5..32............53....4..7......9...1.9...6.   10.8   1.2   1.2   eleven      HardestSudokusThread-01673   21
..6.......3...7..11.7.............9.3....6..5.5.8..2....3..5..6...2...4..4..9.8..   10.4   10.4   10.2   tarek   -pearly6000-3774tarx0137   HardestSudokusThread-00019   21
...1....87.......9..3.9.5....9.3...5.....23.....4..6....6.8..5.47...1...2........   10.3   10.3   2.6   coloin   coly008   HardestSudokusThread-00079   21
1......8....18...6..9..35.......4.....4....2593....4...7..........76......2..59..   10.8   1.2   1.2   eleven      HardestSudokusThread-01705   21
........7..4.2.6..8.....31......29...4..9..3...95.6....1......8..6.5.2..7......6.   10.3   10.3   9.8   tarek   -pearly6000-3819tarx0139   HardestSudokusThread-00004   22
.....4.....2.3.....5.7....9..4..2.8..985....63.........8....79....8...6...5.1...8   10.4   1.2   1.2   tarek   tarx0035   HardestSudokusThread-00034   22
1....67.....18..3..9..7......4.1...3..9....2.8..6..1....2......5...6.8.......5.4.   10.9   1.2   1.2   eleven      HardestSudokusThread-01580   22
1..4....9.56..9.......1..6..6....8..5....4.9.9....5.1..7....2..6....1.5....3.....   10.6   1.2   1.2   eleven      HardestSudokusThread-02092   22
1....67.9.5.........9.....4....9..3.....1....9..6..8.1..27.....7..8...4.8...6.1.7   10.4   10.4   2.6   eleven      HardestSudokusThread-02058   23
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby 999_Springs » Fri Mar 26, 2021 5:39 am

champagne wrote:
999_Springs wrote:champagne, this is hard enough for your database, isn't it, and no other puzzle in your database has this many clues, right?


Hi "999_Springs",

Basically, the potential hardest data base is supposed to store minimal puzzles. I kept the 32 clues puzzle as on oddity, why not these ones.
In the next days, I'll collect the last games and what has been published here. If anybody has something to supply, it's time to do it;

thanks champagne, i look forward to putting more "oddities" in your database :) i only wanted to beat mauricio's 37 clues record, i'm not really bothered about the minimal versions, since i think that all of them would be singles only until the sticking point and none of them would be rated higher than 11.1

i posted a summary of my findings to the maximum clues per se rating thread here. no new 10.9+ or nested multiple forcing chains puzzle showed up besides the 7 already posted
champagne wrote:
999_Springs wrote:
Code: Select all
59.86.7..
.8...5.96
.467.9.8.
6.59..8.7
8...76.5.
.7..5861.
92.68..7.
.5..9..68
.685.79..  SE 11.1, skfr 11.1, 42 clues



As I assume that this is not a minimal puzzle, it would be interesting to have the corresponding list of minimal. Do you have it? They normally all have a SE ER 11.1 (can be more but nor less)

no, because i don't know how to do it. i could find some minimals by randomly removing clues, but there is no way i would be able to determine all of them, especially since this puzzle has so many clues in it. if anyone has any ideas on how to generate all minimal puzzles out of this one (is there a program to do that?) that would be great if you could point it out to me (or generate them yourself). i suspect there would be at least hundreds of minimals for each one of the 7 puzzles in that post
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: The hardest sudokus (new thread)

Postby champagne » Fri Mar 26, 2021 6:44 am

999_Springs wrote:if anyone has any ideas on how to generate all minimal puzzles out of this one (is there a program to do that?) that would be great if you could point it out to me (or generate them yourself). i suspect there would be at least hundreds of minimals for each one of the 7 puzzles in that post


I have a very poor process doing it, killing step by step one clue, giving the "non minimal" and the "minimal" sets with n-1 clues.
I know that blue and likely dobrichev had/have a better attack.

I am short in time to-day, but if I wanted to build an efficient process, I would try the following (I have many pieces of code available)

solve the puzzles to get the solution grid (brute force)
build the table of unavoidable sets (UAs) {of "size <=18"} and reduce the UAs to the pattern to study. (minimum one clue with a valid puzzle).
for each UA, starting from the smaller to the bigger,
... take the clue if it is a one clue UA
... or try all permutations with at least one missing clue but at least one remaining clue clue .

The first UA will usually have at most 4 clues.

I don't have in the short term the 2 weeks needed to do that

note : in such a process,
a valid perm must keep all other UAs "not empty". This reduces the number of possible perms with more than on clue missing for the studied UA
Each puzzle made of
. clues of solved uas +
. perm of the studied UA +
. other clues of the pattern not yet killed

must still be checked for" valid and minimal", but the the number of such cases is drastically reduced.

And when the file of "remaining UAs" is empty, the last puzzle can be still have multiple solutions and then produces a new UA (this is part of the search 17 clues puzzle process)



EDIT and for such a big start, I would expect thousands of sub puzzles.
champagne
2017 Supporter
 
Posts: 7453
Joined: 02 August 2007
Location: France Brittany

Re: The hardest sudokus (new thread)

Postby dobrichev » Fri Mar 26, 2021 7:16 am

Hi 999_Springs,

You can use gridchecker for minimization.

Code: Select all
gridchecker --similar --removeredundant < 999_Springs.11.1.42 > 999_Springs.11.1.42.min

The above produces 7388 minimal puzzles.
As expected, all they are skfr=11.1/1.2/1.2.
None of them is in Champagne's hardest db from 2019.
dobrichev
2016 Supporter
 
Posts: 1862
Joined: 24 May 2010

Re: The hardest sudokus (new thread)

Postby denis_berthier » Fri Mar 26, 2021 7:32 am

If you start putting non-minimal puzzles in the hardest list, or puzzles that already have a morph in it, under the pretext that they have many givens or for any other reason, this will start turning the list into a hotpot of anything that has some feature.

Are you sure this is what you want to do?
Why not make a different list for these puzzles?
denis_berthier
2010 Supporter
 
Posts: 4174
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby Mathimagics » Fri Mar 26, 2021 8:02 am

For the puzzle above, namely:
Code: Select all
59.86.7...8...5.96.467.9.8.6.59..8.78...76.5..7..5861.92.68..7..5..9..68.685.79..


I count 7388 minimal puzzles, with clue counts ranging from 23 to 30.

There are 12 puzzles with 23-clues:
Code: Select all
59....7.......5..6.467...8.6.5.....78.............8.1.92.6.........9......85.79..
59....7...8...5..6.467...8.6.5.....7..............8.1.92.6.........9......85.79..
59..6.7..........6.4.7.9.8.6.5.....78.............8.1.92.6.........9......85.79..
59..6.7..........6.4.7.9.8.6.59....78.............8.1.92.6................85.79..
59..6.7.........96.4.7...8.6.5.....78.............8.1.92.6.........9......85.79..
59..6.7.......5..6.4.7...8.6.5.....78.............8.1.92.6.........9......85.79..
59..6.7...8......6.4.7.9.8.6.5.....7..............8.1.92.6.........9......85.79..
59..6.7...8......6.4.7.9.8.6.59....7..............8.1.92.6................85.79..
59..6.7...8.....96.4.7...8.6.5.....7..............8.1.92.6.........9......85.79..
59..6.7...8...5..6.4.7...8.6.5.....7..............8.1.92.6.........9......85.79..
59.8..7.......5..6.467.....6.5...8.78...............1.92.6.........9......85.79..
59.86.7.......5..6.4.7.....6.5...8.78...............1.92.6.........9......85.79..


There are 66 puzzles with 30-clues, here are the last 5:
Code: Select all
59.86.7.......5.9..467.9.8.6.59.....8...76....7..5.61.92..8..7..5......8.....79..
59.86.7...8........467........9..8......7..5..7..5861.92.6...7..5..9..6..685.79..
59.86.7...8........467.9.........8......7..5..7..5861.92.6...7..5..9..6..685.79..
59.86.7...8........467.9.........8......76.5..7..5.61.92.6...7..5..9...8.685.79..
59.86.7...8........467.9.8.......8......76.5..7..5.61.92.6...7..5..9.....685.79..


I dusted off some old code, it uses recursive descent search to enumerate the minimal puzzles. The original 42-clue puzzle has 32 individually redundant clues. The enumeration took about 30 minutes.

dobrichev wrote:The above produces 7388 minimal puzzles.

Ha ha, this was posted while my enumeration was running. Thanks, Mladen, at least now I know that my enumeration code is ok! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: The hardest sudokus (new thread)

Postby m_b_metcalf » Thu Apr 01, 2021 7:13 am

Mathimagics wrote:I count 7388 minimal puzzles, with clue counts ranging from 23 to 30.
This inspired me to dust off an ancient program I had. The biggest problem was understanding my recursive code :) . The final result confirms yours:
Code: Select all
#clues:   23  24   25   26   27   28  29 30
#puzzles: 12 187 1061 1607 2106 1600 749 66

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13612
Joined: 15 May 2006
Location: Berlin

Re: The hardest sudokus (new thread)

Postby JPF » Thu Apr 01, 2021 9:51 am

dobrichev wrote:You can use
Code: Select all
gridchecker --similar --removeredundant < 999_Springs.11.1.42 > 999_Springs.11.1.42.min

Mathimagics wrote:For the puzzle above,
The enumeration took about 30 minutes.

gridchecker is very fast for that.
It takes 15 seconds on my laptop*

edit:
unfortunately, it doesn't work for multi-solutions puzzles.
example:
Code: Select all
 7 6 1 | 2 3 4 | 5 8 9
 . . 4 | . . . | 6 . .
 . . 3 | . . . | 7 . .
-------+-------+-------
 . 8 . | . . . | . 9 .
 6 . . | . . . | . . 7
 . 2 . | . . . | . 1 .
-------+-------+-------
 . . 2 | . . . | 3 . .
 . . . | 5 . 9 | . . .
 . . . | . 8 . | . . .   

JPF

*Intel(R) Core(TM)i5-8265U CPU @ 1.60GHz 1.80GHz
JPF
2017 Supporter
 
Posts: 6139
Joined: 06 December 2005
Location: Paris, France

Re: The hardest sudokus (new thread)

Postby 999_Springs » Thu Apr 01, 2021 7:41 pm

dobrichev wrote:Hi 999_Springs,

You can use gridchecker for minimization.

Code: Select all
gridchecker --similar --removeredundant < 999_Springs.11.1.42 > 999_Springs.11.1.42.min

The above produces 7388 minimal puzzles.
As expected, all they are skfr=11.1/1.2/1.2.
None of them is in Champagne's hardest db from 2019.

thanks dobrichev! looks like i'll have fun playing around with this program :) it took a while to set up but once it got going i'm very impressed

the minimalisation of the first puzzle took 14 seconds on my intel core i5 laptop, agreeing with jpf

the 7 puzzles in my previous post generated a total of 25803 minimal puzzles and the search took 57 seconds. all 25803 have the same rating as the original puzzle they came from, and all of them are x/1.2/1.2, which is unsurprising but boring

minimal puzzle counts for all 7 puzzles
Code: Select all
puzzle; clues; SE; skfr; number of minimals
59.86.7...8...5.96.467.9.8.6.59..8.78...76.5..7..5861.92.68..7..5..9..68.685.79..  42 11.1 11.1 7388
59.86.7...8...5.96.467.9.8.8.59..6.76...78.5..7..5681.92.68..7..5..9..68.685.79..  42 11.1 11.1 6941
59.86.7...6...5.98.487.9.6.6.59..8.78...76.5..7..5861.92.68..7..5..9..86.865.79..  42 11.1 11.1 4428
59.86.7...6...5.98.487.9.6.8.59..6.76...78.5..7..5681.92.68..7..5..9..86.865.79..  42 11.1 11.1 4430

...6..8..6..58..97.8..7...5921.58.7.5....6.89.68.9.5..8..9.57...96..7.58...86.94.  37 11.1 10.9 480
7.96..8..8.379..56.6..8...99.1.58.6......7.98.8796.5..5.28.69...7...9.85.9857.6..  40 11.0 10.8 796
..96..8..61.87..59.8.....6782..5679......7.86.6798.5..54.7..6.8..6..8.75..856.9..  39 10.9 10.9 1340

the 25803 puzzles each contained between 22 and 31 clues. there was only one 22, which came from the fourth puzzle
59.8..7.......5..8.4.7...6.8.5.....76.............6.1.92...........9...6...5.79..
and only one 31, which came from the third puzzle
59....7...6...5..8.487.9.6....9.........76.5..7..5861.92..8..7..5.....86.86..79..

according to this post, there is no 11.1+ 31 clue puzzle in the database, so this 31 is a new record for the hardest minimal 31

i may keep looking for some more of these high clue puzzles if/when i feel like it - now that i know about gridchecker, i'm sure it would save me a lot of time generating puzzles if i can find out how all the commands work. i'm sure it would have been a lot easier if i'd heard about it earlier!
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: The hardest sudokus (new thread)

Postby champagne » Fri Apr 02, 2021 5:55 am

JPF wrote:
edit:
unfortunately, it doesn't work for multi-solutions puzzles.
example:
Code: Select all
 7 6 1 | 2 3 4 | 5 8 9
 . . 4 | . . . | 6 . .
 . . 3 | . . . | 7 . .
-------+-------+-------
 . 8 . | . . . | . 9 .
 6 . . | . . . | . . 7
 . 2 . | . . . | . 1 .
-------+-------+-------
 . . 2 | . . . | 3 . .
 . . . | 5 . 9 | . . .
 . . . | . 8 . | . . .   

JPF

*Intel(R) Core(TM)i5-8265U CPU @ 1.60GHz 1.80GHz


makes sense, you can not produce minimal sudoku out of a grid with multiple solutions. You have first to add clues to reach a unique solution.
champagne
2017 Supporter
 
Posts: 7453
Joined: 02 August 2007
Location: France Brittany

Re: The hardest sudokus (new thread)

Postby JPF » Fri Apr 02, 2021 10:59 am

I agree that my remark was not useful in this thread which aims to collect valid difficult puzzles (therefore having only one solution)

I invite you nevertheless to read this post of 2007 which generalizes the definition of minimality to "puzzles" or "subgrids" having several solutions.
You will also discover the notion of maximality and "closure" which seem to me essential to the study of the structure of sudoku - subgrids.
I had suggested introducing the notion of maximality in the definition of unavoidable set, but that was bounce back by Red Ed.
See here and here

JPF
JPF
2017 Supporter
 
Posts: 6139
Joined: 06 December 2005
Location: Paris, France

Re: The hardest sudokus (new thread)

Postby champagne » Fri Apr 02, 2021 12:42 pm

JPF wrote:I agree that my remark was not useful in this thread which aims to collect valid difficult puzzles (therefore having only one solution)

I invite you nevertheless to read this post of 2007 which generalizes the definition of minimality to "puzzles" or "subgrids" having several solutions.

JPF


No problem with the concept, but this requires an appropriate code. The start point can have a huge number of solutions, so it could be hard to have an efficient code for all cases.

BTW, the last link requires special rights.
champagne
2017 Supporter
 
Posts: 7453
Joined: 02 August 2007
Location: France Brittany

Re: The hardest sudokus (new thread)

Postby JPF » Fri Apr 02, 2021 8:14 pm

champagne wrote:BTW, the last link requires special rights.

It should be OK now.
The link points to a copy of dobrichev's thread about Unavoidable Sets on the Sudoku Programmers Forum (2010)

JPF
JPF
2017 Supporter
 
Posts: 6139
Joined: 06 December 2005
Location: Paris, France

Re: The hardest sudokus (new thread)

Postby mith » Tue Apr 06, 2021 7:56 pm

I've expanded my searching recently to 25-27c puzzles; since I just did a full update I won't pull a new one just yet, but I believe this is the new high for 27c?

Code: Select all
...........1..2.34.3..156......5...6.67.3.1..3.81...9..7.......1.5.7...36.3..17..  ED=11.5/1.2/1.2


9 new 11.6s for 26c as well.

Code: Select all
..............1.23.24.5..1.....16....165...4.7.5.246...41..5.6..6..4...89........  ED=11.6/1.2/1.2
...........1..2.34.3..4..25..5..34...2..145..6..7...1...8....51.5...12..1.......9  ED=11.6/1.2/1.2
...........1..2.34.3..4..15.....6..2...2...47..2.5.1....3..54...24.1.5..8..9...2.  ED=11.6/1.2/1.2
..............1.23..2.4.51...4...16..6..54..272..16.....6..5.4..8..2.6..2.......9  ED=11.6/1.2/1.2
...........1..2.34.3..4..25........6..7....51.5...12...15..34...2..145..8..9...1.  ED=11.6/1.2/1.2
..............1.23..2.4.51.........6..7..524..8..2.7....4...17..7..54..292..17...  ED=11.6/1.2/1.2
...........1..2.34.3..4..15........6.....7.52..2.5.1....3.254...24.1.5..8..9...2.  ED=11.6/1.2/1.2
...........1..2.34.3..4..15.....6.52...2....7..2.5.1....3..54...24.1.5..8..9...2.  ED=11.6/1.2/1.2
...........1..2.34.3..4..15.....6..2...2...47..2.5.1....3..5....24.1.5..8..9.4.2.  ED=11.6/1.2/1.2


Some of these are closely related, and I'm sure there are a number of others that will be found shortly. (An 11.6 27c wouldn't surprise me at all.)
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby mith » Thu Apr 08, 2021 4:06 pm

As expected, a 27c 11.6:

Code: Select all
........1.....2.3...4.5..62....67.....65...4778..246....2..5.7..4....9..1...4.32.  ED=11.6/1.2/1.2
mith
 
Posts: 996
Joined: 14 July 2020

PreviousNext

Return to General