The New Sudoku Players' Forum

by **dobrichev** » Thu Dec 06, 2012 10:37 pm

There is article by Radek Pelane with different rating approach, not applicable to hardest puzzles.

I am reading Stuart's approach as "when you exhausted all solving techniques from your arsenal, what is the probability to choose the right cell for guessing". This works when applying known techniques takes negligible effort compared to guessing effort. Maybe more accurate results should include scaling to the number of the possibilities in each of the cells.

Pelane, from other side, estimates how easy you will find a technique from your arsenal that can be applied leading to eliminations.

Today I made some experimenting with different approach.
Ignoring the effort in applying the known techniques (singles, tried also with locked candidates), count the average guesses you should do, choosing only from the "best" guesses.
Best guess is one that is most probable to hit the correct value. Since we don't know what is the correct value for the cell, we are choosing (cell,value) pair following these criteria:
a) maximal probability == minimal number of candidates;
b) maximal direct interactions with other pencilmarks.

The a) criterion is calculated by simplification that the number of the candidates in the cell and the number of the positions of the value within the box, row, and column are independent and therefore the resulting probability is the product of the individual probabilities. In practice it is calculated by searching the maximal reciprocal of the product of the above 4 counts.
The b) criterion is pure artificial and its purpose is to limit the number of equally probable guesses. Without such limitation, walking on hardest collection with, say, 50 puzzles per second, each 2000th puzzle takes one hour to be completed just due to the large number of candidates with equal probability that have to be traversed.

All guesses with equal weight are processed, and the results are averaged. Finally an average depth of guessing is calculated, which is the rating value.

There is poor correlation with SE rating, which is not surprise since SE is focused on "hardest step knowledge" but I am focusing on average efforts, weighting every guess to 1, single eliminations to 0 and probability calculations to 0.

The method is not sensitive to VPT in any way. Puzzles solved by singles have rating 0. The method in some degree depends on the number of givens.

There are significant deviations in the rating proportions when small changes in techniques is made (+/- locked candidates), and when b) criterion is changed to similar one. This noise is making the entire approach not so promising.

by **champagne** » Sat Dec 08, 2012 3:43 pm

Hi,

The game 195 is not closed, but I would share some interesting (IMO) data related to that game.

I proposed a pattern for which I identified in the published files loaded in the skfr project

5937 puzzles (basically skfr rating 10 and more).
Among them 288 puzzles eligible to the file of potential hardest.

I stored (but I started to late, so I lost some puzzles) all such puzzles I got in the generation.
I am not so far to switch off the search, so I made an interim report.

I already stored 66891 puzzles rating 10 and more
Among them 4873 matching with the old list
And 336 new puzzles eligible to the list of potential hardest.

It took me nearly 3 days to find the highest known rating (and so far nothing higher)
I tried to explain why it has been so long and I made a back search of the vicinity to that puzzle in the first 220 million Ed puzzles generated.

Here after the puzzle and the 7 puzzles I found with at most 3 digits different from the target.

Hidden Text: Show

As the only systematic expansion I use is (+-1_3), these were the only chance for me to generate the target.

With the cut off I used to select new seeds, only the first one in that lot of 220 milion puzzles had a chance to produce the target. 3 more could have been used as seed at the very beginning of the game.

I don’t know if that puzzle is really uncommon. But my expectation is that we can find many examples of such puzzles in the areas freshly scanned (24 clues 25 clues).

This will require a new organisation if we intend to make public such puzzles.

by **champagne** » Sat Dec 08, 2012 5:57 pm

dobrichev wrote:I am reading Stuart's approach as "when you exhausted all solving techniques from your arsenal, what is the probability to choose the right cell for guessing". This works when applying known techniques takes negligible effort compared to guessing effort. Maybe more accurate results should include scaling to the number of the possibilities in each of the cells.

Hi Mladen,

I made a quick overview of your post.

It seems to me that the topic here is more oriented on ' how to increase your efficiency in sudoku tournaments'.

But I can be wrong

