The New Sudoku Players' Forum

[tknottet]

To eleven, tarek, champagne (and other members),
I'd like to inform you of usage of your puzzle(s).
On renewal of my sudoku site (not commercial), I'm going to add hardest sudoku list with my own rating.
http://www.tknottet.sakura.ne.jp/Test/Difficulty.cgi?List=All
(I'm very sorry but the site is in Japanese language.
I hope that (from left to right) [Puzzle Name],[Rating],[Source WEB Page] are recognized by foreigners.)
By clicking the fourth item(81 digits), visitors can solve the puzzle on my site.
All of top 10 are what are picked up from this Forum. My understanding is that tarek posted GoldenNugget,
champagne posted champagne_dry and eleven posted the other 8 puzzles.
I wish that 3 posters allow me to use their hardest sudokus in this manner.
If the posters (or any other members) have any comment about this usage, please inform me in reply.

My rating is calculating expectation of logic application number of times in try and error solving.
Its value seems highly correlated to SE.
Sometimes the calculation takes more than one month.
Rating value (* denoted) of some puzzles (Patience ... champagne_dry) were calculated before the latest bug-fix.
They will be updated in some months. As a result, the order may change a little.

[JasonLion]

Your URL didn't come through correctly. To get it to work, enclose it in URL commands, similar to this example:

Code: Select all

[url]http://forum.enjoysudoku.com/[/url]

{UPDATE}
Thanks for fixing the link!

[tknottet]

To JasonLion, thank you for your kind adviｃe.

[tarek]

I wish that 3 posters allow me to use their hardest sudokus in this manner

No Problem from my end. The list I compiled at the top of the Hardest sudokus thread has not been updated for quite some time. Champagne has compiled more up-to-date lists which you can find towards the tail-end of that thread.

[tknottet]

To tarek, thank you for your allowing and kind advice.
I will check the Hardest sudokus thread at times, so that my hardest sudoku list includes all puzzles SE(ER) rating of which is highest( currently 11.9).

[champagne]

To tarek, thank you for your allowing and kind advice.
I will check the Hardest sudokus thread at times, so that my hardest sudoku list includes all puzzles SE(ER) rating of which is highest( currently 11.9).

Hi,

IMO, we have nearly no chance to find more 11.9. for simple reasons,

Such ratings have nearly no chance to be seen out of the 20-22 clues field.
That area has been deeply searched by many players.

[tknottet]

To champagne, thank you for your response.
It's my pleasure to know that you read this topic.

I don't know about the chance of more 11.9, but I'll continue to check this forum for my list　maintenance.

[eleven]

tknottet,

of course my puzzles are free for non commercial use, and i feel honoured, when they are published.

I agree with tarek, that champagne's list of hardest sudokus is most up-to-date.
Therefore i would recommend to take the top ten there (ph_1409.zip from this site contains more than 1.5 mio puzzles).

Code: Select all

98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.;11.90;11.90;11.80;GP;champagne dry;1;22;
98.7.....6.....87...7.....5.4..3.5....65...9......2..1..86...5.....1.3.......4..2;11.90;11.90;11.60;GP;kz0;11523;23;
12..3....4....1.2...52..1..5..4..2......6..7......3..8.5....9....9.7..3......8..6;11.90;11.90;11.30;elev;second flush;2;23;
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....;11.90;11.90;11.30;tax;Golden-Nugget;3;21;
.2.4...8.....8...68....71..2..5...9..95.......4..3.........1..7..28...4.....6.3..;11.90;11.90;9.90;elev;3;4;22;
........1....23.45..51..2....25...1..6...27..8...9......42....7.3...6...9...8....;11.90;11.90;9.90;dob;12_12_03;248078;23;
12.3.....4.5...6...7.....2.6..1..3....453.........8..9...45.1.........8......2..7;11.90;11.90;2.60;elev;1;5;22;
..3..6.8....1..2......7...4..9..8.6..3..4...1.7.2.....3....5.....5...6..98.....5.;11.90;1.20;1.20;elev;2;6;22;
.......12......345..3..46....2..1.3..7..6....8..9.......5..2..4.6..8....9..7.....;11.80;11.80;11.70;dob;12_12_03;248083;22;
1.......9..67...2..8....4......75.3...5..2....6.3......9....8..6...4...1..25...6.;11.80;11.80;11.60;elev;15;7;22;

