The New Sudoku Players' Forum

[ravel]

Is some recalibration called for?

The main problem i have with my rating is, that changing the parameter, when to search for subnets (the most time consuming step) always gives worse results for some (but different) puzzles and i dont have an argument, that this or that value would be more justified. So in my current top list i show the minimum points from four different runs, but it takes me too much time to do that for all puzzles.

Up to Mauricio's symmetrical puzzles and now yours the sudokus with very high Explainer rating always have been in my top list also (i only remember one more exception, a 10.1 puzzle by RW). Of course there must be a difference between ER and my rating, because the Explainer only rates the hardest step, while i take the "shortest solution" for the rating. But i agree, that the hardest step is underrepresented in my rating and i am thinking of giving extra points for longer subnet steps. Of course then i will have to recalculate the list, because other solutions would become "better".

For the moment here is a list of puzzles with highest ER, as far as i found them in this thread:

Code: Select all

11.4:
m_b_metcalf:
500000009020100070008000300040702000000050000000006010003000800060004020900000005
StrmCkr:
500000009020100070008000300040002000000050000000706010003000800060004020900000005

11.2:
Ocean's New Year's present for RW
000001020300040500000600007002000001080090030400000800500002000090030400006700000

11.1:
dml 1/07
003000009400000020080600100200004000090800007005030000000900800000005030070010006

11.0:
Mauricio's non minimal puzzle (62 non isomorphic minimals):
600002059520040010003500200300194500010658030005273001004005100030020045750400008

10.9:
Some more puzzles by Mauricio:
300005002040010030009000800500090000020608040004200005006001700010030020400500001
100005004040020030008000700500100000030608010000073005009002600010040020200500003
700000006020030010001500400000190500040600020005273000002005300030010040800000009
100500004070000060002030100020190005004008200500073000003010400080000090200005003

10.8:
dml 3/07
003400080000009200000060001007010000060002000500800040010000900800000030004500007
Another one by Mauricio:
100040030000007004005800700002500080600090002030000400003006000700200000060080001


[m_b_metcalf]

For the moment here is a list of puzzles with highest ER, as far as i found them in this thread:

For the record, here are the two with SE = 10.7, gsfr = 99992 (but maybe they're isomorphs):

Code: Select all

500000009020100060008000300040702000000090000000506010003000800070004020900000005
300000004080700090006000500010908000000060000000507020005000600070001080400000003


Regards,

Mike Metcalf

[Eioru]

Can I know about these puzzles' solving method result by SE?

Code: Select all

11.4:
m_b_metcalf:
500000009020100070008000300040702000000050000000006010003000800060004020900000005
StrmCkr:
500000009020100070008000300040002000000050000000706010003000800060004020900000005

11.2:
Ocean's New Year's present for RW
000001020300040500000600007002000001080090030400000800500002000090030400006700000

11.1:
dml 1/07
003000009400000020080600100200004000090800007005030000000900800000005030070010006

11.0:
Mauricio's non minimal puzzle (62 non isomorphic minimals):
600002059520040010003500200300194500010658030005273001004005100030020045750400008

10.9:
Some more puzzles by Mauricio:
300005002040010030009000800500090000020608040004200005006001700010030020400500001
100005004040020030008000700500100000030608010000073005009002600010040020200500003
700000006020030010001500400000190500040600020005273000002005300030010040800000009
100500004070000060002030100020190005004008200500073000003010400080000090200005003

10.8:
dml 3/07
003400080000009200000060001007010000060002000500800040010000900800000030004500007
Another one by Mauricio:
100040030000007004005800700002500080600090002030000400003006000700200000060080001


[StrmCkr]

11.4:
m_b_metcalf:
500000009020100070008000300040702000000050000000006010003000800060004020900000005
StrmCkr:
500000009020100070008000300040002000000050000000706010003000800060004020900000005

solving methods's aren't directly disscussed as there still debated on..

the method of steps is listed on the previous page (not in detail) used for solving each of these two.

this one is for mine.
[Added:] This is Explainers output for the variant (ER 11.4):
61 Hidden Single
4 Pointing
3 Claiming
4 Naked Pair
1 X-Wing
3 Hidden Pair
2 Naked Triplet
1 Swordfish
2 XY-Wing
3 Bidirectional Y-Cycle
3 Turbot Fish
4 Bidirectional Cycle
14 Forcing Chain
2 Nishio Forcing Chains
7 Region Forcing Chains
1 Cell Forcing Chains
1 Dynamic Cell Forcing Chains
1 Dynamic Double Forcing Chains
6 Dynamic Region Forcing Chains
11 Dynamic Contradiction Forcing Chains
5 Dynamic Contradiction Forcing Chains (+)
6 Dynamic Contradiction Forcing Chains (+ Forcing Chains)
6 Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)

