The hardest sudokus

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

Postby m_b_metcalf » Thu Nov 08, 2007 6:20 pm

RW wrote:Nice one tarek! Interesting that it is not created in the same way as the most recent toughies in the "9+" thread, and it isn't fully diagonal. It actually breaks many "rules" that have been made up for creating tough puzzles. Apart from not being diagonal, there's also several given digits repeated in band 1 and stack 3.

Indeed, congratulations to tarek for breaking a record that has stood since February:!: Taking up RW's remark, I generated 101 puzzles with this pattern imposing what I still think of as the 'dml' rule, that all values are distinct in each band and stack. Of these, only one was not mimimal. The SE rating and frequency of the others are given in the table below (ignore the Index column).

Regards,

Mike Metcalf

Code: Select all
 Rating  Index  Frequency

  2.6      69       1
 
  3.4      56       3
 
  4.5      19       1
 
  6.6      71       1
  6.69     31       4
 
  7.1      11      19
  7.2      23      15
  7.3      26       4
  7.5      48       2
  7.6      93       1
 
  8.3      90       5
  8.4      86       9
  8.5      64       5
  8.9      41       7
 
  9.0      47      10
  9.1      53      10
  9.2      72       1
  9.4       9       2

 11.5       -       0
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8416
Joined: 15 May 2006
Location: Berlin

Postby ronk » Thu Nov 08, 2007 6:26 pm

RW wrote:Interesting that it is not created in the same way as the most recent toughies in the "9+" thread, and it isn't fully diagonal. It actually breaks many "rules" that have been made up for creating tough puzzles. Apart from not being diagonal, there's also several given digits repeated in band 1 and stack 3.

It seems pretty close to a "diagonal" to me.
Code: Select all
 . . 7 | . . . | . . 2
 . 8 . | . . 6 | . 9 .
 1 . . | . . . | 4 . .
-------+-------+-------
 . . . | 3 . 9 | . . .
 . . . | . . 5 | . . 1
 . 3 . | . 8 . | . 5 .
-------+-------+-------
 . . 2 | . 6 . | . . .
 . 9 . | 5 . . | . 8 .
 4 . . | . . . | 7 . .

This permutation has maybe a couple extra clues (in r5c9 and r7c5) and I think the center box is somehow strangely exempt from the "no repeat" rule.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby coloin » Thu Nov 08, 2007 6:52 pm

I was just about do do what ronk did.

The "Golden Nugget" trick perhaps is 4 clues in box 3, like m_b_metcalf's puzzle.

C
Last edited by coloin on Thu Nov 08, 2007 7:15 pm, edited 1 time in total.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby JPF » Thu Nov 08, 2007 7:30 pm

Congratulations, tarek !

ronk wrote:It seems pretty close to a "diagonal" to me.
Here are isomorphics of Golden Nugett and Easter Monster :

Golden Nugett :
Code: Select all
 . . . | . 1 . | . . 5
 . . . | . . . | . 3 9
 . . 3 | . . 5 | 8 . .
-------+-------+-------
 . . 8 | . . 9 | . . 6
 . 7 . | . 2 . | . . .
 1 . . | 4 . . | . . .
-------+-------+-------
 . . 9 | . . 8 | . 5 .
 . 2 . | . . . | 6 . .
 4 . . | 7 . . | . . .

Easter Monster :
Code: Select all
 . . . | . . . | . . 1
 . . . | . . 2 | . 3 4
 . . 4 | . . . | 5 6 .
-------+-------+-------
 . . 5 | . . 3 | 6 . .
 . 1 . | . 7 . | . . .
 8 . . | 9 . . | . . .
-------+-------+-------
 . . 6 | . . 4 | . 2 .
 . 9 . | 8 . . | . . .
 7 . . | . 1 . | . . .

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

Postby m_b_metcalf » Thu Nov 08, 2007 8:04 pm

JPF wrote:
ronk wrote:It seems pretty close to a "diagonal" to me.
Here are isomorphics of Golden Nugett and Easter Monster :

