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 Paquita » Tue Aug 22, 2023 5:21 pm

Checking rates, I came across this one
98.76.5..7.5..9....64.58...8.....4.....9...........32.6.8..5..4.7.64.....498.7..5 ED=11.9/1.2/1.2

I believe it was from Hendrik and it seems to be a new 11.9. Correct me if I'm wrong.
Paquita
 
Posts: 132
Joined: 11 November 2018

Re: The hardest sudokus (new thread)

Postby champagne » Tue Aug 22, 2023 5:45 pm

mith wrote:That seems pretty reasonable; my CPU can go up to 32 threads but it probably averages around 1200-1500% CPU (peaking around 2600%) running the multithreaded version for the high SER puzzles. If the single-threaded runtime for Golden Nugget were exactly 30 minutes and your CPU's speed is comparable, it averaged 1268% here; not a perfect comparison obviously but it should give an idea how much the multithreading matters.

I'd guess it taken about two-three months of my PC's time to rate all of the 11.6+ expanded forms in the depth 3 database (232529). Hard to say how making the contradiction search exhaustive would affect that. Regardless, it's would be a couple orders of magnitude more effort to re-rate all of them now compared to when I started the depth search.

my desk computer is an old (at least five years old) I7_770 3.4 GHz
champagne
2017 Supporter
 
Posts: 7455
Joined: 02 August 2007
Location: France Brittany

Re: The hardest sudokus (new thread)

Postby mith » Tue Aug 22, 2023 7:30 pm

Just a bit under 20 minutes here for Golden Nugget.
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby hendrik_monard » Tue Aug 22, 2023 7:40 pm

Paquita wrote:Checking rates, I came across this one
98.76.5..7.5..9....64.58...8.....4.....9...........32.6.8..5..4.7.64.....498.7..5 ED=11.9/1.2/1.2

I believe it was from Hendrik and it seems to be a new 11.9. Correct me if I'm wrong.

Hi Paquita,

Indeed, it was the first of 10 puzzles with SER 11.9 in my list of 28 September 2022.

Today I examined the list with new puzzles submitted by you yesterday. I always do that before adding puzzles to my local reference database.
They all are minimal. However, 1495 of them are duplicates of previously submitted puzzles. All of these duplicates are in your preceding list with the exception of the the two 11.8s that are in mith's most recent list.
hendrik_monard
 
Posts: 96
Joined: 19 April 2021
Location: Leuven (Louvain) Belgium

Re: The hardest sudokus (new thread)

Postby mith » Tue Aug 22, 2023 7:56 pm

Oh, one more thing on the ph2010 puzzles; one of them rates 11.7, not 11.8:

Code: Select all
........1..2..3.4..5..6.7.......1.3....4....85...7.2....5.2.9...9.....8.76.9.....;11.80;1.20;1.20;DOB;13_01;768268;22;*
........1..2..3.4..5..6.7.......1.3....4....85...7.2....5.2.9...9.....8.76.9.....     11.7    1.2     1.2
time 518.438244342804


The time is for rating with the pattern game serate rather than the SukakuExplainer one, just to be sure the difference isn't there. skfr appears to be 11.8 so that may be the explanation, or it could be something else.
mith
 
Posts: 996
Joined: 14 July 2020

Postby 1to9only » Tue Aug 22, 2023 8:11 pm

champagne wrote:Some members of the forum having a good practice of JAVA fixed some bugs in serate, but nobody, AFAIK, tried to reach a rating morph neutral although this oddity has been source of trouble in many case in the game.

The morphs rating problem was fixed some time ago (I posted about it here). It is a rework of lksudoku's fix posted here.
The fix is in all my various versions of SEs. PGE does not have the fix as it was created for the Patterns Game.

