The hardest sudokus

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

Postby RW » Mon Nov 20, 2006 12:22 pm

Nice puzzles tarek! I like the new patterns as they have only 21 given clues. The Aries could also be called Mjolnir as it reminds me of the hammer of Thor.:)

I had a look at Daemonicus #18, SE 9.9. Adding up the ratings for all steps before the first placement in explainer gives 463.8, including 7 steps rated 9.9! Now that's a real pearl! Gonna be interesting to see how ravel's program handles these. Btw. If someone wish to crack this puzzle with propositions, I don't recommend starting from box 7. Not a single candidate can be eliminated from that box using propositions with SSTS.:D In box 8 two eliminations can be found, in box 9 three. Most possible eliminations in the starting grid seems to be in the empty box (from r1c3 5/7 candidates can be eliminated). Wonder why this is... Box 7 is very hard to make eliminations in, even after making all possible eliminations with SSTS propositions in boxes 1, 2 and 3 there is still no available elimination in box 7.

If you want to reach the solution fast and don't care about the aesthetic value or proving uniqueness of your solution, one way to solve it would be to make the available eliminations in r3c1, r3c4 and r3c7 (7 eliminations) after which r9c9=1 is a backdoor with one hidden pair.

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

Postby RW » Mon Nov 20, 2006 1:32 pm

I wrote:The Aries could also be called Mjolnir as it reminds me of the hammer of Thor.

Upon closer inspection, maybe this is a better pattern for Mjolnir:

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

SE: 9.2, gsf: 99416, suexrat: 325

Don't expect it to reach the list, but maybe some of the more efficient puzzle generators around can find some harder with this pattern.:)

Edit: Replaced it with a harder one, this was the original:
Code: Select all
.....27......5..3...41....6..1.....4.8.....6.3.....5..5....42...6..9..8...78....1



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

Postby Ocean » Mon Nov 20, 2006 2:54 pm

RW wrote:Upon closer inspection, maybe this is a better pattern for Mjolnir: [...]
maybe some [...] can find some harder with this pattern.

The "Mjolnir" pattern is isomorph to the six puzzles with a six-mutable cell . The search for hard puzzles in this pattern is not yet finished. No ultra hard puzzles found so far, but maybe a few things of interest...

001002000020030000400500600006000007010000080900000500007008003030090010500700400 # gsfr=99708 ER=9.5
001002000030040000500100600007000008090000040200000100003006005040090080100700200 # gsfr=99696 ER=9.5
001002000030040000500100600007000003040000080900000100002003006080050040100700900 # gsfr=99687 ER=9.4
001002000020030000400100500005000004060000070800000100008007003030020060100500900 # gsfr=99597 ER=9.4
001002000030040000500600700007000008020000090100000500003008004040010060600500100 # gsfr=99595 ER=9.4
001002000020030000400100500006000001030000070800000600002009004070080030600500800 # gsfr=99578 ER=9.4
001002000020030000400100500005000004030000060700000100002008006060090080100500700 # gsfr=99546 ER=9.2
001002000030040000500100600007000008020000040800000100008006003040090020100700800 # gsfr=99536 ER=9.2
001002000020030000400500600006000007030000080100000500002009008080010090500600400 # gsfr=99529 ER=9.2
001002000030040000500100600006000005020000070800000900009003004040070020100600800 # gsfr=99527 ER=9.9
001002000020030000300400500004000001060000070800000300002006007070080060400500900 # gsfr=99496 ER=9.2


Here is a minimal 21 (reduced from the gold list pattern, and also a reduction of the Mjolnir-equivalent pattern):
Code: Select all
# M21.
# gsfr=99519
# ER=9.9
 *-----------*
 |..1|..2|...|
 |.3.|.4.|.5.|
 |6..|7..|8..|
 |---+---+---|
 |..5|...|..1|
 |.9.|...|.4.|
 |8..|...|3..|
 |---+---+---|
 |..4|..1|..2|
 |...|.5.|.6.|
 |...|9..|7..|
 *-----------*