And here is an isomorph of Golden Nugget and of the original SE 11.4 (symmetric on the anti-diagonal):
Code: Select all
 . . . . . . . 3 9
 . . . . 1 . . . 5
 . . 3 . . 5 8 . .
 . . 8 . . 9 . . 6
 . 7 . . 2 . . . .
 1 . . 4 . . . . .
 . . 9 . . 8 . 5 .
 . 2 . . . . 6 . .
 4 . . 7 . . . . . Golden Nugget

 . 4 . . . . . 7 2 
 . . . . 1 . . . 6
 . . . . . . 5 . .
 5 . . . . 9 . . .
 . 2 . . 7 . . 1 .
 . . 8 3 . . . . .
 . . 3 8 . . . . .
 . 6 . . 2 . . . 4
 9 . . . . 5 . . . SE 11.4

Regards,

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

Postby RW » Thu Nov 08, 2007 8:04 pm

ronk wrote:It seems pretty close to a "diagonal" to me.

Yes, of course it's pretty close. As you said, it's also pretty close to not having any repeated givens within chutes and pretty close to the pattern used in the 9+ thread. But I still think it's worth noticing that this new record holder does not follow exactly any of the rules we've invented for tough puzzles so far. This shows that our searching methods haven't been perfect (even though the method used in the 9+ thread felt quite perfect) and that there still might be a lot harder puzzles that can be found with some completely different methods.

Btw. I just heard from a ravel that his program, the one originally used in this thread, gives this puzzle 22 points, which makes it number two on his subnets rating list.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby tarek » Thu Nov 08, 2007 9:19 pm

thanx everybody. I hope this would be a stimulus for more difficult puzzle & better understanding of the rating.

indeed it was close to halloween (& bonfire night), "Pumpkin Slasher" would have been a another good name:D

The generating method is not that special:
1. From diagonals with an empty box
2. we moved to 16 clue diagonal empty box psudopuzzles with the empty box flanked by 4 boxes containing 1 clue each then filling that empty box and minimizing.
3. I tried some neighbourhood searches as well with some success.

So between finding a pattern and fill boxes & a neibourhood search, I combined both approaches.

As ronk mentioned, there is a box that doesn't follow the rules, that is the box that we were filling then minimizing. I was trying to control that to have "more diagonal" clues or to have fewer clues - without much success until this showed up. I was targeting "no box with more than 3 clues" & 2 boxes with 1 or less clues each.
This puzzle is not an M3 but the Sx9 rating was so eccentric that warranted an SE rating (which will not be repeated:D ).

This also has a backdoor size 2 on all techniques in gsf's solver (which rang alarm bells too)

ravel in a PM to tarek wrote:Of course i was interested, what my old program says to it. In both runs it gives the same "solutions" with 22 points (others only differ in the last eliminations):
r6c5<>7(r5c5<>1,r6c6<>6,r6c2<>6,r4c2<>4,r1c7<>1),r2c5<>3,r8c5<>4(r8c3<>7,r1c3<>1,r1c4<>8),r7c9<>1,r3c4<>9,r8c6<>4,r7c1<>7,r1c7<>1
r6c5<>7(r5c5<>1,r6c6<>6,r6c2<>6,r4c2<>4,r1c7<>1),r2c5<>3,r7c4<>2(r1c7<>1,r3c8<>1),r7c6<>6,r7c6<>3,r8c4<>5,r3c4<>9,r7c1<>7,r1c7<>1

So from my subnets rating it is number 2 after Oceans puzzle (24), together with dml's, 3 points more than the top puzzles in the new lists.


tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby coloin » Thu Nov 08, 2007 9:39 pm

How long did SE take ?

AW will surely award the Jellies and Swords soon !

It might just prompt a rationalization of the rating game.

Here are the new M3 puzzles and several others not in gsf's list.
Permuted from a {-1+1} of gsfs list