Test file (using se-mismatch puzzle from PG#0435):
Code: Select all
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4

PGE output:
Code: Select all
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=9.9/9.9/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=9.9/9.9/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4

PGXplainer (from here) output:
Code: Select all
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4

Edit: PGXplainer is PGE (for the Patterns Game) with my fix to lksudoku's fix to Chaining!
Last edited by 1to9only on Wed Aug 23, 2023 7:35 am, edited 1 time in total.
User avatar
1to9only
 
Posts: 4177
Joined: 04 April 2018

Re: The hardest sudokus (new thread)

Postby Paquita » Tue Aug 22, 2023 8:47 pm

Hendrik,

Your other puzzles from the 11.9's list do rate 11.8, maxlex, PGE, only this one remains 11.9. I wanted to mention it as the 11.9's are rare and ususally get a bit of attention when one is found. And it should be a 11.9 in the database. (The tenth!)

I apologize for the doubles in my list. I made a mistake in what I did publish already.

Hendrik and mith,

All my 11.8's were found when I was using your results as seeds. At that time mith, you did not publish the minimals and that makes it hard to see if a puzzle was already found. After a short excursion on rating expanded puzzles, I go back to rating minimals. I believe there are more expanded versions than minimals, every single that is added makes for a new expanded puzzle. I think rating minimals is more efficient and it is so much more easy to see if a puzzle was found already.
So I found a few 11.8 that are now in miths minimal list, and they do rate T&E(3).
Just this 11.8 is not in miths list
98.76.5..7.4.5..6..........6.794....5...87.....86.5.....9.....8....9432......64.. ED=11.8/1.2/1.2 PAQ
And i missed a few of these in miths list
JPF
98.76.5..7.5.48....64..9....976.4.8.....87..9....5.....4......3..6...4.2......... ED=11.8/1.2/1.2
98.76.5..7.5.48....64..9....4.....3...6...42............76.4..8...95........87.9. ED=11.8/1.2/1.2
9876.........958.......4...8.9...36..6....2...23....8767.......3.82..69...23.67.. ED=11.8/1.2/1.2
9876.........958.......4...76....3...32....87..9...26.67.......2.83..69...32.67.. ED=11.8/1.2/1.2
9876.........958.......4...8.9...36..6....2...23.6..8767.......3.82..69...23..7.. ED=11.8/1.2/1.2
9876.........958.......4...76....3...32.6..87..9...26.67.......2.83..69...32..7.. ED=11.8/1.2/1.2
Paquita
 
Posts: 132
Joined: 11 November 2018

Re: The hardest sudokus (new thread)

Postby mith » Tue Aug 22, 2023 9:34 pm

Paquita wrote:I believe there are more expanded versions than minimals, every single that is added makes for a new expanded puzzle.


The definition of a singles expanded puzzle we use is a puzzle which has had all possible singles added. Some minimals are already singles expanded (anything EP>2.3). Some expanded forms can have additional digits added which aren't singles but allow them to remain depth 3 (this is what one of my scripts does), but overall the minimal to expanded form ratio is about 4:1 in the depth 3 databases.

(The exact count may be slightly off due a rare and annoying duplication bug - which may be fixed in the latest scripts but it was rare enough that I can't be sure - but currently the minimal database is at 4634322 while the expanded is at 1114097; the only requirement for these apart from form is that they are depth 3, so this includes a large number of puzzles below the proposed 11.6 cutoff, including some 4.Xs which solve quickly with uniqueness.)

Paquita wrote:98.76.5..7.4.5..6..........6.794....5...87.....86.5.....9.....8....9432......64..


This is already in the database, it's just that the gsf-minlex form of the expanded puzzle rates 11.7 instead of 11.8, so it's not included in the previous minimal list. As I mentioned, I will include a full minimal list when I do the actual update.

The JPF ones are also in, just in their gsf-minlex form (since that's how all of them are saved in the database). When I get the scripts on github, I'll include one to check this quickly using gsf's sudoku program.

1to9only wrote:The morphs rating problem was fixed some time ago (I posted about it here). It is a rework of lksudoku's fix posted here.


I knew I remembered you mentioning this somewhere, thanks :) I'll run the 11.8s against your SE at some point.
mith
 
Posts: 996
Joined: 14 July 2020

Postby 1to9only » Wed Aug 23, 2023 7:44 am

1to9only wrote:PGXplainer (from here) output:
Code: Select all
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4

Edit: PGXplainer is PGE (for the Patterns Game) with my fix to lksudoku's fix to Chaining!

I've updated my previous post to mention that there is a version of PGE that has my fix to lksudoku's fix!! Download PGXplainer.jar from here.

Usage:
Code: Select all
java.exe -jar PGXplainer.jar --input=puzzles.txt --output=output.txt
or
java.exe -cp PGXplainer.jar sudoku.serate --input=puzzles.txt --output=output.txt
User avatar
1to9only
 
Posts: 4177
Joined: 04 April 2018

Re: The hardest sudokus (new thread)

Postby P.O. » Wed Aug 23, 2023 9:56 am

98.76.5..7.5..9....64.58...8.....4.....9...........32.6.8..5..4.7.64.....498.7..5 ED=11.9/1.2/1.2

SE is not reliable to hierarchize puzzles that are not in te1, 11.9 the highest SE rating involving nested chains of 300, 400 nodes for a puzzle that is in 4-template and solves with this one combination (1 2 3 4) doesn't seem reasonable.
Hidden Text: Show
Code: Select all
#VT: (311 39 41 3 3 18 18 8 6)
Cells: nil nil nil nil nil nil nil nil nil
Candidates:nil nil nil nil nil nil nil nil nil

9      8      123    7      6      1234   5      134    123             
7      123    5      1234   123    9      1268   13468  12368           
123    6      4      123    5      8      1279   1379   12379           
8      12359  12367  1235   1237   1236   4      15679  1679           
1234   1235   12367  9      12378  12346  1678   15678  1678           
14     159    167    145    178    146    3      2      16789           
6      123    8      123    9      5      127    137    4               
5      7      123    6      4      123    1289   1389   12389           
123    4      9      8      123    7      126    136    5               

1: (1 2 3 4) 16 instances
..3..4.12.1.23..4.2.41....3....234.1432..1...1..4..32..2.3..1.4..1.42.3.34..1.2..
..3..4.12.1.23..4.2.41...3.....234.1432..1...1..4..32..2.3..1.4..1.42..334..1.2..
..3..4.12.1.23..4.2.41....3..2..34.143..21...1..4..32..2.3..1.4..1.42.3.34..1.2..
..3..4.12.1.23..4.2.41...3...2..34.143..21...1..4..32..2.3..1.4..1.42..334..1.2..
..2..4.13.1.32..4.3.41....2....324.1423..1...1..4..32..3.2..1.4..1.432..24..1..3.
..2..4.13.1.32..4.3.41....2..3..24.142..31...1..4..32..3.2..1.4..1.432..24..1..3.
..2..4.13.1.32..4.3.41..2......324.1423..1...1..4..32..3.2..1.4..1.43..224..1..3.
..2..4.13.1.32..4.3.41..2....3..24.142..31...1..4..32..3.2..1.4..1.43..224..1..3.
..3..4.12.1.23..4.2.41....3.3..214..4.2..3..11..4..32..2.3..1.4..1.42.3.34..1.2..
..3..4.12.1.23..4.2.41...3..3..214..4.2..3..11..4..32..2.3..1.4..1.42..334..1.2..
..3..4.12.1.23..4.2.41....3.32..14..4...23..11..4..32..2.3..1.4..1.42.3.34..1.2..
..3..4.12.1.23..4.2.41...3..32..14..4...23..11..4..32..2.3..1.4..1.42..334..1.2..
..2..4.13.1.32..4.3.41....2.2..314..4.3..2..11..4..32..3.2..1.4..1.432..24..1..3.
..2..4.13.1.32..4.3.41....2.23..14..4...32..11..4..32..3.2..1.4..1.432..24..1..3.
..2..4.13.1.32..4.3.41..2...2..314..4.3..2..11..4..32..3.2..1.4..1.43..224..1..3.
..2..4.13.1.32..4.3.41..2...23..14..4...32..11..4..32..3.2..1.4..1.43..224..1..3.

.......1..1..........1.............1.....1...1..............1....1..........1....
.......1..1..........1..........1...........11..............1....1..........1....

........2...2.....2............2......2.............2..2............2.........2..
........2...2.....2..........2..........2...........2..2............2.........2..
..2..........2............2.....2....2..............2....2...........2..2........
..2..........2............2.2............2..........2....2...........2..2........
..2..........2..........2.......2....2..............2....2.............22........
..2..........2..........2...2............2..........2....2.............22........

........3...3.....3............3......3............3...3............3..........3.
........3...3.....3..........3..........3..........3...3............3..........3.
..3..........3............3.....3....3.............3.....3............3.3........
..3..........3............3.3............3.........3.....3............3.3........
..3..........3...........3......3....3.............3.....3.............33........
..3..........3...........3..3............3.........3.....3.............33........

.....4..........4...4............4..4...........4.............4....4.....4.......

#VT: (2 6 6 1 3 18 18 8 6)
Cells: (8 11 22 46 61 66 77) nil nil (6 17 37 49) nil nil nil nil nil
SetVC: ( n4r1c6   n1r1c8   n1r2c2   n4r2c8   n1r3c4   n4r5c1   n1r6c1   n4r6c4   n6r6c6   n1r7c7
         n1r8c3   n1r9c5   n7r6c3   n8r6c5   n9r6c9   n5r6c2   n5r5c8   n5r4c4   n7r7c8   n8r8c8
         n9r3c8   n9r8c7   n9r4c2   n6r4c8   n3r9c8   n2r8c9   n2r9c1   n6r9c7   n3r1c9   n3r3c1
         n7r3c9   n1r4c9   n8r5c9   n3r7c2   n2r7c4   n3r8c6   n2r1c3   n3r2c4   n2r2c5   n8r2c7
         n6r2c9   n2r3c7   n3r4c3   n7r4c5   n2r4c6   n2r5c2   n6r5c3   n3r5c5   n1r5c6   n7r5c7 )
9 8 2   7 6 4   5 1 3
7 1 5   3 2 9   8 4 6
3 6 4   1 5 8   2 9 7
8 9 3   5 7 2   4 6 1
4 2 6   9 3 1   7 5 8
1 5 7   4 8 6   3 2 9
6 3 8   2 9 5   1 7 4
5 7 1   6 4 3   9 8 2
2 4 9   8 1 7   6 3 5

P.O.
 
Posts: 1731
Joined: 07 June 2021

Re: The hardest sudokus (new thread)

Postby champagne » Wed Aug 23, 2023 10:42 am

P.O. wrote:98.76.5..7.5..9....64.58...8.....4.....9...........32.6.8..5..4.7.64.....498.7..5 ED=11.9/1.2/1.2

SE is not reliable to hierarchize puzzles that are not in te1, 11.9 the highest SE rating involving nested chains of 300, 400 nodes for a puzzle that is in 4-template and solves with this one combination (1 2 3 4) doesn't seem reasonable.
[hidden][code]


For sure, a manual solver having heard of the TH pattern can solve it easily. It is the same with puzzles having a double JE .....
The SE rating just tells you that this resists to the set of rules used by Sudoku Explainer.
champagne
2017 Supporter
 
Posts: 7455
Joined: 02 August 2007
Location: France Brittany

Re: The hardest sudokus (new thread)

Postby mith » Wed Aug 23, 2023 3:27 pm

Yeah, a large number of the depth 3 puzzles have a trivial placement with TH (about a third of min-expands have a single guardian), and I would assume this is similar for depth 2 TH puzzles with high SER. Not a surprise the template approach finds them easier, given the nature of the pattern. (Nor is it a surprise that SE tends to need such large chains to crack it.)

Likewise, the T&E depth itself just tells us that these puzzles resist a T&E process.
mith
 
Posts: 996
Joined: 14 July 2020

Re:

Postby mith » Wed Aug 23, 2023 3:45 pm

1to9only wrote:
1to9only wrote:PGXplainer (from here) output:
Code: Select all
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4
1.85......32.6..5.65...2...8.......9.2.....3...9...1.......7.13.6..3.47....4..9.5 PG#0435 ED=10.0/10.0/9.4 ED=10.0/10.0/9.4

Edit: PGXplainer is PGE (for the Patterns Game) with my fix to lksudoku's fix to Chaining!

I've updated my previous post to mention that there is a version of PGE that has my fix to lksudoku's fix!! Download PGXplainer.jar from here.

Usage:
Code: Select all
java.exe -jar PGXplainer.jar --input=puzzles.txt --output=output.txt
or
java.exe -cp PGXplainer.jar sudoku.serate --input=puzzles.txt --output=output.txt


Posted in the wrong thread, oops.

I got the following on the first three puzzles in the expanded database (the ones related to Loki):

Code: Select all
java -Xrs -Xmx500m -cp PGXplainer.jar sudoku.serate --input=test-in
........1.....2.34.35.......62......7.3.25..885...67...7853....32..68...5.62.7.8. ED=11.9/11.9/3.4
........1.....2.......3..45.16.23...27.81.6..3.87.61...32.67..81.7.8....68....... ED=11.9/11.9/3.4
........1.....2.......3..45.16.23...27.8.61..3.871.6...32.68..718..7....6.7...... ED=11.8/11.8/3.4


Can you check these as well? They should all rate 11.8 if the morph-dependency is gone. (At least, I don't recall any uniqueness issue when I studied these previously.)

hendrik's 11.9s that I checked (the depth 3 ones, and the depth 2 discussed in the recent posts) stay at 11.9, though I never walked through any of them to look for morph dependency issues so that may just be right.
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby denis_berthier » Wed Aug 23, 2023 3:46 pm

.
All the known puzzles in T&E(3) have the tridagon pattern with guardians.
Having only 1 guardian is NOT the most favourable case, as it allows one placement and the pattern becomes as inexistent. Tridagons with more guardians are often much more useful to reduce the puzzle complexity, because they allow the use of chain rules based on them.

mith wrote:Likewise, the T&E depth itself just tells us that these puzzles resist a T&E process.

I have a strong objection to this.
The T&E-depth can't be compared with SER, the value of which is the result of obscure computations that have never been described in plain English.
On the contrary, being strictly in T&E(BRT, n) means the puzzle needs to use contradictions arising from n candidates when only Singles are used to get such contradictions. This is clear structural information about the puzzle.
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby champagne » Wed Aug 23, 2023 4:22 pm

mith wrote:Likewise, the T&E depth itself just tells us that these puzzles resist a T&E process.


As the {backdoor size x / T&E(n)} is not a solving property used by manual solvers, I would agree with this.
But it will be interesting to see if the family contains puzzles without the TH pattern. (I would bet "no")
champagne
2017 Supporter
 
Posts: 7455
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to General