by **champagne** » Tue Dec 11, 2012 3:22 pm

coloin wrote:here are the new puzzles with skfr that i found above 11.3 [79 11.0 and above]
C

these have been entered with the serate rating

They will be in the next update of the file

....5.7.....9.1.6.........52....8.16.......2..3....4.7.7..4......82.9...9.68.....;11.7;11.7;9.4
.2...1......6...3...9.8...7..5....78.3.....1.8...4.5....4.9.7...6.2.....9.......5;11.5;11.5;9.9
2.......6.3..8..1...4...9...5.3.1......82.......7.5.8...9...2...7..1..5.6.......4;11.6;11.6;11.3
98.7.....7..8..9....5.4....39....6...6.........2....31...3..76.....1...2.....5..4;11.7;11.7;2.6
..1.5.7..4....9....8.2.....2......4..9.8.......3.6.5.....5.16......7..13..6.....7;11.7;1.2;1.2

by **pjb** » Tue Dec 11, 2012 10:24 pm

Regarding the first of these:

Code: Select all: ....5.7.....9.1.6.........52....8.16.......2..3....4.7.7..4......82.9...9.68.....;11.7;11.7;9.4

I was surprised to find that it can be solved in 2 steps:

1. A simple row/column multifish:

Code: Select all: 20 Truths = {3457R2, 3457R4, 3457R5, 3457R8, 3457R9} 20 Links = {45c2, 37c5, 35c7, 34c9, 2n13, 4n34, 5n1346, 8n18, 9n68} 22 Eliminations

2. A naked triple of 457 in box 4, after which can be solved with singles

It seems a deficiency in our rating scheme that it doesn't take into account techniques such as multifish and SK loops.

pjb

by **champagne** » Wed Dec 12, 2012 8:52 am

Hi pjb,

I work heavily on exotic patterns here

Nevertheless, the primary collection remains based on serate (now mostly skfr) ratings.

There are two main reasons to go in that direction.

1) to study exotic patterns, we need sample files
2) many attempts to create new rating tools give results much closer to the primary rating we have here.

Just consider the two last rating tools we have seen

The rating tool proposed by Denis Berthier. pattern-based-classification-of-hard-puzzles

the chaos rating

JPF wrote:Here is the link of an article recently published by Nature:

The Chaos Within Sudoku

JPF

In the first case, although we don’t now how many puzzles of our sample file have been processed, the highest ratings are clearly in the high ratings of serate.

The second one worked out only a small sample, as far as we know, and elected “platinum blonde “ as the hardest.
That one is far from serate’s top list, but still on the high side (and can be solved easily using Exocet properties)

On the other way, we still have no clear view on what can be the “hardest puzzle”.

In the collection of “potential hardest” now located here
all “exotic patterns” identified by my program are shown.

Except may-be some puzzles as Golden Nugget where the Exocet has a small effect, all these puzzles can be excluded from the “first short list” of potential hardest.
I have to update the “exotic” file, but if I refer to past results, more than 80% of the primary list disappear in that process.

The “first short list” still contains some exotic patterns not seen by my program and surely has other not yet described exotic patterns.

The final short list should be much shorter.

I long ago processed that “final short list “ with my odd solver to select puzzles with a very long path.

Later on, the priority has been given to the search of new “primary hardest” and to the study of exotic pattern, but clearly this has to be updated to produce a fresh short list of hardest.

by **champagne** » Thu Dec 20, 2012 10:27 am

pjb wrote:Regarding the first of these:

Code: Select all
....5.7.....9.1.6.........52....8.16.......2..3....4.7.7..4......82.9...9.68.....;11.7;11.7;9.4

I was surprised to find that it can be solved in 2 steps:

1. A simple row/column multifish:

Code: Select all
20 Truths = {3457R2, 3457R4, 3457R5, 3457R8, 3457R9} 20 Links = {45c2, 37c5, 35c7, 34c9, 2n13, 4n34, 5n1346, 8n18, 9n68} 22 Eliminations

pjb