Code: Select all
+---+---+---+
|..3|..6|...|
|.5.|.8.|1..|
|7..|2..|...|
+---+---+---+
|...|.9.|4.1|
|.14|...|95.|
|...|...|..8|
+---+---+---+
|.9.|.4.|..5|
|..2|..7|...|
|6..|3..|...|
+---+---+---+ SE=11.0 # coloin-08/11/07-1


Code: Select all
# ..3..6....5..8.1..7..2.........9.4.1.14...95.........8.9..4...5..2..7...6..3..... # coloin-08/11/07-1
# ..3.5....4....9....8.2....1.1.8...7...5..3...9...4.......6....7.7.....18......32. # coloin-08/11/07-2
# ....5...9...7...2...8..16...41.6.3...6........85..4....3...84.....9...5.....2...7 # coloin-08/11/07-3
# .2...6...4...8......91..5....5....3.....9...6...3..95...19...7.8....4....6..2.... # coloin-08/11/07-4
# .2.4.......6.8....7....3..5.4..6....3....7.9...82.....5......32.....185.......6.. # coloin-08/11/07-5
Breaking in to gsf's top 10
# ..3....8..5....1..7....2..42...97......86.........4..7..8...3..6...4...2.1.....5. # coloin-08/11/07-6
# .23...7...5.......78...3.......6..9.3....82.....5....1..4..28......9...5...1...6. # coloin-08/11/07-7

Code: Select all
SE-11.0 SX9- 982 # ..3..6....5..8.1..7..2.........9.4.1.14...95.........8.9..4...5..2..7...6..3..... # 95203 FNP C22.m/M3.1494.355 
SE-10.8 SX9-1526 # ..3.5....4....9....8.2....1.1.8...7...5..3...9...4.......6....7.7.....18......32. # 97542 FNP C21.m/M3.1141.465 
SE-10.5 SX9-1042 # ....5...9...7...2...8..16...41.6.3...6........85..4....3...84.....9...5.....2...7 # 16513 FNP C22.m/M3.1902.279 
SE- 9.9 SX9-1049 # .2...6...4...8......91..5....5....3.....9...6...3..95...19...7.8....4....6..2.... # 25347 FNP C21.m/M3.1096.484 
SE- 9.3 SX9- 386 # .2.4.......6.8....7....3..5.4..6....3....7.9...82.....5......32.....185.......6.. #  1589 FNP C21.m/M3.1766.300
 
SE- 9.6 SX9-1103 # ..3....8..5....1..7....2..42...97......86.........4..7..8...3..6...4...2.1.....5. # 95684 FNP C21.m/M2.1.190269 
SE-10.9 SX9-1531 # .23...7...5.......78...3.......6..9.3....82.....5....1..4..28......9...5...1...6. # 95569 FNP C21.m/M2.4.14760   
C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby JPF » Fri Nov 09, 2007 1:17 am

tarek wrote:I hope this would be a stimulus for more difficult puzzle & better understanding of the rating.

coloin wrote:It might just prompt a rationalization of the rating game.

Here I wrote:...
Like ravel, gsf, AW and others I agree that it's time to think about what we are really looking for in term of rating.
A public program (or at least a common methodology) should be set up accordingly to evaluate quickly these very hard puzzles and to find what we are looking for in them.
...

I think we have to be fair with gsf's program which is the only one open to everybody, set up recently, quick and which is not a black box.

I'm still not clear why a puzzle is said to be harder than an other.
Is it clear in the solver-people's mind ?
If so, why don't you open a thread on this subject ?

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

Postby coloin » Fri Nov 09, 2007 10:39 pm

I think we have to be fair with gsf's program which is the only one open to everybody, set up recently, quick and which is not a black box.

Indeed, although when other rating programs consistantly rate a puzzle higher one will ask questions of it. The "Easter Monster" was consistently rated highly by almost all rating programs. Having said that about the sudoku -q1, it does seems to make sense. Maybe the solving technique qualifications of the M2/M3 need to be tweaked. [Make it easier to rate M3]

Although I suppose the generation of the "hardest" puzzles is academic to almost all potential human solvers, I think the interesting aspect will be what makes the "Golden Nugget" the hardest puzzle [if indeed it is at present].