and mikes puzzle.

A very difficult and interesting puzzle. It seems to require nested chains with multiple inferences. I have not seen this before.

It is still possible to rate this puzzle with the current version of the Sudoku Explainer. But you need to start the .jar file from a command line, and to use the "-Xmx" option to tell the Java VM to use more memory (by default it only uses a fraction of the available memory). For instance:

java -Xmx500m -jar SudokuExplainer.jar

starts the application and tells the Java VM to use at most 500MB. This should be enough to solve the puzzle.

By the way, if you have installed the full Java JDK (not only the JRE), you may want to use the java command from the jdk, and to also add the "-server" option: the GUI gets less responsive but the long analyses run faster (about 2h20 instead of 3h15 on my computer).

Difficulty rating: 11.4

57 x Hidden Single
2 x Direct Hidden Pair
1 x Naked Single
5 x Pointing
2 x Naked Pair
1 x X-Wing
3 x Hidden Pair
2 x Naked Triplet
1 x Swordfish
1 x XY-Wing
1 x BUG type 1
1 x Forcing X-Chain
1 x Bidirectional Cycle
8 x Forcing Chain
2 x Nishio Forcing Chains
14 x Region Forcing Chains
5 x Cell Forcing Chains
1 x Dynamic Cell Forcing Chains
7 x Dynamic Contradiction Forcing Chains
3 x Dynamic Region Forcing Chains
3 x Dynamic Contradiction Forcing Chains (+)
11 x Dynamic Contradiction Forcing Chains (+ Forcing Chains)
2 x Dynamic Region Forcing Chains (+ Forcing Chains)
5 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)
2 x Dynamic Region Forcing Chains (+ Dynamic Forcing Chains)
4 x Dynamic Contradiction Forcing Chains (+ Dynamic Forcing Chains)

as for the other one's in this link.
http://forum.enjoysudoku.com/viewtopic.php?t=5194