I am preparing an update of the exocet properties in the file of potential hardest.
The last long task is the check for rank0 logic. I hope to have covered my last update of the file before Christmas.

I checked in a separate run that one, it will appear as having both a pure rows and a pure columns rank 0 logic.

EDIT: The solver uses a different row base, with only 16 truths and 21 eliminations

16 Truths = {3R2489 4R2489 5R2489 7R2489 }
16 Links = {3c579 4c29 5c27 7c5 2n13 4n34 8n18 9n68 }

by **champagne** » Tue Dec 25, 2012 10:27 am

Hi everybody,

Merry Xmas and happy new year first.

The ongoing long run to work out the exotic rank0 property on the current file of potential hardest ended during the last night.
I loaded the last version of the exotic properties here

both files are now in line with 550 000 puzzles rating at minimum 10.3 skfr .

As I'll be off from mid January till mid march, the next update should not come before end of march at best, although i have in hands a big file of new puzzles created by mladen dobritchev.

by **dobrichev** » Fri Jan 04, 2013 8:29 am

Hi everybody and Happy New Year.

There are several non-minimal puzzles in the latest version of the hardest collection.
One of them is intentionally included - the Mauritio's 37-givens 11.2.
Another one is 11.3 "colh54;ronk-02-20-08 #1".
The rest came from me :oops:

Champagne, please remove them (except Mauritio's one) from the next release of the collection.
Here they are

Hidden Text: Show

by **dobrichev** » Mon Jan 07, 2013 10:58 pm

eleven wrote:Here is the output for -qFN, which confirms the backdoor sizes 3....

coloin wrote:So -q1 would have been more appropriate. Thanks eleven.

Thank you eleven and coloin.
So if my calculations are close to the reality, below is distribution by skfr rate of a collection of 42330 puzzles with backdoor of size 3 in singles. 80% of them are obtained by close-to-hardest half billion puzzles and 20% came from additional vicinity search.

Hidden Text: Show

by **eleven** » Mon Jan 07, 2013 11:51 pm

Time to say congratulations, Mladen.
These are the easiest known puzzles, which need 3 guesses for a singles solver. Normally you have good chances for the hardest with this property (as your stats also show).
Numbers 3,4,11, and 12 simply solve with basics and a remote pair !

by **tarek** » Tue Jan 08, 2013 7:38 pm

From this link:

gsf wrote:
ravel wrote:Amazing puzzle, Ocean. I never thought, that backdoor size is a good criterion for hardness, but i did not expect such an "easy" M3 puzzle (far away of all hardest lists).

here's one from gordon's 22M 18 catalog
just a bit easier (6 proposition steps instead of 9) q1 rating 1278, singles backdoor size 3
Code: Select all
3.....2.....54.......6.....1.2..3..........648.........9.7...5.......1.8.5..6....

I'm checking the other 22M now (min q1 rating 6, max 8596)

The above puzzle solves with triples

I'm not sure who is keeping track of all posted singles M3 puzzles. They used to be quite rare in 2007 before their numbers exploded!!!

by **tarek** » Wed Jan 09, 2013 10:59 am

The relatively easy singles M3 puzzles are very good for manual solvers due to their guess-defeating properties.

What comes next is to see what singles M3 puzzle has the least number of backdoor triplets. Could there be a puzzle with only 1 singles backdoor triplet? A search in the neighbourhood of that puzzle might bring some unexpected results

BTW I thought that gsf kept record of all published singles M3 puzzles :mrgreen:

by **ronk** » Wed Jan 09, 2013 12:18 pm

tarek wrote:What comes next is to see what singles M3 puzzle has the least number of backdoor triplets. Could there be a puzzle with only 1 singles backdoor triplet?

That is highly unlikely IMO, but "mm" would be the number of interest in "M3.mm.nn".

by **dobrichev** » Wed Jan 09, 2013 4:23 pm

What "mm" and "nn" are?

The New Sudoku Players' Forum

The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

hardest collection

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: Easiest M3

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)