GP is champagne, elev eleven, tax tarek and dob dobrichev in this forum.
Probably the 5th puzzle (no name here) is Imam Bayildi. I have no tools here to verify it, but your 2 versions of Imam Bayildi must be a non miminal (23 clues) and minimal version (22 clues) of the same puzzle. The redundant clue obviously is no big help to solve the puzzle.
I saw that you also rated them equally.

Can you tell us more about your try&error method (and why it takes that long) ? Also dukuso's and gsf's ratings are based on try&error, but they are very fast. Their ratings also correlate to some extent with SE, but there are puzzles, where these ratings are rather bad.

[tknottet]

To eleven, thank you for your allowing, information and interest in my method.

I will add some puzzles from ph_1409 to my list in future.

As for Imam Bayildi, I'll check and report in later.
If the redundant clue is no big help to solve the puzzle, I hope that two versions in my list will get same rating value after the latest bug-fix.
Today I got the rating value of New_Imam_bayildi. In a few days I'll get the rating value of Imam_bayildi.

My method is to know about each candidate how many times the logic must be applied, after the candidate is assumed as the big number of the cell, until the puzzle is solved by try & error strategy.
To save calculation time, at every stage of calculation, only specific candidates are considered. The condition is to be in cells which has minimum number (2 or 3) of candidates at the stage.
The rating value is the statistical expectation of the number of times over all of the specific candidates.

I'm afraid that my explanation in English is poor.
So I try to explain it by a simple example 17Hints12538, which is one of minimum sudokus of Prof. Gordon Royle of The University of Western Australia.

puzzle: ...9...329.18............4..3...2...6.....1......4.....2..8.......7..6..7........
My logic leads to:
5 67 67|9 1 4 |8 3 2
9 4 1 |8 2 3 |57 * *
2 8 3 |56 * 57|9 4 1
-----------+-----------+-----------
4 3 * |1 * 2 |57 8 *
6 * 2 |3 * 8 |1 * 4
8 1 * |56 4 * |2 * 3
-----------+-----------+-----------
1 2 * |4 8 * |3 * *
3 59 4 |7 59 1 |6 2 8
7 * 8 |2 3 * |4 1 59
where nm denotes a 2 -candidate cell, * denotes a more-than-2-candidate cell.
In this case, 2 is a minimum number of candidate per cell, so I calculate the number of times for every candidate in 2-candidate cells.
The number of 2-candidate cells is 10, so 20 candidates are assumed, only one candidate is assumed for each time.
For 10 candidates, assumption of it results success by logic operation. Then the number of times is 1 for these candidates.
For 9 candidates, assumption of it results failure by logic operation. Then the number of times is 2(=1+1), because after failure the other candidate in the same cell must be checked.
Assumption of only one candidate which is 7 in 5th 2-candidate cell(57) results not-concluded as follows.
5 67 67|9 1 4 |8 3 2
9 4 1 |8 2 3 |57 * *
2 8 3 |56 56 7 |9 4 1
-----------+-----------+-----------
4 3 * |1 * 2 |57 8 *
6 * 2 |3 * 8 |1 * 4
8 1 * |56 4 59|2 * 3
-----------+-----------+-----------
1 2 * |4 8 * |3 * *
3 59 4 |7 59 1 |6 2 8
7 * 8 |2 3 * |4 1 59
In this stage, there are 11 2-candidate cells. Assumption of each candidate results failure.
So the statistical expectation of the number of times for this stage is 2, because the other candidate must be checked.
As for the above mentioned candidate 7 in 5th 2-candidate cell(57), the assumption results failure. The expectation is 4 (sum of 1=[from assumption to the above stage], 2=[to check both candidates in a 2-candidate cell] and 1=[until solved by checking another candidate(5)]).
So, my rating value of this puzzle is 1.6, which is the average of 1(10 candidates), 2(9 candidates) and 4(1 candidate).

To calculate the expectation, I must check all candidates in a condition(such that in minimum-candidate-cells). In some hardest puzzles, stages for not-concluded case are many in depth. In the case of Golden-Nugget, the calculation reached to the 13th in depth. So total number of times to apply logic operation is very large.

[UPDATE]
The above is only explanation of calculating expectation.
The reason why it takes long time maybe to take much time in each logic operation.
My logic operation sometimes takes a few minutes.

[eleven]

Thanks for the explanation.