Another minimal 21 - reduced from the gold list pattern. This pattern bears some similarity to tarek's Aries and Daemonicus - but is not isomorph to any of those two patterns.
Code: Select all
# M21
# gsfr=99366
# ER=9.5
 *-----------*
 |..1|..2|...|
 |.3.|.4.|.5.|
 |6..|7..|8..|
 |---+---+---|
 |..5|...|..9|
 |.6.|...|.4.|
 |7..|...|3..|
 |---+---+---|
 |..9|..3|..1|
 |.4.|.5.|...|
 |...|8..|7..|
 *-----------*
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby tarek » Tue Nov 21, 2006 2:46 am

RW wrote:Nice puzzles tarek! I like the new patterns as they have only 21 given clues. The Aries could also be called Mjolnir as it reminds me of the hammer of Thor.:)
Thanx, I'm glad you liked them.....I don't like the Aries pattern myself, but it provided an alternative in a non creative hour, may be the hammer of Thor should find me instead of me finding it:D

RW wrote:I had a look at Daemonicus #18, SE 9.9. Adding up the ratings for all steps before the first placement in explainer gives 463.8, including 7 steps rated 9.9! Now that's a real pearl!
gsf's rating was not kind to it though & therefore is bottom in the list.....The SE rating was unpredictable again & I could have passed over it if the suexr was not high....

The 21 clue pearly diagonals are not just rare... but also suffer from the fact that they tend to become easier to crack fro such powerful solvers, I think it has to do with "too much unblocked information", that is why I think that the hardest puzzle should have 22-23 clues.... That is a speculation.

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

Postby ravel » Tue Nov 21, 2006 10:21 am

RW wrote:I had a look at Daemonicus #18, SE 9.9... Gonna be interesting to see how ravel's program handles these.
I tried it, after 3 runs the best solution needs 10 steps:
r7c5<>6, r7c9<>6, r9c5<>1, r1c3<>8, r2c1<>9, r5c6<>3, r9c6<>3, r5c8<>6, r9c2<>3, r2c4<>2

In the moment i am experimenting with a quickly written extension, which i hoped will allow me to solve the hardest. But it is too slow now and i have to see, if it does unnecessary things or if this is a wrong way. In the latter case i would need some days to improve it, but i will not have the time in the next weeks.
ravel
 
Posts: 998
Joined: 21 February 2006

need help with gsfr and seuxr

Postby dml » Wed Nov 22, 2006 7:32 pm

tarek wrote:7....39...9..5......86....1..1.....2.2.....8.5.....3..9....47......3..5...61....4 gsfr=99536 seuxr=563 SE=9.9

tarek


Where do you find the codes gsfr and seuxr and SE?

What is the best way to evaluate the difficulty of a sudoku grid?

Are you confident that those programs are correct in their evaluation?
Why using 3 programs?

Is there a maintained list of hardest gsfr , seuxr ?

thanks
Patrick.
dml
 
Posts: 34
Joined: 12 November 2006

Re: need help with gsfr and seuxr

Postby RW » Wed Nov 22, 2006 8:13 pm

dml wrote:Where do you find the codes gsfr and seuxr and SE?

What is the best way to evaluate the difficulty of a sudoku grid?

Are you confident that those programs are correct in their evaluation?
Why using 3 programs?

Is there a maintained list of hardest gsfr , seuxr ?

Ravel explained how to get the ratings here. The three programs are used, because all have slightly different approaches to the rating system. Some puzzle found extremely hard for one rating can be found very easy by another. If all three find the puzzles extremely hard, then you can expect the result to be quite reliable. I guess this also answered the question about the best way to evaluate difficulty, there's several different approaches, all have their ups and downs. The best way would of course be to consider all factors that affect difficulty, but that's impossible, because difficulty is in the eye of the beholder. As with the programs, any two human solvers wouldn't have the same approach to solve the same puzzle either and therefore the experience of difficulty varies from person to person.

Ravel did keep a list of the top 10 hardest for all rating systems on the main post of this thread, but I can't see it anymore. I think the current records are gsf: 99960, suexrat: 1630 (slight variation each time you use the program), ER: cannot solve using logical techniques only.

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

Re: need help with gsfr and seuxr

Postby dml » Wed Nov 22, 2006 10:17 pm

