The hardest sudokus

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

Postby Mauricio » Fri Jan 19, 2007 11:05 pm

What? The second sudoku with gsfr ~99500 had 14 points with your rating? It was the highest rated with your rating and the lowest rated with gsf.

I see there is little correlation between your approach and gsf.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby ravel » Sat Jan 20, 2007 11:36 am

There have always been puzzles, where the 2 ratings differ much.
As i understood it, gsf's rating tries "easier" steps before harder ones and uses "batch moves", i.e. applies all possible eliminations with same hardness at once.
My program only differs between very easy (basic) steps, contradiction chains of arbitrary length (=hardness) and those using subnets. I think, gsf's program distinguishs more levels of hardness.
So puzzles, that e.g. can be cracked with a few hard steps without applying possible easier ones, or those where only a few out of the batch moves are needed to solve it, will be rated lower by my program.
If almost all of the batch moves are needed, my rating will be higher.

But on the average i find, that there is much correlation between the ratings.

[Added:] In this case also note, that the -X rating (without using backdoor cells) is higher: 99690 .
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ravel » Thu Jan 25, 2007 10:08 am

In dml's last list with 20 puzzles 8 of them were equivalent to earlier sent puzzles (lines 4, 13, 16, 17, 18, 20, 21, 22). Interestingly with line 4 (dml 7/07) he has refound Ocean's present for gsf.

I have added swordfish and turbot fish now. Unfortunately (and not surprising) i did not find a way to get the best results for all puzzles in reasonable time. When i change the parameters, there are always some puzzles, for which then longer solutions are produced.

Here is the updated list of all 19+ points puzzles, where i took the best of two runs:

24 11.2 000001020300040500000600007002000001080090030400000800500002000090030400006700000 Ocean's New Year's present for RW
22 11.5 000000039000001005003050800008090006070002000100400000009080050020000600400700000 tarek Golden Nugget
22 11.1 003000009400000020080600100200004000090800007005030000000900800000005030070010006 dml 1/07
21 10.6 100300000020090400005007000800000100040000020007060003000400800000020090006005007 dml161
21 10.4 100007000020030500004900000008006001090000020700000300000001008030050060000400700 dml45
20 10.8 003400080000009200000060001007010000060002000500800040010000900800000030004500007 dml 3/07
20 10.7 000001020300040500000600007002000006050030080400000900900002000080050400001700000 Ocean's Christmas present for gsf
20 10.7 003900000040070001600002000800000002070050030009000400200001008000040050000600900 dml12
20 10.5 100007000020080000004300500005400001080000020900000300000005007000020060003100900 dml48
19 11.4 600000002090400050001000700050084000000020000000305040200000600030009080007000001 coloin-04/13-1600 (coloin04-10)
19 11.4 300000900070001050002000004000076010000305000060810000400000200050600080009000003 tarek071223170000-103
19 11.1 000008007030090040005000100020609000004020000000003060001000800040060090700000005 tarek071223170000-008
19 11.1 600000002010080040007000900030804000100000000000035080000009600050040010000200007 tarek071223170000-009
19 10.8 100007000090050020003000400080005000600090000000802060004000100020060050700000003 tarek071223170000-025
19 10.6 002900000030070000500004100008000002090000030600500400000003008000060070100200500 dml52
19 10.6 000001020300040500000600007001000006040080090500000300800002000050090400006700000 Ocean's New Year's present for ravel #2
19 10.7 003400000050009200700060000200000700090000010008005004000300008010002900000070060 dml 5/07
19 10.7 000001020300040500000600001001000007050030040800000900400002000090050800006700000 Ocean's New Year's present for ravel #1
19 10.6 400009000030010020006700000001000004050200070800000600000004008070030010000500900 dml1
19 10.6 100000002090400050006000700050964000000800000000035040700000600030009080002000001 coloin-04/13-1601 (coloin04-10)
19 10.4 900004000050080070001200000002600009030000040700000500000009002080050030000700600 dml8
Last edited by ravel on Mon Jan 07, 2008 1:29 pm, edited 1 time in total.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby m_b_metcalf » Tue Feb 06, 2007 8:36 pm

ravel wrote:There have always been puzzles, where the 2 ratings differ much.

JPF has suggested that this might be of interest (from the Patterns Game thread). I have only SE for rating. It requires about 30 steps before a single cell is solved by it.
Code: Select all
 7 . . . . . . . 3
 . 9 . 4 . . . 8 .
 . . 1 . . . 5 . .
 . 8 . 9 . 5 . . .
 . . . . 3 . . . . Pearl 15 x 9.6, then up to 9.8
 . . . 2 . 8 . 6 .
 . . 5 . . . 1 . .
 . 6 . . . 9 . 4 .
 3 . . . . . . . 7

Regards,

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

Postby ravel » Wed Feb 07, 2007 1:30 pm

Thanks,
it rates 11 points, one solution found is
r2c3<>3(r2c1<>5,r8c4<>5,r1c8<>1),r9c3<>4,r1c2<>4,r1c2<>5,r1c8<>9.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby m_b_metcalf » Wed Feb 07, 2007 2:00 pm

ravel wrote:Thanks,
it rates 11 points, one solution found is
r2c3<>3(r2c1<>5,r8c4<>5,r1c8<>1),r9c3<>4,r1c2<>4,r1c2<>5,r1c8<>9.