Interesting.
Different to SE and most others, where the rating is that of the "hardest step", it is an overall rating (where only singles and locked candidates are used as "solving techniques").
This explains longer computing times (hard to say, if it could be done much faster - have you thought about using fast public solvers ?).

[tknottet]

have you thought about using fast public solvers ?

When I started to make my hardest sudoku list, I didn't know The New Sudoku Players' Forum, nor public solvers.
Although I know them now, I would like to continue my time consuming rating.
I hope that I can rate the remained 11.9 puzzles in ph_1409 list within this year.

[denis_berthier]

Hi tknottet,

Nice to see that someone is trying to find a new rating system.

Before any comment, I’ll try to describe my understanding of your method. Please tell me if I’m right.

1) what you call "logic operation" is the application of three kinds of rules:
- propagation of elementary constraints (direct contradictions)
- singles
- locked candidates (also called pointing/claiming, basic interactions, or whips[1] in my approach)
Let me call T this set of rules.

2) You're implicitly defining two closely related notions by mutual recursion: the rating R of a puzzle P and the rating R of a candidate (I use the same name for both as there can’t be any confusion)
Let P be a puzzle
- apply repeatedly to P all the rules in T until quiescence, thus obtaining a puzzle P1 (with both decided values and candidates)
- if P1 is solved, define R(P) as 0 (or 1 ???)
- otherwise, define R(P) as the weighted average of the R ratings of the (yet undecided) candidates in P1, where the weight for each candidate C in P1 is the inverse of the number of candidates in the same cell as C, [*** for efficiency reasons, this is limited to candidates C in cells with the smallest number of candidates in P1, say n];

- for each candidate C in P1 [restricted by ***], create a new puzzle P1(C) by adding C as a value and then applying repeatedly all the rules in T until quiescence; define the rating R of C as follows:
- if P1(C) is solved then R(C) = n (this case allows no conclusion, all the candidates in the same cell must be tried)
- if P1(C) displays a contradiction, i.e. a cell with no possible value, then R(C) = 1 (this case allows the elimination of C)
- otherwise, define R(C) as R(P1(C)), where the latter is computed by applying recursively the above procedure [or are you adding anything else ("from assumption to the above stage"?]

(That’s guaranteed to converge)

[tknottet]

Hi denis_berthier,
Thank you for your interest and kindness to confirm my explanation.

1) what you call "logic operation" is the application of three kinds of rules:
- propagation of elementary constraints (direct contradictions)
- singles
- locked candidates (also called pointing/claiming, basic interactions, or whips[1] in my approach)
Let me call T this set of rules.

"logic operation" is the application of some kinds of rules.
To explain "some kinds of rules", I use the terms in the following page.
http://www.sudocue.net/guide.php
"some kinds of rules" include:
Naked Singles, Full House, Hidden Singles, Squeezing, Cross-Hatching,
(I suppose direct contradictions and singles mean above rules.)
locked candidates
Disjoint Subsets
Some kind of coloring technique using strong/weak link chain
a technique using a vector between a pair of candidate( "If A is eliminated, then B must be eliminated")

As for this theme, I had to respond to the following comment.

(where only singles and locked candidates are used as "solving techniques").

But I didn't. I'm very sorry.

2) You're implicitly defining two closely related notions by mutual recursion: the rating R of a puzzle P and the rating R of a candidate (I use the same name for both as there can’t be any confusion)
Let P be a puzzle
2_1) apply repeatedly to P all the rules in T until quiescence, thus obtaining a puzzle P1 (with both decided values and candidates)
2_2) if P1 is solved, define R(P) as 0 (or 1 ???)
2_3) otherwise, define R(P) as the weighted average of the R ratings of the (yet undecided) candidates in P1, where the weight for each candidate C in P1 is the inverse of the number of candidates in the same cell as C, [*** for efficiency reasons, this is limited to candidates C in cells with the smallest number of candidates in P1, say n];

2_4) for each candidate C in P1 [restricted by ***], create a new puzzle P1(C) by adding C as a value and then applying repeatedly all the rules in T until quiescence; define the rating R of C as follows:
2_5) if P1(C) is solved then R(C) = n (this case allows no conclusion, all the candidates in the same cell must be tried)
2_6) if P1(C) displays a contradiction, i.e. a cell with no possible value, then R(C) = 1 (this case allows the elimination of C)
2_7) otherwise, define R(C) as R(P1(C)), where the latter is computed by applying recursively the above procedure [or are you adding anything else ("from assumption to the above stage"?]
[tknottet add numbers from 2_1) to 2_7) for referring.]
(That’s guaranteed to converge)