RW"][quote="dml wrote:
Ravel did keep a list of the top 10 hardest for all rating systems on the main post of this thread, but I can't see it anymore. I think the current records are gsf: 99960, suexrat: 1630 (slight variation each time you use the program), ER: cannot solve using logical techniques only.

RW


Still not found gsfr and seuxr , I see no clear indications on http pointeurs where to load the files "gsf" or "gsfr" . Probably better to have the lattest versions.

What is the difference between gsf and gsfr ?

Also I see sometimes notation [99960 Y] , what Y means?
I ask the question because one guy claims to have found the hardest sudoku. This seems to me not acceptable claim if there is not an accepted way to quantify the difficulty.
It would be nice to have one program to evaluate the human difficulty to resolve a grid. Are there some people working on this problem?
dml
 
Posts: 34
Joined: 12 November 2006

Postby RW » Wed Nov 22, 2006 11:21 pm

dml wrote:Still not found gsfr and seuxr , I see no clear indications on http pointeurs where to load the files "gsf" or "gsfr" . Probably better to have the lattest versions.

There is sno such program as "gsf". There is a program called "sudoku" that is made by gsf and can be downloaded here. Please read ravel's post for how to use it. In that same post there is a link to a page where you can download dukuso's program, called suexrat9. There is no difference between 'gsf' and 'gsfr', I think some people only use gsfr as short for 'gsf rating'.
dml wrote:I ask the question because one guy claims to have found the hardest sudoku. This seems to me not acceptable claim if there is not an accepted way to quantify the difficulty.

My advice, enter it into Sudoku Explainer, press 'F9', if it gives you a rating (might take several minutes), then it isn't the hardest sudoku. If it cannot rate it, try gsf's program with these options:
-B -q'FNP(FNBTHWX)V(8)-G' -f%Q
if it gives you a rating, then it isn't the hardest sudoku. If it cannot rate it, try again with these options:
-B -q'FNP(FNBTHWXY)V(9)-G' -f%Q
if it gives a rating < 99960, then it isn't the hardest. If it gives a rating > 99960, or doesn't rate it at all, then it probably is the hardest known.

dml wrote:Also I see sometimes notation [99960 Y] , what Y means?

The Y makes the difference between the two options for gsf's program I gave you. The first one uses techniques up to coloring within the propositions (forcing nets), the second one has a Y added to the line, which means that it uses techniques upto multicoloring within the propositions.
dml wrote:It would be nice to have one program to evaluate the human difficulty to resolve a grid. Are there some people working on this problem?

Many have tried, many have succeeded quite well when it comes to puzzles that the normal human usually solves. The rating gets a lot harder when you start discussing monster puzzles like the one in this thread.

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

Postby tarek » Thu Nov 23, 2006 12:22 am

This thread (28 pages of it until now) should have everything you need dml..... RW has really explained everything........... I would suggest that you would give it 10 minutes & go through the thread from the start .......... Ravel's 1st post is extremely informative ..... several other posts are also informative... & would answer all that you're questioning...

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

Postby merallas » Thu Nov 23, 2006 10:59 am

