The New Sudoku Players' Forum

[tarek]

This is irrelevant now. I just checked an old sudoku solver by rubylips here .

It is relatively fast, available online & apparantly uses tabling to a certain limit where Brute force is needed. I'm not sure if it is relevant now, as the post prior to editing described an older version that I discovered.

with this version, Puzzle 214 came on top with 2 Guesses & 7 Nishio from gsf's top 12 (I haven't looked beyond 12).......

[Heavily Edited]

This just adds to the variety of puzzle evaluation.......

Ravel, do you think that the techniques that you use prior to BF counting should be increased ?

tarek

[RW]

Hi RW

I checked you puzzles with the Sudoku Explainer. The ratings are:

Yes, probably should have mentioned that I already did that. I first ran the 9000 puzzles through suexrat9 and filtered out all with rating > 350. Then I picked all of these with explainer rating 9.0 or higher. I tried gsf's solver also, but I think his program just dislikes me in general, because none of the commands suggested in this thread worked (yes, I have downloaded the latest version)...

RW

[gsf]

I tried gsf's solver also, but I think his program just dislikes me in general, because none of the commands suggested in this thread worked (yes, I have downloaded the latest version)...

one problem is that windows handles { % " ' } differently in different contexts
I believe some windows users have had success putting the command lines in batch files
if that doesn't work pm me a failed command line and the error message
(I use uwin on windows so it feels like home)

[tarek]

I tried gsf's solver also, but I think his program just dislikes me in general, because none of the commands suggested in this thread worked (yes, I have downloaded the latest version)...

...
I believe some windows users have had success putting the command lines in batch files

True, ravel posted a batch file format here

tarek

[ravel]

Ravel, do you think that the techniques that you use prior to BF counting should be increased ?

Yes, of course, i would like to add xy-wing, swordfish, (at least advanced and multiple) coloring, xy-chains up to a limit of the number of cells, other UR-types (at least 2-6) and xz-ALS. Also the BF-steps at least should be devided in 2 levels, where i also would suggest to rate those needing less then a certain number of cells easier (this is hard to implement, because it would need an optimization of contradiction chains - again time consuming). Also i would like to have a rating, which is more robust to equivalence transformations.
BUT - i neither have time to implement it nor to recalculate then all ratings.

This are the ratings for RW's puzzles(thanks Viggo for the ER's - please post them, if you already have them for new puzzles, it takes some time to get them).

Code: Select all

RMS  ER   gsfr    suexrat9(2x)
 8   9.0  99324      521/520
 4   9.1  99354      374/371
 4   9.2  99324      359/356
 4   9.1  99262      470/503
 4   9.0  99324      457/455
 6   9.1  99374      416/410
 4   9.1  99334      480/473