Thank you very much for better framework of description.
Before I rewrite the description with your framework, I would like to emphasize that R(P) is ｓtatistical expectation of "how many times T is applied form first quiescence until determined solved/displaying a contradiction". I don't think of eliminating candidates. If a contradiction is found, another candidate in the same cell is tested.

Followings are my description with your framework.
Let P be a puzzle
2-1)apply repeatedly to P all the rules in T until quiescence, thus obtaining a puzzle P1 (with both decided values and candidates) [no change]
2-2)if P1 is solved, define R(P) as 0. [not 1]
2_2+)if P1 displays a contradiction, define R(P) as 0. [for the use in applying recursively]
2_3) otherwise, define R(P) as the weighted average of the R ratings of the (yet undecided) candidates in P1, where the weight for each candidate C in P1 is the inverse of the number of candidates in the same cell as C, (*** for efficiency reasons, this is limited to candidates C in cells with the smallest number of candidates in P1, say n);
[no change]
2_4) for each candidate C in P1 [restricted by ***], create a new puzzle P1(C) by adding C as a value and then applying repeatedly all the rules in T until quiescence; define the rating R of C as follows:
[no change]
2_5) if P1(C) is solved then R(C) = R(P1(C))+1. [changed; R(P1(C))=0 by 2_2). +1 is count of until getting P1(C).]
2_6) if P1(C) displays a contradiction, R(C) = R(P1(C))+1 + R(C_S) + (1+R(P1(C_C))/2
C_S is the candidate in the same cell as C such that (directly or after applying rules recursively) determined as the big number of the cell
C_C is the other candidate in the same cell as C (in case of n=2 no C_C exists, in case of n=3 only one C_C exists)
[changed; my rating program calculates the ｓtatistical expectation under the condition that if a candidate(C) is selected as a starting candidate to be added as a value, the next candidate after finding contradiction is selected in the same cell as C. So try and error continues until C_S is selected and evaluated. The probability that C_C is selected before C_S is 1/2.]
2_7) otherwise, define R(C) as R(P1(C)), where the latter is computed by applying recursively the above procedure.
After the procedure, R(C) is calculated by the equation in 2_5) or 2_6) for each case.
[added: equation depends on the final results (solved/contradiction)]

[denis_berthier]

Hi tknottet,

Thanks for your detailed answer. A few details may still have to be clarified, but the general idea is clear.

Regarding T, do you have any particular reason for choosing such a queer set of rules ? Otherwise, you could try using the set I defined in my first post (you'd just have to forget some of your rules):
- it's somehow the most basic set one can imagine for T&E (you could even restrict it further to only Singles and direct constraint propagation)
- computations should become much faster (it is well known from the existing solvers that adding rules makes them slower in the mean)
Of course, you'd get a different rating. It is likely also that you would have to go somewhat deeper in T&E, but not much deeper I think (and not as much deeper as to counterbalance the speed increase).

More generally, what's the purpose of your rating ? Is it intended to rate the mean difficulty of a puzzle when one follows some specific resolution model, choosing randomly when the model allows several possibilities ?

[tknottet]

Hi denis_berthier,

At first

More generally, what's the purpose of your rating ? Is it intended to rate the mean difficulty of a puzzle when one follows some specific resolution model, choosing randomly when the model allows several possibilities ?

Yes, it is. I had to write this on the top of my explanation.

Regarding T, do you have any particular reason for choosing such a queer set of rules ? Otherwise, you could try using the set I defined in my first post (you'd just have to forget some of your rules):
- it's somehow the most basic set one can imagine for T&E (you could even restrict it further to only Singles and direct constraint propagation)
- computations should become much faster (it is well known from the existing solvers that adding rules makes them slower in the mean)
Of course, you'd get a different rating. It is likely also that you would have to go somewhat deeper in T&E, but not much deeper I think (and not as much deeper as to counterbalance the speed increase).

I have no particular reason. T is a set of rules that I provide for visitors to my site .
As for rating, comparison with a resolution model with a smaller rule set is interesting.
I'll try a smaller rule set ( as which a set of Singles and direct constraint propagation is intended).
The first report will be in March.
As for the report, do you recommend to create a new topic?
I'm afraid that the topic name is strange for these discussion.