In order to test my program (http://homepages0ipact0nl/~allersma/all_lab0htm#soft ) I put all the sudokus of this site, which are written as oneliners, in a batchfile (total of 1466). A special version of the program has been equiped with an interface to handle this batchfile automatically. It appeared that all the sudokus could be solved by the program. Only four sudokus need the most powerful technique. The first two, however, are clones of a puzzle I have met earlier. It seems not to be extreme difficult ones.

708000300000601000500000000040000026300080000000100090090200004000070500000000000
102000300000405000600000000070000048300020000000500090090800007000010600000000000
000800070000010900000004001100006004080050000005700030070000000400002006003500080
500004300070020000008100006009000007010000080400000200900003700000040050006700001

Due to the gambling option in the program, sudokus which are indicated as very difficult by my program are not necessarily very difficult. Therefore I like to know the opinion of the specialists about the last two sudokus.

merallas
merallas
 
Posts: 39
Joined: 26 September 2006

Postby dml » Sun Nov 26, 2006 7:55 pm

RW wrote:My advice, enter it into Sudoku Explainer, press 'F9', if it gives you a rating (might take several minutes), then it isn't the hardest sudoku. If it cannot rate it, try gsf's program with these options:
-B -q'FNP(FNBTHWX)V(8)-G' -f%Q
if it gives you a rating, then it isn't the hardest sudoku. If it cannot rate it, try again with these options:
-B -q'FNP(FNBTHWXY)V(9)-G' -f%Q
if it gives a rating < 99960, then it isn't the hardest. If it gives a rating > 99960, or doesn't rate it at all, then it probably is the hardest known.
RW


RW
First I want to thank you for the help
I tried -B -q'FNP(FNBTHWXY)V(9)-G' -f%Q on the list top95 and find no sudoku with note >= 99940
Where is a list of top grids?

Also I tested AL ESCARGOT it reachs 99951

And finally I found some grids that seems to hang with this setting
Then what program should be taken as reference , since it seems "gsf" can solve AL ESCARGOT and Explainer cannot.
I suppose Explainer miss a technique used by gsf and probably the opposite.

Did somebody made statistics on frequency to find "99920+" vs "99900+"?
seems to me that 1/3 of 99900+ are greater than 99920
1 every 30 "99920+" is greater than 99930
1 every 15 "99930+" is greater than 99940
1 every 15 "99940+" is greater than 99950

I assume 1 every X is greater than 99960
X is probably in [10-30] and so on

I propose this one for now that reaches 99966

500600100
002004000
000007090
009080200
030000040
007100006
010200500
000030070
006900000

This one can probably be added to best grids
Would be nice to have an command line version of Explainer
Patrick
dml
 
Posts: 34
Joined: 12 November 2006

Postby gsf » Sun Nov 26, 2006 8:32 pm

dml wrote:And finally I found some grids that seems to hang with this setting
Then what program should be taken as reference , since it seems "gsf" can solve AL ESCARGOT and Explainer cannot.
I suppose Explainer miss a technique used by gsf and probably the opposite.

download the latest gsf solver and
Code: Select all
-q hardest
should work on all of the hardest puzzles
if this solver hangs on any puzzle(s) please post the puzzle(s)
thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby dml » Sun Nov 26, 2006 8:58 pm

gsf wrote:
dml wrote:And finally I found some grids that seems to hang with this setting
Then what program should be taken as reference , since it seems "gsf" can solve AL ESCARGOT and Explainer cannot.
I suppose Explainer miss a technique used by gsf and probably the opposite.

download the latest gsf solver and
Code: Select all
-q hardest
should work on all of the hardest puzzles
if this solver hangs on any puzzle(s) please post the puzzle(s)
thanks


one exemple is:

060200001
900030000
000005700
300010600
700000050
002400009
001006002
000700003
050009000

I used as recommended -B -q'FNP(FNBTHWXY)V(9)-G' -f%Q
Is not it a valid way to evaluate hard sudokus?

As new in the list I expected to find a standard reference way to evaluate the sudokus.
I understand how this can be a hard problem but since many people work on that since quite a while I expected some consensus.
And logically an agreement on best program to evaluate, for me it can only be a command line program otherwise we cannot test extensively it with millions of sudokus, make statistics etc..

Is AL escargot the hardest sudoku in the world?
And why ? Just because Explainer does not find a logical solution?

Is your program exhaustif in term of know technics to solve the sudoku?
thanks
dml
 
Posts: 34
Joined: 12 November 2006

Postby gsf » Sun Nov 26, 2006 11:10 pm

dml wrote:I used as recommended -B -q'FNP(FNBTHWXY)V(9)-G' -f%Q
Is not it a valid way to evaluate hard sudokus?

the option above was a workaround until I reposted my solver
its reposted and with that version
-q hardest should rate all of the puzzles posted in this thread

note that there is a difference between solving and rating
most of the solvers referencesd on this forum are pretty solid
but rating is still in flux and certain input data and options may illustrate that
even for the solid solvers

thanks for the posted puzzle
along with the workaround options
it coaxes bad behavior in the Y cycle method that is usually not hit
because other methods (disabled by the workaround) usually solve first
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to General

cron