there is a listing of most of the other puzzles and how to solve them. (all using contradictions subnets. found in my post.

[ronk]

Where he later found a cousin by swapping r4c4 & r6c6:

Code: Select all

5.......9
.2.1...7.
..8...3..
.4.6.2...
....5....
.....7.1.
..3...8..
.6...4.2.
9.......5

Wouldn't that be a reflection about the anti-diagonal making puzzles 1 & 2 isomorphic?

I may have mis-identified the anti-diagonal. Sudopedia defines it to run "from left-top to right-bottom". However, that definition is not consistent with the orientation of an anti-diagonal matrix.

[Pat]

I may have mis-identified the anti-diagonal.

Sudopedia defines it to run "from left-top to right-bottom".

However, that definition is not consistent with the orientation of an anti-diagonal matrix.

Sudopedia is wrong

Wikipedia is more mature,
and they got it right --
the main diagonal starts at r1c1 --

the main diagonal
is the diagonal which runs from the top left to the bottom right

[coloin]

Its about time we finally get to the bottom of what makes our hard sudokus hard...- we cant really quantify our ratings until we know this......

The 20 clue from m_b_metcalf has 20 given clues and 61 insertable clues.

Code: Select all

5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5     SE 11.4


It is the hardest according to the SE ratings.....

Lets break it down into the unavoidables......

The sudoku has N number of unavoidables [size 4 - 63][possibly more than 50000 at a guess]
All the unavoidable sets are covered by the 20 given clues. The vast majority of the unavoidable sets are covered by more than one clue.
Each clue covers uniquely a number [n] of unavoidable sets of size [x]
n must be greater than 1 [EDIT - at least 1] to be an essential clue in a minimal sudoku puzzle.

The number of grid solutions for each clue is larger than average but not extraordinary.[This is more a function of the other grid solutions which are irrelevant to the unique grid solution of our puzzle]

If we could look at the unavoidable sets which are uniquely covered [by each clue]

Is n greater than expected ?
Is the average size of x large ?

It would appear on a superficial glance that the sole effect of each given clue reaches out to every empty cell so I think both n and x will tend to be larger than normal.

We have 20 given clues and 61 [correct] insertable clues.

This will give 1830 [61*60 / 2] ways to insert 2 [back-door correct] clues [non-minimally]

I have added two clues - here is one of the easiest, one of the hardest and the original minimal puzzle for comparison.

Code: Select all

suexrat9                                                                                      SE
  59 ,  5.......9.2.1.9.7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9......45     SE 1.5  [all hidden singles]
 832 ,  5.......9.2.1...7...8...3...4.7.2.......5.........6.1.4.3...8...6...4.2.9.2.....5     SE 10.6
1285 ,  5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5     SE 11.4

For some reason the addition of the above 2 clues in the first example makes the puzzle very easy - although it doesnt make any of the original 20 given clues superfluous.[EDIT it does make 2@r4c6 superfluous] The two clues by being there must reduce the value of n and x for some [? all] of the given clues. [EDIT - This is an understatement !]

Is "hardness" an unknown function of n,x, which is consistently high for each given clue ?

C

[m_b_metcalf]

Its about time we finally get to the bottom of what makes our hard sudokus hard...- we cant really quantify our ratings until we know this......

The 20 clue from m_b_metcalf has 20 given clues and 61 insertable clues.

Code: Select all

5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5     SE 11.4


One thing that struck me about this puzzle (from staring at it for so long waiting for SE to solve it), is the symmetery not only of the clue pattern, but of the values themselves. They have an extraordinary degree of symmetry: box 1 reflects box 9, two
values in box 3 reflect those in box 7, the two 'cross-bars' are identical, and the central value is a repeat of r1c1 and r9c9.

Does this play a role?

Regards,

Mike Metcalf

[coloin]

Maybe the symmetry means that the unavoidable sets can be large.

This was the case in Greatest divergance possible in dual solution puzzle?: where the largest unavoidable possible in a 21 clue puzzle was found.

In MM's puzzle there are not many unavoidables specific to the r1c1 clue smaller than 27 clues......

For example here are 2 pseudopuzzles with 2 solutions
The unavoidable set includes the 5@r1c1

Code: Select all

+---+---+---+
|..4|...|289|
|.2.|18.|574|
|7.8|42.|361|
+---+---+---+
|.4.|7.2|658|
|...|.51|43.|
|...|.46|91.|
+---+---+---+
|4.3|21.|896|
|86.|..4|.23|
|9.2|..8|.45|
+---+---+---+ [x = 33 clues]

+---+---+---+
|.1.|...|2.9|
|.26|1..|.7.|
|.98|..5|361|
+---+---+---+
|.4.|7.2|...|
|...|951|...|
|...|.46|.1.|
+---+---+---+
|..3|.1.|8.6|
|.6.|..4|.2.|
|9..|...|1.5|
+---+---+---+  [x = 49 clues]


Probably unremarkable except there could be rather a lot of these........

C

[gsf]

this doesn't take into account unavoidables
but a very simple (and fast) rating correlates with the ER ratings for ravel's most recent list
the rating counts the number of propositions and guesses using singles constraints
and weighs guesses more than propositions

use these option with my solver for the quick rating
%e lists the elapsed time
-e G filters out puzzles that require guessing with the FNP constraints (singles with propositions)
the rating is guesses*100+propositions

Code: Select all

-R'G*100+P' -BX -qFNP -f'%v # %04r' -Ff%e -e G


here is ravels list with the ER and the quick rating

Code: Select all

ER   gsfQ puzzle                                                                            author
11.4,1013,5.......9.2.1...7...8...3...4...2.......5.......7.6.1...3...8...6...4.2.9.......5,StrmCkr
11.4,1008,5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5,m_b_metcalf
11.2,0418,.....1.2.3...4.5.....6....7..2.....1.8..9..3.4.....8..5....2....9..3.4....67.....,Ocean's New Year's present for RW
11.1,0215,..3.....94......2..8.6..1..2....4....9.8....7..5.3.......9..8.......5.3..7..1...6,dml 1/07
11.0,0204,6....2.5952..4..1...35..2..3..1945...1.658.3...5273..1..4..51...3..2..4575.4....8,Mauricio's non minimal
10.9,0510,7.......6.2..3..1...15..4.....19.5...4.6...2...5273.....2..53...3..1..4.8.......9,Mauricio
10.9,0206,1..5....4.7.....6...2.3.1...2.19...5..4..82..5...73.....3.1.4...8.....9.2....5..3,Mauricio
10.9,0205,3....5..2.4..1..3...9...8..5...9.....2.6.8.4...42....5..6..17...1..3..2.4..5....1,Mauricio
10.9,0203,1....5..4.4..2..3...8...7..5..1......3.6.8.1.....73..5..9..26...1..4..2.2..5....3,Mauricio
10.8,0507,1...4..3......7..4..58..7....25...8.6...9...2.3....4....3..6...7..2......6..8...1,Mauricio
10.8,0308,..34...8......92......6...1..7.1.....6...2...5..8...4..1....9..8......3...45....7,dml 3/07
0.397939s


[coloin]

Could you explain the difference betwwen a guess and a proposition ! ?

I think I understand your rating weighting [guesses*100]

Doesnt it depend on which clue you guess as to the ease with which the puzzle succumbs ?

It is possible to analyse all the possible guesses.

20 given clues
61 cells without a clue

total cells without a clue = 61 correct guesses possible,488 possible guesses incorrect.

The analysis of these 488 wrong guesses
All will have a conflict - many will have simple box and row constraint - but many will not reveal a conflict until a long chain reaches one - this happens in difficult puzzles. I cant see milage in differentiating these - after all if a clue is wrong it will reveal conflicts throughout the puzzle.

I think it holds that difficult puzzles have a larger number of large unavoidable sets uniquely covered by one clue.
Certainly the converse is true - easy puzzles tend to have one of the clues [commonly the one with the least grid solutions] which only have a small number of smaller unavoidables uniquely covered by that clue.

I await Red Ed to comment - as I can only make amateurish attempts to find the large unavoidables !

C

[gsf]

Could you explain the difference betwwen a guess and a proposition ! ?

I think I understand your rating weighting [guesses*100]

Doesnt it depend on which clue you guess as to the ease with which the puzzle succumbs ?

It is possible to analyse all the possible guesses.

a proposition step loops over all candidate values, sets a value, and applies the basic constraints
until { solution, contradiction, no-progress }
with -X on solutions are ignored (to nullify lucky backdoor discovery)
-B batches all of the proposition step contradictions until the end of the step and applies them en masse

so propositions with -BX are essentially unbiased guesses

when basic constraints and propositions fail to advance pure guessing is applied
starting with cells with the least number of candidates -- but you're right, luck comes
into play with guesses

nested propositions should take care of this
I was originally concerned about that getting out of hand
but the backdoor conjecture means that limiting to 2 concurrent propositions will be enough
(or the conjecture is refuted)

so when a singleton proposition step fails to advance a pairwise proposition step
could be applied and the number of solutions found in the pairwise step (there'd better be
at least one for the conjecture) would factor into the rating

[gsf]

I coded pairwise propositions in my solver and reposted it
use

Code: Select all

-qquick


for quick rating for the hardest puzzles
the %r format prints the rating which is just a count of the number of batched propositions

for the hardest sudoku pairwise propositions uncover backdoors
those backdoors are not applied until all have been uncovered (and accounted for in the proposition count)
the result is a rating that is emprically immune to automorphic puzzle permutations

you can test it by using the -JN option which re-solves each input puzzle using N permuted
copies of the orginal (e.g., -J100 to solve the original and 100 permuted copies)

btw, you can also use

Code: Select all

-J100 -f%v


to generate a stream of puzzles with 100 permuted copies for other rating progs

here is ravel's list with the quick pairwise proposition ratings

Code: Select all

11.4,15511,5.......9.2.1...7...8...3...4...2.......5.......7.6.1...3...8...6...4.2.9.......5,StrmCkr
11.4,15351,5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5,m_b_metcalf
11.2,12444,.....1.2.3...4.5.....6....7..2.....1.8..9..3.4.....8..5....2....9..3.4....67.....,Ocean's New Year's present for RW
11.1,13473,..3.....94......2..8.6..1..2....4....9.8....7..5.3.......9..8.......5.3..7..1...6,dml 1/07
11.0,10860,6....2.5952..4..1...35..2..3..1945...1.658.3...5273..1..4..51...3..2..4575.4....8,Mauricio's non minimal
10.9,10940,7.......6.2..3..1...15..4.....19.5...4.6...2...5273.....2..53...3..1..4.8.......9,Mauricio
10.9,10940,1..5....4.7.....6...2.3.1...2.19...5..4..82..5...73.....3.1.4...8.....9.2....5..3,Mauricio
10.9,10940,3....5..2.4..1..3...9...8..5...9.....2.6.8.4...42....5..6..17...1..3..2.4..5....1,Mauricio
10.9,10944,1....5..4.4..2..3...8...7..5..1......3.6.8.1.....73..5..9..26...1..4..2.2..5....3,Mauricio
10.8,08932,1...4..3......7..4..58..7....25...8.6...9...2.3....4....3..6...7..2......6..8...1,Mauricio
10.8,14469,..34...8......92......6...1..7.1.....6...2...5..8...4..1....9..8......3...45....7,dml 3/07
3.070533s


the last one does not correlate with SE
how consistent is SE with permuted copies?
here are 10 generated by -J10 for testing

Code: Select all

..6.1.....9...2...4..8....5..1.....78..4...3..2....9.......61.....5...8.3...7...4
..9..2....4.8..5..6...1.....8.4....31.....7....2....9......6.1..3..7.4.....5....8
.4.8..3..6...1......9..2...1.....7...8.4....5..2....6....3....8.5..7.4.......9.1.
....3...8.5...7.4....9..1...4..8..3...6..1...9..2.......1....7..8..4...52.....6..
1......6...8.3...4.2....9......7..1......62....45....8..38.....7...4...5.9...1...
..34...7.....1.6.......8..52...9......8..3..4.1.7.....9.....2....45....8.6.....1.
5..4....7.....1.9.....8.3...1.7.....8...5.4....2..6....6......14..3..8....9....2.
....1.7....4..8..3...2...9..1..6......8..45..2..9.....6......1...5.....8.7...34..
.5...4..8...9...2.....6.1..3....8..4..92......7..1.....4...37..8.......5..1....6.
....5.8.....6....1.3...7.4.6....1.....92......4..8..5...2.....9.8..4.3..1......7.


[ravel]

when basic constraints and propositions fail to advance pure guessing is applied starting with cells with the least number of candidates...

gsf,
i didn't understood exactly, how your quick rating (in both versions) works. I had expected that the first version would corellate good with dukusos suexrat9, but it doesn't.
When stuck, often strongly linked (conjugated pair) candidates are a better choice for a try to eliminate them than bivalue candidates, because you do not only get a number, but also more candidates can be eliminated immediately.

I only had a quick look now at your last quick rating. Could you explain, what you mean with ?

those backdoors are not applied until all have been uncovered (and accounted for in the proposition count)

The new rating correlates better with mine. dml 3/07 is number 5 in my current top list (as i already said, i'm not satisfied with my rating, still hoping for a good idea, that would allow me to improve it with slight canges ).
I also want to say, that (as i see it), the quick ratings like Explainer's only rate the hardest step, not the amount of very hard steps, as my program does (in a more or less good way).

[gsf]

when basic constraints and propositions fail to advance pure guessing is applied starting with cells with the least number of candidates...

gsf,
i didn't understood exactly, how your quick rating (in both versions) works. I had expected that the first version would corellate good with dukusos suexrat9, but it doesn't.
When stuck, often strongly linked (conjugated pair) candidates are a better choice for a try to eliminate them than bivalue candidates, because you do not only get a number, but also more candidates can be eliminated immediately.

from my ancient understanding of suexrat9, it basically takes metrics from a backtraking
solver that is presented with N permuted copies of the same puzzle, with some formula
for combining the different results

the first rating I posted yesterday that counted guesses suffers from a similar bias as suexrat9 because
cell values are assigned as the backtrack search progresses, which allows either good
or bad choices early on to bias the rest of the search

I only had a quick look now at your last quick rating. Could you explain, what you mean with ?

those backdoors are not applied until all have been uncovered (and accounted for in the proposition count)

The new rating correlates better with mine. dml 3/07 is number 5 in my current top list (as i already said, i'm not satisfied with my rating, still hoping for a good idea, that would allow me to improve it with slight canges ).
I also want to say, that (as i see it), the quick ratings like Explainer's only rate the hardest step, not the amount of very hard steps, as my program does (in a more or less good way).

right
so there are tradeoffs
* differences due to input puzzle permutations
* counting the number of methods required to get to a solution could be expensive
* counting only the hardest method could hide the effects of uncounted almost-hardest methods

the second method I posted addresses these issues by
* using naked and hidden singles only
* singleton proposition logic that looks at all single cell assignments and counts the propositions
only after all assigments have been tested
(this part is done stepwise by partitioning the cells by the number of candidates
and operating on all cells with the least number of candidates first, ending the step
when any cell with i candidates progresses the puzzle)
* pairwise proposition logic that assigns all cells pairwise and counts the propositions
(using the same stepwise partitioning as singleton propositions)

if the backdoor conjecture holds then puzzles that foil singleton propositions will fall to pairwise propositions
contradictions and backdoors found during the pairwise propositions are also batched
and not applied until all pairs are tested (for rating they don;t need to be applied -- discovery
of any backdoor in this step means the puzzle is solved)

you can use the -J option of my solver to generate a stream of permutations of one puzzle
to test if the -qquick rating, SE, or any other ratings, are biased on input puzzle layout