The hardest sudokus (new thread)

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

Postby tarek » Tue Jan 13, 2009 5:40 pm

briturner wrote:As a followup question, what do you do about variations with better scores?
This is very unfortunate. The 10000 2 option seems to serve in these puzzles to reproduce similar results between machines. I would have expected this to mean that this to be same over permutations of the same puzzle ... Maybe this means that the permutations in suexratt are not that random ???!!!!!


In this case, I would say that the lowest rating should be taken into account ... The suexratt rating of 2768 might mean that a downgrading is needed ....

Because it would be tedious to do all of this by one person .... I will run the program on the original puzzle but will accept & change the ratings if another user demonstrates that a permutation has indeed a lower rating.

I will also show the top 5 from each category for that same reason.

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

Postby tarek » Tue Jan 13, 2009 6:07 pm

Because of the lower Suexratt score of coly013 I ran several permutations of its closest conteder, tarx0134 under suexratt
Code: Select all
suexratt test.txt 10000 2
rating:   4566 ,    3222 , ........8..3...4...9..2..6.....79.......612...6.5.2.7...8...5...1.....2.4.5.....3
rating:   4675 ,    3331 , ..3.5..8.4..1.9........7....1...4.....8.2..6.7..9....2..2...6.8.......9.......325
rating:   4445 ,    3031 , ........1......234.....456...7.......3...2..68.1.9......98......4...6..51...7..4.
rating:   4580 ,    3029 , 1...7.8.....6.2..4...3.......9..6..35...9.1.....4...2..51...9..6........987......
rating:   4376 ,    2954 , 123......6.........59...1.....4...8.5...1.9....1..6..7...7........6.8..49...3.2..
totalnodes:226445003
until evidence of lower rates are presented ... the top list will change.

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

Postby briturner » Wed Jan 14, 2009 1:16 am

Greetings,

I realize I am new here, and not in your guy's league (my highest puzzles I am currently generating have Q2 ratings of only 97500 to 97700), but I have a suggestion:

For ratings, using the min-lex version of the puzzle to base the rating on.

reasoning:
you have basically 4 options for handling variations:
- Take the highest
- Take the lowest
- Take the first submitted
- Take the rating of a normalized version

Taking the highest encourages people to run various permutations, trying to get higher scores. This means lots of computing power used to improve the score without really generating anything new. My opinion is that this is probably the second best option, since if you do the effort , you get a positive result, but it is a bit wasteful.

Take the lowest discourages running permutations other than someone doing it to knock someone else down. This just feels wrong to me since the only motivation is negative, but it also means that anyone score can be degraded at any time.

Take the first submitted will cause people to hold out on submitting puzzles as they run permutations to try to get a higher score. Again wasting time without generating anything new, but now doing it in secret since they cannot release the puzzle while they are doing this.

Take the rating of the normalized puzzle appears to me to be the least wasteful and best option. Since ratings are somewhat subjective anyways, this at least provides a single puzzle a single score without wasting time running permutations.

The absolute worst idea would be to allow permutations to be submitted as a separate puzzle, which would encourage outright theft. No one is suggesting this, but I mention it to be complete with the options.


I did a quick test with the Q1 and Q2 rating, and found the it's variations much more acceptable (0.005% compared to 15% with suexratt).

also, is there a program or command line that can take a puzzle and generate the min-lex version?

thanks
brit
briturner
 
Posts: 3
Joined: 12 January 2009

Postby ronk » Wed Jan 14, 2009 1:44 am

briturner wrote:For ratings, using the min-lex version of the puzzle to base the rating on.

Sounds very reasonable to me.

briturner wrote:The absolute worst idea would be to allow permutations to be submitted as a separate puzzle, which would encourage outright theft.