So what is hardest for Explainer (#3), is easiest for suexrat. I interpret this as: It needs the most complicated step, but only a few hard steps.
What is hardest for suexrat (#1), is easiest for Explainer: It needs more steps, but not very hard ones.

There seems to be a little more correlation between the BF steps and suexrat than with ER or gsfr.

[gsf]

There seems to be a little more correlation between the BF steps and suexrat than with ER or gsfr.

from what I remember suexrat does a naked/hidden singles (or close to it)
backtrack search and averages backtrack behavior over several complete passes
on the puzzle, where each pass randomly selects the cells/candidates to guess on

random selection attempts to wash differences between equivalent puzzle permutations

the "hardest" rating from my solver attempts to wash differences by counting all moves at each level (guessing point)
and rates puzzles with more levels and/or less moves per level harder
the assumption being that hard puzzles cause solvers to guess and
and smaller #moves-that-advance-the-solution/#total-moves ratios would
cause more non-productive guesses

the rating does skew the guessing by checking cells with i candidates as a group,
starting with i=2 at each level, and incrementing until at least one productive move is found
or until no moves remain (which causes the next constraint set to be applied)

[RW]

Thanks for the ratings ravel, so apparently I double my old RMS-record!

I was suprised that they all qualified. All of these came from the same grid, with the same clue count. Also from a grid with exceptionally few puzzles to choose from at this clue count. My question now is of course: does this in some way imply that we could find several ultra hard puzzles that would qualify for the list in all possible grids? Probably there still is billions of toughies out there that aren't discovered, but that there would actually be several hiding in every grid would be suprising...

(thanks Viggo for the ER's - please post them, if you already have them for new puzzles, it takes some time to get them).

I apologize for not posting them immediately, sorry for wasting your time.

one problem is that windows handles { % " ' } differently in different contexts
I believe some windows users have had success putting the command lines in batch files

Ah, I simply hadn't noticed that they were talking about batch files, I had only tried them directly at the command prompt. I'll try the files next.

RW

[ravel]

My question now is of course: does this in some way imply that we could find several ultra hard puzzles that would qualify for the list in all possible grids? Probably there still is billions of toughies out there that aren't discovered, but that there would actually be several hiding in every grid would be suprising...

Since all 7 preselected 21s from the Pt-grid (which we expect to be poor for toughies) qualified, there should be at least hundreds of ultras in it. So i am sure that more toughies are out there (in fact billions) than i could run through my program in my lifetime and even fast rating programs probably would need years to rate them all, even if they would be known in advance.
So i wonder, how long it will take, that i only can accept puzzles with more than 10 steps, because some program filters lists with hundreds of puzzles per day, where 90% would qualify.

[RW]

Since all 7 preselected 21s from the Pt-grid (which we expect to be poor for toughies) qualified, there should be at least hundreds of ultras in it.

I don't think anymore that we could expect a grid to have hard puzzles based on some properties. I checked the grids on your list a while ago and they were as average as an average set can be when it comes to 2-digit unavoidables.

I don't think there's many more tough 21s in the Pt-grid (only discarded two puzzles with suexrat 350-400 and ER 8.4 and 8.8), but tough 22+ puzzles should exist. Coming to think about it, with possibly 10^16 minimal puzzles per grid, there should be thousands, if not millions of ultras in all grids. Has anybody got any good estimate of how many random puzzles needed to generate one ultra? So, yes, I'm sure that if you continue this hread for a year or so, then you will probably have to discard all but the 10+ steppers.

RW

[ravel]

Has anybody got any good estimate of how many random puzzles needed to generate one ultra?

Good question.
Oh, i did not know, how easy it is to find a puzzle, that qualifies for the list (never tried it myself). I generated 20000 puzzles with suexg and rated them with suexrat9. Under the 30 highest rated there were two with ER 9.1 and 11 with 9.0. Out of them two needed 4 BF steps.

So 1 in 10000 random puzzles qualified. This would mean, that there are about 10^21 puzzles, that would qualify, too much for my taste.

Therefore i will raise the limit for new puzzles to 8 steps now, found in 6 runs of my program (as i did it for the 10+ steps puzzles in the list). When i find the time, i will recalculate the 8/9-steppers in my list and remove the puzzles with less than 8 steps.

[Eioru]

2..3..4......9......3..1..98..2..6...4.....3...6..4..17..8..2......5......1..9..7 ~ 27 Forcing Chain
1..2..3......4......4..5..67..8..5...9.....2...3..7..48..9..2......1......5..6..7
1..2..3.............4..1..53..6..2...7.....3...9..4..82..8..7......6......8..5..9 ~ hard and 31 Forcing Chain
1..2..3......4......5..6..73..1..2...2.....7...6..8..58..9..4......6......9..7...

[daj95376]

Eioru, your third puzzle has an Achilles Heal. (It's also not symmetrical.)

Code: Select all

1..2..3.............4..1..53..6..2...7.....3...9..4..82..8..7......6......8..5..9

# after Naked Quad, Swordfish, Swordfish, Hidden Pair
 *-----------------------------------------------------------------------------*
 | 1       5689    567     | 2       45789   6789    | 3       46789   467     |
 | 56789   5689    23      | 4579    45789   36789   | 14689   146789  12467   |
 | 6789    23      4       | 379     3789    1       | 689     26789   5       |
 |-------------------------+-------------------------+-------------------------|
 | 3       48      15      | 6       15789   789     | 2       14579   147     |
 | 48      7       1256    | 159     1589    289     | 14569   3       146     |
 | 56      1256    9       | 1357    12357   4       | 156     1567    8       |
 |-------------------------+-------------------------+-------------------------|
 | 2       14569   1356    | 8       149     39      | 7       1456    1346    |
 | 4579    1459    1357    | 1479    6       2379    | 1458    1458    1234    |
 | 467     1346    8       | 1347    12347   5       | 146     1246    9       |
 *-----------------------------------------------------------------------------*

r6c2 =  2|5|6   => contradiction using net of Naked/Hidden Singles
r6c2 =  1       => cascade of Singles to solution


[daj95376]

Eioru, your first puzzle has two Achilles Heals.

Code: Select all

2..3..4......9......3..1..98..2..6...4.....3...6..4..17..8..2......5......1..9..7

# after Swordfish, Swordfish, Swordfish, Hidden Pair
 *-----------------------------------------------------------------------------*
 | 2       156789  5789    | 3       678     5678    | 4       15678   568     |
 | 1456    5678    4578    | 4567    9       25678   | 13578   5678    23568   |
 | 456     5678    3       | 4567    24678   1       | 578     25678   9       |
 |-------------------------+-------------------------+-------------------------|
 | 8       13579   579     | 2       137     357     | 6       4579    45      |
 | 159     4       257     | 15679   678     5678    | 5789    3       258     |
 | 359     2357    6       | 579     378     4       | 5789    2578    1       |
 |-------------------------+-------------------------+-------------------------|
 | 7       3569    459     | 8       1346    36      | 2       19      3456    |
 | 3469    368     248     | 1467    5       2367    | 19      468     3468    |
 | 3456    23568   1       | 46      2346    9       | 358     4568    7       |
 *-----------------------------------------------------------------------------*

Incorrect value for <19> in [b9] => contradiction using net of Naked/Hidden Singles
Correct   value for <19> in [b9] => cascade of Singles to solution


[ravel]

The hardest of Eiorus 4 puzzles was the second with 4 steps.

Thanks to Pat and JPF for posting the hardest of Nick70's 19-clue pattern collection. One of them, #848, was by far the hardest for my rating, it needed 10 steps, all the others less than 4.

I will remove all puzzles from the list with less than 8 steps next week, so if someone is interested in the current list, please copy it before. I already recalculated the 8-step puzzles, 4 of the 14 will fall out of the list (since solutions with 7 brute force steps were found), 2 by Ocean and the 2 from the top1465. The calculation of the 9-steppers is not yet finished (at least 3 of the 14 are out, two downrated to 8).

I also made a million puzzles test now. I generated 10^6 minimal random sudokus with suexg and rated them with gsf's program and suexrat9. The best rated had 99424 and 530 resp. There were 191 puzzles with gsfr 99344+ and 153 with suexrat 340+. 49 duplicates in these 2 lists.
Compare: Nicks 10-stepper had 99354 and 353 (note that the suexrat is varying in different runs), so 42 puzzles were harder rated by gsf and 103 by suexrat.

There was no high stepper under the 191 best gsf rated and only number 30 of the 153 best suexrat rated made the first run with 8 steps (and the second in the meantime). This one run took about that long as the calculation for 150 of the other puzzles.

So the two ratings gave much differences in difficulty for my program. Extreme: a puzzle solvable with triple was rated 390 by suexrat9.

So maybe one out of a million will qualify, thats a good rate

[tarek]

Just an observation.........

All SE>9.5 have been following these 2 patterns:

Code: Select all

 . . * | . . * | . . *
 . * . | . * . | . * .
 * . . | * . . | * . .
-------+-------+-------
 . . * | . . * | . . *
 . * . | . * . | . * .
 * . . | * . . | * . .
-------+-------+-------
 . . * | . . * | . . *
 . * . | . * . | . * .
 * . . | * . . | * . .

 . . * | . . . | . . *
 . * . | . * . | . * .
 * . . | . . . | * . .
-------+-------+-------
 . . . | * . * | . . .
 . * . | . * . | . * .
 . . . | * . * | . . .
-------+-------+-------
 . . * | . . . | . . *
 . * . | . * . | . * .
 * . . | . . . | * . .


mixing the 2 patterns we get

Code: Select all

 . . * | . . * | . . *
 . * . | . * . | . * .
 * . . | * . . | * . .
-------+-------+-------
 . . * | * . * | . . *
 . * . | . * . | . * .
 * . . | * . * | * . .
-------+-------+-------
 . . * | . . * | . . *
 . * . | . * . | . * .
 * . . | * . . | * . .

which should be a target or expanding it a bit to

Code: Select all

 * . * | . . * | * . *
 . * . | . * . | . * .
 * . * | * . . | * . *
-------+-------+-------
 . . * | * . * | . . *
 . * . | . * . | . * .
 * . . | * . * | * . .
-------+-------+-------
 * . * | . . * | * . *
 . * . | . * . | . * .
 * . * | * . . | * . *

I'm sure that 1 million puzzles following 1 of the last 2 masks would provide some nice results

tarek