Thanks. You may have seen that JPF changed 3 of the values, uppping the ante to 10.7:
Code: Select all
 7 . . . . . . . 3
 . 2 . 4 . . . 8 .
 . . 1 . . . 5 . .
 . 8 . 9 . 5 . . .
 . . . . 3 . . . .
 . . . 2 . 8 . 6 .
 . . 5 . . . 1 . .
 . 4 . . . 9 . 2 .
 3 . . . . . . . 7      SE=10.7


Regards,

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

Postby ravel » Wed Feb 07, 2007 4:47 pm

This one has 12 points:
r7c8<>3(r8c5<>5,r2c1<>5,r1c8<>1),r5c8<>5,r9c7<>9,r7c2<>6,r8c4<>5,r1c6<>1
ravel
 
Posts: 998
Joined: 21 February 2006

Postby m_b_metcalf » Wed Feb 07, 2007 5:14 pm

ravel wrote:This one has 12 points:
r7c8<>3(r8c5<>5,r2c1<>5,r1c8<>1),r5c8<>5,r9c7<>9,r7c2<>6,r8c4<>5,r1c6<>1

Ravel, thanks we're getting there slowly. Could I ask you to look at my 6:11 pm posting on the Patterns Game thread too?

Thanks,

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

Postby JPF » Wed Feb 07, 2007 5:15 pm

m_b_metcalf wrote:You may have seen that JPF changed 3 of the values, uppping the ante to 10.7:
Code: Select all
 7 . . . . . . . 3
 . 2 . 4 . . . 8 .
 . . 1 . . . 5 . .
 . 8 . 9 . 5 . . .
 . . . . 3 . . . .
 . . . 2 . 8 . 6 .
 . . 5 . . . 1 . .
 . 4 . . . 9 . 2 .
 3 . . . . . . . 7      SE=10.7


Thanks Mike for posting the puzzle here in this thread.
Thanks ravel for the rating.

a bit surprised by the 12 note when I remember the time spent by S.Explainer to give its 10.7 rating and the strange (and unusual noise) of my PC during 20 minutes:D
I even don't speak about the proposed solution (?)

PS :
oups ! Mike is just breaking the bank with his 11.4 + !
see here
Code: Select all
 5 . . . . . . . 9
 . 2 . 1 . . . 7 .
 . . 8 . . . 3 . .
 . 4 . 7 . 2 . . .  SE at least 11.4
 . . . . 5 . . . .
 . . . . . 6 . 1 .
 . . 3 . . . 8 . .
 . 6 . . . 4 . 2 .
 9 . . . . . . . 5


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

Postby ravel » Wed Feb 07, 2007 8:05 pm

Wow,
congratulations for the new Explainer record, Mike.

My rating is not so exciting, 16 points, but for the first hard step it needs 6 subnets (!), which i think is a record, too.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby m_b_metcalf » Wed Feb 07, 2007 11:16 pm

ravel wrote:Wow,
congratulations for the new Explainer record, Mike.

My rating is not so exciting, 16 points, but for the first hard step it needs 6 subnets (!), which i think is a record, too.


Thanks. This was a joint effort with JPF supplying the pattern as well as the incentive to go ever higher (and we're not done yet as he still leads in the challenge with only six days to go). Also, I built some conjectures of dml into my algorithms.

Can someone give me the gsfr rating? I can't run it on my PC.

Regards,

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

Postby JPF » Thu Feb 08, 2007 11:52 am

m_b_metcalf wrote:Can someone give me the gsfr rating? I can't run it on my PC.

Mike,
ravel made a good summary on the rating programs here
ravel wrote:Sudoku Explainer is the only program i know so far, that can solve the hardest puzzles in human readable (and graphical) form. It is also great for "normal" puzzles to look what techniques it uses to solve them….
[Edit:] With version 1.2 now also the current hardest puzzles can be solved.
Well, it seems not to be true for your nightmarish puzzle:)
Code: Select all
500000009020100070008000300040702000000050000000006010003000800060004020900000005

ratings
gsfr : 99992
suexrat9 : 1263

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

Postby ravel » Thu Feb 08, 2007 11:53 am

Mike,

i tried to get the ER for your puzzle, but on my linux pc i ended up with
"Exception in thread "main" java.lang.OutOfMemoryError: Java heap space":) This never happened for any other puzzle.
[Added:] My program eliminated 3 from r9c8 using 6 subnets (giving r8c9=3). Then the ER goes down to 9.4.

The gsf rating is 99992. Note that the last digit may change for isomorphic puzzles. A rating above 99990 says, that it cannot be solved with contradiction chains using basics and multicoloring. In the list above there are only 8 other puzzles with this property ([Added:] Mauricio has posted 2 other ones here, which have been lower rated by my program).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Mauricio » Thu Feb 08, 2007 9:19 pm

ravel wrote:The gsf rating is 99992. Note that the last digit may change for isomorphic puzzles. A rating above 99990 says, that it cannot be solved with contradiction chains using basics and multicoloring. In the list above there are only 8 other puzzles with this property ([Added:] Mauricio has posted 2 other ones here, which have been lower rated by my program).

Don't forget this non minimal sudoku and this list.
I think I have 2 more unpublished symmetric (DS) sudokus beyond multicoloring.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby ravel » Fri Feb 09, 2007 4:12 pm

Thanks for the links Mauricio.
I have to apologize, because i had overlooked (or forgot about) the non minimal ER 11.0 puzzle. I just saw, that there are hundreds of minimal versions (with 26 to 28 givens) of it. I just picked out one 26-clue and got 14 points. I will rate them with my program after the weekend.
ravel
 
Posts: 998
Joined: 21 February 2006

PreviousNext

Return to General