Permutations are not allowed. Determining whether or not puzzles are isomorphic (equivalent, permuted) is the biggest reason for row-order minimum lexicographical order canonicalization (c14n) in the first place. (dang, that's a mouthful)

briturner wrote:is there a program or command line that can take a puzzle and generate the min-lex version?

I use gsf's program, with the command line ...

sudoku -qFN -f%#.c test.dat

... combined with fgrep to find puzzles that don't already exist in a library.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Wed Jan 14, 2009 2:45 am

one clarification on canonicalization in my solver
there are two minlex forms
-f%c : minlex based on the solution grid
-f%#mc : minlex based on the puzzle (subgrid) -- also allows partial puzzles
in general the minlex based on the solution grid algorithm is faster than the subgrid algorithm as the number of clues increases
the knee is somewhere near 20 clues if memory serves correct
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Wed Jan 14, 2009 4:10 am

ronk wrote:
briturner wrote:For ratings, using the min-lex version of the puzzle to base the rating on.
Sounds very reasonable to me.
Fair enough. Unfortunately all my database & ratings are based on the original puzzle configuration & therefore some work needs to be done. Will recompute for top 10 to bring out the top 5. This excercise is to calculate the top puzzle(s) so it shouldn't really have a major impact on the rest of the puzzles already rated & in the database.

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

Postby tarek » Wed Jan 14, 2009 8:19 am

Was compiling the database. The first victim was
Code: Select all
..6.....1.7.4...2.....5.3...8...7........4.8.9.28.......1...5...2.9...7.3.......6 coly005
which is isomorphic to
Code: Select all
.....5..4.9.....2...6.7.3.....7..8....86.....13..8......3.1.6...2......54......9. tarx0068
. The database will be constructed to show non isomorphic puzzles, therefore only the 2nd puzzle will be in the database. The lack of an up to date database was IMO the reason behind some isomorphic puzzles appearing.

I'll post some notes with the database.

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

HardestDatabase090115

Postby tarek » Wed Jan 14, 2009 6:49 pm

This is my current database (HardestDatabase090115), sorted according to q2 rating

List deleted to avoid order confusion with recent updated form of list

1st line is the fields names
The database is missing the ER,EP,ED of many puzzles, therefore I will not show a top 5 for ER at this moment in time.

The Date field as well has not been filled.

Not all Sx9 or Sxt ratings are based on the row normal minles isomorph, only the ones in the top 10.

tarek

[EDIT: Database re-posted with cosmetic modifications]
{EDIT: List deleted to avoid order confusion with recent updated form of list]
Last edited by tarek on Thu Dec 30, 2010 11:42 am, edited 3 times in total.
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Re: HardestDatabase090115

Postby gsf » Wed Jan 14, 2009 7:13 pm

tarek wrote:This is my current database (HardestDatabase090115), sorted according to q2 rating

thanks
if you make this the first line in the db
Code: Select all
#!sudoku -c2,ID,PuzzleR,PuzzleC,Label,Poster,Date,Q1,Q2,ER,EP,ED,Sx9,Sxt

then my solver will be able to access the fields by name
other solvers could at least use the
Code: Select all
-c2,

to determine that the puzzle is in the 2nd comma-separated field
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: HardestDatabase090115

Postby champagne » Wed Jan 14, 2009 7:38 pm

tarek wrote:This is my current database (HardestDatabase090115), sorted according to q2 rating

Hi tarek,

Could it be possible to get it with puzzles starting in position 1 ??

I would see what is my up to date ranking for these puzzles.

champagen
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Postby tarek » Wed Jan 14, 2009 8:07 pm

The database has been re-posted with the puzzle in the first column & gsf sudoku friendly 1st line:D

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

Postby champagne » Wed Jan 14, 2009 8:31 pm

tarek wrote:The database has been re-posted with the puzzle in the first column & gsf sudoku friendly 1st line:D

tarek

Thanks for the future.

I reshaped that one handly and I am runnng it.

I have to dig in the first entry. Seen by my solver, it has nothing that makes it eligible as an "hardest puzzle". Not even one of the specificities given by ttt:!: No symmetry, no need to look for SK loop.

Either there is a bug in my solver, or it is over valued in the ranking.

By chance the list is long enough to include my hardest known, Silver Plate, but that one and Golden Nugget would have disappeared with a cut off slightly lower:!::!:

champagne

EDIT: I think I already checked that one when coloin submitted it just because he expressed a disenchantment when I got that result.
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Wed Jan 14, 2009 10:04 pm

tarek wrote:The database has been re-posted with the puzzle in the first column & gsf sudoku friendly 1st line:D

While you're still in the mood to honor requests:) ...

To make more relevant fields stay on-screen for human readers, would you please make [edit: PuzzleC] the last field:?:

BTW IIRC, if you replaced hyphens with underscores, your Pearly6000 entries wouldn't line wrap.

BTW2 I applaud your use of ",," instead of ",0," for empty fields.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Thu Jan 15, 2009 1:48 am

ronk wrote:To make more relevant fields stay on-screen for human readers, would you please make [edit: PuzzleC] the last field:?:

BTW IIRC, if you replaced hyphens with underscores, your Pearly6000 entries wouldn't line wrap.
I sense that there is a display problem which isn't present in IE7 ... because I used the [size] tags I managed to shrink the text to esablish 1 record per line (that is true even with 1024*768 display)

ronk wrote:BTW2 I applaud your use of ",," instead of ",0," for empty fields.
is that sarcasm:D , I'll continue with it regardless:D

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

Postby champagne » Thu Jan 15, 2009 1:59 am

Hi all,

here some statistics coming out of the run of the database just published by tarek.
I run the file under several options
First one (column 2)is a kind of standard processing including the search of the SK loop.
Is given the processing time in seconds.

Column 3 is the lowest number I got for puzzles giving the higher time in column 2 under the following options :
Search of "bi bi" patterns
Forcing or not level 4 at the start.

Last column indicates whether a SK loop and/or a "bi bi" pattern can be found.
Two puzzles have both
A small number of puzzles have none.
I have not seen "symmetry", but the program has been modifed recently to include new "symmetry patterns" and it has not been validated yet.

EDIT checking first Item, i saw that I missed one double "bi bi" with two different targets. (I already saw double "bi bi", but with redundancy). May be I missed others

One can see that in the present status of the program, "bi bi" pattern have unclear effect:

Normally, if the "bi bi" is of the form 123 123, effect is very strong
( eg: Trompe l'oeil)
With the form 1234 1234, effect can be very strong as in Golden Nugget if some super candidates of the "bi bi" pattern are immediately eliminated.
If as in Silver Plate no elimination is found at the start, a more precise analysis of the pattern is requested. No idea for the time being what can come out at the end.

All puzzles not having the SK loop and solved in less than 3 seconds should be discarded from the list of hardest. They can be solved "easily" by a skilled player.
In the final list, it should likely be the case for puzzles solved in less than 3 seconds in the second column.


Code: Select all
coly013,coloin          1.4           BB r2c7 r4c9 r8c3  BB r56c8 r3c9 r9c7
colx062,coloin          2.8   
tarx0037,tarek          7.0           SK BB r46c5 r2c4 r8c6
dukdiamond2,coloin      3.5           SK
coly012,coloin          3.7           BB r12c7 r4c8 r7c9
tarx0035,tarek          28.1  1.5     BB r9c8 r7c4 r8c2
tarx0009,tarek          15.1  13.8    BB r46c4 r2c5 r7c6
tarx0105,tarek          56.2  57.6
tarx0104,tarek          58.3  57.3
Pearly6000-1803,tarek   9.9           SK
tarx0006;Trompe_l'oeil  33.4  1.5     BB r3c79 r4c2 r6c8
tarx0064,tarek          5.1   
Pearly6000-1802,tarek   9.7           SK
tarx0012,tarek          3.2           BB r4c46 r5c7 r6c3
colx180,coloin          22.7  23.5    BB r12c7 r4c8 r7c9
coly002,coloin          7.1           BB r12c7 r5c8 r8c9
tarx0067,tarek          2.5           BB r46c5 r2c4 r8c6
coly007,coloin          4.3           BB r12c7 r4c8 r7c9
Pearly6000-2803,tarek   9.9           SK
coly010,coloin,         2.6           BB r2c17 r4c8 r7c9
coly006,coloin,         3.7           BB r2c17 r4c8 r7c9
coly008,coloin,         3.4           BB r2c17 r4c8 r7c9
ultra0300;tarek         6.2           SK
tarx0108,tarek          49.5  1.9     BB r1c23 r2c5 r3c8
tarx0119,tarek          63.5  1.7     BB r6c45 r4c3 r5c8
ultra0313;tarek         3.4           SK
tarx0010,tarek          53.9  2.0     BB r6c45 r4c2 r5c7
pearly6000-3978,tarek   3.2           SK
tarx0136,tarek          2.3   
PlatinumBlonde,coloin   32.1  28.2
tarx0051,tarek          17.5  17.0
tarx0134,tarek          3.7     
tarx0062,tarek          8.3           BB r78c9 r3c7 r5c8
tarx0141,tarek          12.0  17.2
tarx0068,tarek          16.0  18.1    BB r6c46 r4c3 r5c7
tarx0131,tarek          13.0  15.2
tarx0018,tarek          2.5   
pearly6000-4143,tarek   4.1           SK   
pearly6000-4268,tarek   9.3           SK
pearly6000-3802,tarek   9.2           SK
pearly6000-3238,tarek   9.5           SK
pearly6000-3112,tarek   9.6           SK
ultra0203,tarek         4.6           SK
tarx0005,tarek,         6.4           BB r6c45 r4c8 r5c3
tarx0004,tarek,         5.3           BB r5c46 r4c3 r6c7
tarx0003,tarek          6.1           BB r6c56 r4c7 r5c2
tarx0079,tarek          4.7           BB r9c78 r7c2 r8c4
colx001,coloin          28.6  27.7    BB r12c7 r4c8 r7c9
colx134,coloin          32.0  34.8    BB r6c56 r4c8 r5c2
tarx0114,tarek          4.3           BB r5c46 r4c2 r6c8
tarx0014,tarek          5.8           BB r13c2 r4c3 r7c1
TungstonRod,coloin      9.7   3.4     BB r56c6 r2c5 r8c4
Golden_Nugget,tarek     56.7  30.0    BB r12c7 r4c8 r7c9
tarx0052,tarek          2.5           BB r46c5 r2c4 r8c6
weekender1,coloin      56.8   3.6     BB r12c7 r4c8 r7c9
tarx0075,tarek         22.5  18.3     BB r46c5 r2c4 r8c6
CloudyBay,coloin        5.1           SK BB r6c56 r4c8 r5c2
tarx0001;Fata_Morgana   7.1   1.2     BB r5c46 r4c2 r6c8
Pearly6000-1847,tarek   4.9           SK
tarx0002,tarek          32.4  2.3     BB r5c46 r4c2 r6c8
dukdiamond1,coloin      3.2           SK
tarx0130,tarek          8.0           BB r5c46 r4c3 r6c7
tarx0140,tarek          8.3           BB r5c46 r4c3 r6c7
tarx0137,tarek          23.3  4.3     BB r13c2 r5c3 r7c1
coly004,coloin          4.4           BB r12c7 r5c8 r8c9
tarx0121,tarek          42.3  1.3     BB r46c2 r3c1 r9c3
tarx0011,tarek          7.2           BB r5c46 r4c2 r6c8
colx1665,coloin         4.3           BB r12c7 r4c8 r7c9
tarx0145,tarek          5.5           BB r5c46 r4c2 r6c8
tarx0013,tarek          23.8  1.9     BB r5c46 r4c3 r6c7
Easter-Monster,JPF      4.4           SK
Pearly6000-1801,tarek,  33.0  21.6    BB r5c46 r4c8 r6c2
tarx0007,tarek          6.4           BB r5c46 r4c3 r6c7
coly009,coloin          1.5           BB r12c7 r4c8 r7c9
SilverPlate,coloin      67.2  77.9    BB r6c56 r4c8 r5c2
colx467,coloin          2.1           BB r23c7 r4c9 r8c8
tarx0008,tarek          53.2  3.2     BB r78c9 r3c7 r5c8
tarek071,tarek          29.6  29.6    BB r5c46 r4c8 r6c2
tarx0103,tarek          4.7           BB r5c46 r4c3 r6c7
tarx0139,tarek          3.0           BB r5c46 r4c3 r6c7
coly001,coloin          3.3           BB r12c7 r4c8 r7c9
tarx0059,tarek          26.1  23.4
BronzeMedalian,coloin   16.5  16.0    BB r6c56 r4c8 r5c2
tarx0061,tarek          28.6  2.9     BB r13c2 r5c1 r8c3
tarx0080,tarek          12.6     
tarx0146,tarek          5.0           BB r5c46 r4c2 r6c8



champagne
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to General