Here are some related puzzles [with different box 3 clues] which have high SX9 values.

Code: Select all
SX9-1450 ,  .......38....1...5..3..5.9...8..9..6.7..2....1..4.......9..8.5..2....6..4..7.....  GNsibling6     - 10.6
SX9-2164 ,  .......35....1..89..3..5.....8..9..6.7..2....1..4.......9..8.5..2....6..4..7.....  GNsibling5     - 10.6
SX9-2206 ,  .......93....1..85..3..5.....8..9..6.7..2....1..4.......9..8.5..2....6..4..7.....  GNsibling4     - 10.6
SX9-2355 ,  .......85....1..39..3..5.....8..9..6.7..2....1..4.......9..8.5..2....6..4..7.....  GNsibling3     - 10.6
SX9-2401 ,  ........3....1..85..3..5.9...8..9..6.7..2....1..4.......9..8.5..2....6..4..7.....  GNsibling2     - 10.5
SX9-2584 ,  ........5....1..83..3..5.9...8..9..6.7..2....1..4.......9..8.5..2....6..4..7.....  GNsibling1     - 10.6
SX9-3792 ,  .......39....1...5..3..58....8..9..6.7..2....1..4.......9..8.5..2....6..4..7.....  Golden Nugget  - 11.5
C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby JPF » Sat Nov 10, 2007 1:31 am

coloin wrote:Although I suppose the generation of the "hardest" puzzles is academic to almost all potential human solvers, I think the interesting aspect will be what makes the "Golden Nugget" the hardest puzzle [if indeed it is at present].

Indeed, although the hardest known puzzle for SE is :
Code: Select all
100200000300000400000005600050006000000030010000700020060040300000100000000000080

Golden BUG:D

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

Postby tarek » Sat Nov 10, 2007 10:26 am

coloin wrote:How long did SE take ?

5-6 hours overnight (AMD64 3.20 1GB RAM)

JPF wrote:although the hardest known puzzle for SE is :
Code: Select all
100200000300000400000005600050006000000030010000700020060040300000100000000000080

Golden BUG:D

:D, SE author should be made aware, what prevents SE current ratings from being over/under estimated with such a flaw?

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby ttt » Sat Nov 10, 2007 4:40 pm

Wow... 11.5 ! you know, in Vietnam have just man Solved Arto Escargot ... the first last year
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby gsf » Thu Nov 15, 2007 10:05 am

finally got some time to respond

I collated recent puzzles and added them to q1-taxonomy-2007-11-11.dat -- thanks

the high suexrat9 ratings are a neat achievement
suexrat9 is based on a backtracking solver that uses singles to propagate constraints
the rating counts nodes visited during the backtrack search
its DLX based, so the node count will be much higher than some non-DLX based solvers (like mine)
it washes the inherent bias in the basically deterministic search algorithm
(it uses the time honored search strategy of asserting the most constrained variables first)
by running the node count search multiple times on pseudo random permutations of the input puzzle

the -q1 rating is also based on singles (but has a fallback to add locked candidates for the hardest of the hardest puzzles)
it differs from suexrat9 in that it makes all propositions, in order of tuple degree
(e.g. bivalue first, then trivalue etc., stopping after the lowest degree that advances the solution),
rather than a random sample
the hardest puzzles require multiple rounds of nested propositions, with small numbers
of placements/eliminations for each round of propositions

I believe that the aesthetic rating we are aiming at is related to the statistics gathered by
the P constraint method used by -q1

the ratings output by my solver are basically polynomial functions of the counters accumulated
by the constraint methods applied

that function can be tweaked with the -R option to meet our collective ideas of hardness

running -v2 -q1 on the golden nugget shows that it is in a class by itself in the q1 taxonomy
Code: Select all
propositions 137484  solutions   4  contradictions   0  iterations 334982  girth  22  degree   5  nesting 2

it only yields to nested propositions
out of 100K of them only 4 provided placements/eliminations that advance the solution
in this case it was 4 actual solution paths
degree 5 means that bivalue 3-value .. 4-value propositions produces no info
only 5-value/5-location cells did, and only 4 pairs at that
girth 22 means that some of the singles propagations after propositions required 22 iterations
to reach steady state
girth is roughly analgous to chain/cycle length

the -v2 numbers above correspond to the P portion of the Q1stats field in q1-taxonomy.dat
for the golden nugget its
Code: Select all
P1.2.137135.4.0.334061.22.5.2.236

for comparison easter monster required 9 rounds of 400K total propositions at degree 5 girth 25
using singles and locked candidates (V3 in the Q1stats field)
Code: Select all
P9.16.467645.2.20.1697341.25.5.2.238


maybe the librarians/collators among us can pick out the puzzles that seem out of whack among the different ratings
then we can look at the P stats to see if they provide enough info to make sense out of the discrepancy

I'm not saying that the answer must be in the P constraint counts
just that its in a form that can be experimented
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Mon Nov 19, 2007 1:28 am

Thanks for that valuable contribution, .....I have extended a search, no doubt as tariq has, I have very many more puzzles and i have a few comments to make before I publish my results !

The three ratings programs i have used are, SE, sx9 and gsf's -q1. I have now [even more] reservations regarding the value of SE and the specificity of sx9.

And then there are "pencilmarks"..................it is interesting that gsf's rating program is following along the lines of the AIC and the Red/Green discussions on the "Eureka" forum.

SE
apart from its slowness, it is debatable if it actually finds the hardest step needed in a puzzle. We have seen the EM puzzle succumbing to a clever elimination.

sx9
up to last week the highest dukuso "suexrat9" score was around 2150 [tariq's ultra-203].

This has been smashed by the GN [Golden Nugget] puzzle.

However, I have generated now many over this value, and at least 10 puzzles over +3000.

They dont come out as well as the GN, and gsfs previous post explains why !

I think this come down to having more "pencilmarks", and unless you attack the puzzle at the correct spot - a bi-value cell, or a "bi-locus" clue in a box [not sure of correct term here] - the puzzle appears harder to crack. The puzzles all tend to have 3 clues in a chute, and also one generated clue - but still rated highly by suexrat9. There tends to be a high observed number of pencilmarks remaining.

If the suexrat9 works essentially by solving 100 isomorphs of the puzzle and averaging the time taken - I was wondering if it should be based on the time taken for the "easist" 25% ????

BTW what is the command line of gsf's SX version:?:

And finally, gsfs program -q1.

I have 100 new M3 puzzles

I have over 150 new puzzles with >95000

None are higher than 98500, and the ones I looked at havnt done what the GN puzzle did with -v2.

The GN puzzle isnt M3, and I understand that therefore has 4 pairs of clues which when added make it solved relativly easily. The M3 guality doent ensure an ultra hard puzzle as we have seen.

The "pencilmarks"
The GN puzzle has no bi-value cells and a few bi-locus boxes [I dont think a puzzle can be made without these ?].

Starting from a valid puzzle, initially there are 9 pencilmarks in each empty cell. [1 is correct, 8 will be incorrect !]

These will be reduced by the simple "rules" of sudoku. Up to what point are we unable to eliminate the "incorrect" pencilmarks I wonder.

The remaining "pencilmarks" are the preposition clues - added in turn by gsf's -q1 function.

As I understand it [I could be wrong however] the GN puzzle when 2 [ ? targeted] "incorrect" preposition clues are added - it doesn't bring about a contradiction that often - [although there would be one if the solving process could be extended]. And this is possibly why gsfs -v2 program rings the alarm bells.

The M3 puzzles don't have 2 "correct" clues which make the puzzle "easy", but do they have higher percentage of the [targeted] proposition pairs of "incorrect" clues giving a "visable" contradiction ?

If this is true then it may be another reason why GN is our current "hardest" puzzle.

Puzzles to follow in 48 hours.
coloin
 
Posts: 1638
Joined: 05 May 2005

PreviousNext

Return to General