## The hardest sudokus

Everything about Sudoku that doesn't fit in one of the other sections
ravel wrote:These are the ratings for Oceans puzzles. The last line shows the Explainer rating, where the "9." is omitted.
Code: Select all
` 1  2  3  4  5   6   7  8  9 10  11 12 13 14 15 16 17 18 7, 5, 8, 5, 7, 10, 12, 5, 4, 5, 15, 7, 7, 7, 5,12, 5, 3 5  2  4  3  4   8   9  3  1  2   4  3  2  2  3  3  3 8.4 `

Thanks again ravel for analyzing the puzzles.

The screening process brought forward about four puzzles per 100.000. Most of these made it to the list, but the score was higher than expected for some of them. The only thing I did was search the diagonal pattern for lots of puzzles, and then try to pick the most prospective.

My logical solver could solve only 20-25% of the diagonal puzzles. The un-scientific statistics for the basic screening criterium showed a rather peaky distribution pattern:
Code: Select all
`# Diagonal pattern - Rough distribution of r.   r         >1000:     0.001%900-1000:  0.002%800-900:   0.005%700-800:   0.02%600-700:   0.07%500-600:   0.4%400-500:   1.5%300-400:   5%200-300:  20%100-200:  55%50-100:   18%<50:       0`

Thanks to tso and r.e.s. for thorough comparision between the various rating principles.
Ocean

Posts: 442
Joined: 29 August 2005

The hardest rated puzzle (9.8), which the author of Sudoku Explainer, Nicolas Juillerat, (told me he) has found in a list similar to the top1465, needed 11 steps in my program and goes to the top 10 in my list. I found it there (the page also has nice samples for different techniques). Not very surprising, it has an almost diagonal pattern:
Code: Select all
` +-------+-------+-------+ | 7 . . | . . . | 4 . . | | . 2 . | . 7 . | . 8 . | | . . 3 | . . 8 | . . 9 | +-------+-------+-------+ | . . . | 5 . . | 3 . . | | . 6 . | . 2 . | . 9 . | | . . 1 | . . 7 | . . 6 | +-------+-------+-------+ | . . . | 3 . . | 9 . . | | . 3 . | . 4 . | . 6 . | | . . 9 | . . 1 | . 3 5 | +-------+-------+-------+`
The ratings of Explainer and mine are somewhat contrary. While Explainer only rates the hardest needed step, my program rates the minimum number of (probably) hard steps needed. So i think that a combination of both ratings is a good measure for the toughest.
ravel

Posts: 998
Joined: 21 February 2006

It has been interesting to watch all this new development in producing hard sudukos the last couple of weeks. Good work!

However, it is disapointing to discover, that most solvers did not produce a constant rating of a puzzle, when the puzzle is scrampled. You should expect that. The new discovered solver, Sudoku Explainer, seems to be better in this regard, and in the same time it is able to break all known sudokus. The rating from the Explainer is based on the worst chain (I suppose longest) used in the solving proces. It do not rate the number of steps. I have counted the number of steps for some of the top sudokus below:

Code: Select all
`Sudoku name  Explainer Explainer steps  Ravel solver              rating      rated >=4        steps  Ocean #7/18:  9.9           61              12Ocean #3/3:   9.9           51              11top1465 #77:  9,8           46              10Ocean #6/18:  9.8           53              10Ocean #1/3:   9.5           45              11Ocean #1/18   9.5           54               7Ocean #11/18  9.4           68              15tso #7/31:    9.4           43              12tso #3/31:    9.4           52               7top1465 #89:  9,3           51              10 `

However some of the steps may not be nescessary in order to solve the puzzle. Well I don't think the table above make any new discoveries.

The rating from the Explainer is like this (copy from Explainer web-site):

1.0: Last value in block, row or column
1.2: Hidden Single in block
1.5: Hidden Single in row or column
1.7: Direct Pointing
1.9: Direct Claiming
2.0: Direct Hidden Pair
2.3: Naked Single
2.5: Direct Hidden Triplet
2.6: Pointing
2.8: Claiming
3.0, 3.2, 3.4: Naked Pair, X-Wing, Hidden Pair
3.6, 3.8, 4.0: Naked Triplet, Swordfish, Hidden Triplet
4.2, 4.4: XY-Wing, XYZ-Wing
4.5 - 5.0: Unique rectangles and loops
5.0, 5.2, 5.4: Naked Quad, Jellyfish, Hidden Quad
5.6 - 6.0: Bivalue Universal Graves
6.2: Aligned Pair Exclusion
6.5 - 7.5: Bidirectioal X-Cycles and Y-Cycles
6.6 - 7.6: Forcing X-Chains
7.0 - 8.0: Forcing Chains, Bidirectional Cycles
7.5 - 8.5: Nishio
8.0 - 9.0: Cell/Region Forcing Chains
8.5 - 9.5: Dynamic Forcing Chains
9.0 - 10.0: Dynamic Forcing Chains (+)

Can anyone tell the difference between the last four lines?

The Sudoku Explainer do also have some shortcommings. In the example below an elimination of a candidate can be made manually using 22 links (with no special tricks). The Explainer uses 52 links (I think so). Possibly such a "monster chain" cause the rating by the Explainer to increase abnormally for a puzzle. The Explainer errornets produce a contradiction on a candidate value in a cell to be true or false.

The contradiction, "empty cell" is never used and therefore extra links may be needed to reach a contradiction. Another reason could be, that is just not able to find the shortest chain.

The number of links to produce the rating 9.9 seems to be 68 for Ocean #7/18.

Example from no.89 of top1465:
Code: Select all
` 1469   124    468    | 3      267    78     | 5      24689  4689   469    5      2468   | 69     1      28     | 7      3      468    39     238    7      | 5689   256    4      | 69     2689   1     ----------------------+----------------------+---------------------- 2      378    9      | 158    357    13578  | 4      1678   3568   345    6      348    | 12458  9      123578 | 138    178    358    345    3478   1      | 458    3457   6      | 389    789    2     ----------------------+----------------------+---------------------- 8      14     346    | 7      3456   135    | 2      1469   3469   7      9      2346   | 1246   8      123    | 136    5      346    1346   1234   5      | 146    2346   9      | 138    1468   7     `

My manual errornet for eliminating 3 from r7c9 is like this:
Code: Select all
`[r7c9](-3-[r7c3])       (-3-[r45c9])       (-3-[r8c9])       =9=[r7c8]-9-[r6c8]=9=[r6c7]=3=[r5c7]-3-[r5c3]=3=[r8c3]=2=[r9c2]-2-[r13c2]=2=[r2c3]           -2-[r2c6](-8-[r2c9])                    -8-[r1c6]-7-[r5c6]=7=[r5c8]=1=[r4c8]=6=[r4c9](-6-[r2c9])                                                                 -6-[r8c9]-4-[r2c9] => empty cell r2c9 => r7c9<>3`

This errornet produce the contradiction (empty cell) using 22 links.

The exsact same puzzle was given to the Sudoku Explainer. It produces the elimination using 52 links and the contradicion is the value being 6 or not 6. Here is the text copied from the program:

Dynamic Contradiction Forcing Chains
With this rule, we will prove the two following assertions:

If R7C9 contains the value 3, then R4C8 must contain the value 6
If R7C9 contains the value 3, then R4C8 cannot contain the value 6

Because the same assumption yields to contradictory results, we can conclude that the assumption is false, that is, R7C9 cannot contain the value 3.
Each assertion is proved by a different chain of simple rules. The chains can be dynamic, which means that the conclusions of multiple sub-chains must be combined in some cases.
The details of each chain are given below. Use the view selector below the grid to switch between the graphical illustrations of the two different chains.
Chain 1: If R7C9 contains the value 3, then R4C8 cannot contain the value 6 (View 1):
(1) If R7C9 contains the value 3, then R7C9 cannot contain the value 9 (the cell can contain only one value)
(2) If R7C9 does not contain the value 9, then R7C8 must contain the value 9 (only remaining possible position in the block)
(3) If R7C8 contains the value 9, then R6C8 cannot contain the value 9 (the value can occur only once in the column)
(4) If R6C8 does not contain the value 9, then R6C7 must contain the value 9 (only remaining possible position in the block)
(5) If R6C7 contains the value 9, then R6C7 cannot contain the value 3 (the cell can contain only one value)
(6) If R7C9 contains the value 3 (initial assumption), then R4C9 cannot contain the value 3 (the value can occur only once in the column)
(7) If R7C9 contains the value 3 (initial assumption), then R5C9 cannot contain the value 3 (the value can occur only once in the column)
(8) If R5C9 does not contain the value 3, R4C9 does not contain the value 3 (6) and R6C7 does not contain the value 3 (5), then R5C7 must contain the value 3 (only remaining possible position in the block)
(9) If R5C7 contains the value 3, then R5C3 cannot contain the value 3 (the value can occur only once in the row)
(10) If R7C9 contains the value 3 (initial assumption), then R7C3 cannot contain the value 3 (the value can occur only once in the row)
(11) If R7C3 does not contain the value 3 and R5C3 does not contain the value 3 (9), then R8C3 must contain the value 3 (only remaining possible position in the column)
(12) If R8C3 contains the value 3, then R8C3 cannot contain the value 2 (the cell can contain only one value)
(13) If R8C3 does not contain the value 2, then R2C3 must contain the value 2 (only remaining possible position in the column)
(14) If R2C3 contains the value 2, then R2C6 cannot contain the value 2 (the value can occur only once in the row)
(15) If R2C6 does not contain the value 2, then R2C6 must contain the value 8 (only remaining possible value in the cell)
(16) If R2C6 contains the value 8, then R2C9 cannot contain the value 8 (the value can occur only once in the row)
(17) If R7C9 does not contain the value 9 (1), then R1C9 must contain the value 9 (only remaining possible position in the column)
(18) If R1C9 contains the value 9, then R3C7 cannot contain the value 9 (the value can occur only once in the block)
(19) If R3C7 does not contain the value 9, then R3C7 must contain the value 6 (only remaining possible value in the cell)
(20) If R3C7 contains the value 6, then R2C9 cannot contain the value 6 (the value can occur only once in the block)
(21) If R2C9 does not contain the value 6 and R2C9 does not contain the value 8 (16), then R2C9 must contain the value 4 (only remaining possible value in the cell)
(22) If R2C9 contains the value 4, then R1C8 cannot contain the value 4 (the value can occur only once in the block)
(23) If R7C8 contains the value 9 (2), then R7C8 cannot contain the value 4 (the cell can contain only one value)
(24) If R7C8 does not contain the value 4 and R1C8 does not contain the value 4 (22), then R9C8 must contain the value 4 (only remaining possible position in the column)
(25) If R9C8 contains the value 4, then R9C8 cannot contain the value 6 (the cell can contain only one value)
(26) If R3C7 contains the value 6 (19), then R1C8 cannot contain the value 6 (the value can occur only once in the block)
(27) If R3C7 contains the value 6 (19), then R3C8 cannot contain the value 6 (the value can occur only once in the block)
(28) If R7C8 contains the value 9 (2), then R7C8 cannot contain the value 6 (the cell can contain only one value)
(29) If R7C8 does not contain the value 6, R3C8 does not contain the value 6 (27), R1C8 does not contain the value 6 (26) and R9C8 does not contain the value 6 (25), then R4C8 must contain the value 6 (only remaining possible position in the column)

Chain 2: If R4C8 must contain the value 6, then R4C8 cannot contain the value 6 (View 2):
(1) If R7C9 contains the value 3, then R7C9 cannot contain the value 9 (the cell can contain only one value)
(2) If R7C9 does not contain the value 9, then R7C8 must contain the value 9 (only remaining possible position in the block)
(3) If R7C8 contains the value 9, then R6C8 cannot contain the value 9 (the value can occur only once in the column)
(4) If R6C8 does not contain the value 9, then R6C7 must contain the value 9 (only remaining possible position in the block)
(5) If R6C7 contains the value 9, then R6C7 cannot contain the value 3 (the cell can contain only one value)
(6) If R7C9 contains the value 3 (initial assumption), then R4C9 cannot contain the value 3 (the value can occur only once in the column)
(7) If R7C9 contains the value 3 (initial assumption), then R5C9 cannot contain the value 3 (the value can occur only once in the column)
(8) If R5C9 does not contain the value 3, R4C9 does not contain the value 3 (6) and R6C7 does not contain the value 3 (5), then R5C7 must contain the value 3 (only remaining possible position in the block)
(9) If R5C7 contains the value 3, then R5C3 cannot contain the value 3 (the value can occur only once in the row)
(10) If R7C9 contains the value 3 (initial assumption), then R7C3 cannot contain the value 3 (the value can occur only once in the row)
(11) If R7C3 does not contain the value 3 and R5C3 does not contain the value 3 (9), then R8C3 must contain the value 3 (only remaining possible position in the column)
(12) If R8C3 contains the value 3, then R8C3 cannot contain the value 2 (the cell can contain only one value)
(13) If R8C3 does not contain the value 2, then R2C3 must contain the value 2 (only remaining possible position in the column)
(14) If R2C3 contains the value 2, then R2C6 cannot contain the value 2 (the value can occur only once in the row)
(15) If R2C6 does not contain the value 2, then R2C6 must contain the value 8 (only remaining possible value in the cell)
(16) If R2C6 contains the value 8, then R1C6 cannot contain the value 8 (the value can occur only once in the block)
(17) If R1C6 does not contain the value 8, then R1C6 must contain the value 7 (only remaining possible value in the cell)
(18) If R1C6 contains the value 7, then R5C6 cannot contain the value 7 (the value can occur only once in the column)
(19) If R5C6 does not contain the value 7, then R5C8 must contain the value 7 (only remaining possible position in the row)
(20) If R5C8 contains the value 7, then R5C8 cannot contain the value 1 (the cell can contain only one value)
(21) If R5C7 contains the value 3 (8), then R5C7 cannot contain the value 1 (the cell can contain only one value)
(22) If R5C7 does not contain the value 1 and R5C8 does not contain the value 1 (20), then R4C8 must contain the value 1 (only remaining possible position in the block)
(23) If R4C8 contains the value 1, then R4C8 cannot contain the value 6 (the cell can contain only one value)

/Viggo
Viggo

Posts: 60
Joined: 21 April 2006

In case someone might be interested to see a puzzle that Explainer rates (at least slightly-)differently before & after 180-degree rotation ...

Code: Select all
`.....5.897.....2...9.32...1...6..4.7....3....6.8..9...4...12.7...1.....235.8.....Difficulty rating: 8.6 / 1053 x Hidden Single 3 x Direct Hidden Pair 6 x Pointing 2 x Claiming 1 x Naked Pair 1 x Hidden Pair 1 x XYZ-Wing 1 x Unique Rectangle type 1 1 x Bidirectional Cycle 4 x Forcing Chain 16 x Region Forcing Chains 1 x Cell Forcing Chains .....8.532.....1...7.21...4...9..8.6....3....7.4..6...1...23.9...2.....798.5.....Difficulty rating: 8.5 / 1050 x Hidden Single 2 x Direct Hidden Pair 3 x Naked Single 9 x Pointing 2 x Claiming 1 x Hidden Pair 1 x XYZ-Wing 1 x BUG type 1 2 x Bidirectional Y-Cycle 1 x Turbot Fish 3 x Bidirectional Cycle 6 x Forcing Chain 14 x Region Forcing Chains 1 x Cell Forcing Chains `

I was a bit disappointed to see unique-solution strategies included in the rating process -- not because I dislike those strategies, but because I think there's a case to be made for rating a puzzle as though one doesn't know its origin.

IMO there's a place for both kinds of rating -- one that measures how difficult it is to solve a puzzle in a way that allows one to state
"This puzzle has a unique solution, and this is it ..."
and another that measures how hard it is solve in a way that allows one to state
"If this puzzle has a unique solution, then this is it ..."
Last edited by r.e.s. on Fri Jul 07, 2006 3:35 pm, edited 1 time in total.
r.e.s.

Posts: 337
Joined: 31 August 2005

ravel wrote:The hardest rated puzzle (9.8), which the author of Sudoku Explainer, Nicolas Juillerat, (told me he) has found in a list similar to the top1465, needed 11 steps in my program and goes to the top 10 in my list. I found it there (the page also has nice samples for different techniques). Not very surprising, it has an almost diagonal pattern:
Code: Select all
` +-------+-------+-------+ | 7 . . | . . . | 4 . . | | . 2 . | . 7 . | . 8 . | | . . 3 | . . 8 | . . 9 | +-------+-------+-------+ | . . . | 5 . . | 3 . . | | . 6 . | . 2 . | . 9 . | | . . 1 | . . 7 | . . 6 | +-------+-------+-------+ | . . . | 3 . . | 9 . . | | . 3 . | . 4 . | . 6 . | | . . 9 | . . 1 | . 3 5 | +-------+-------+-------+`
The ratings of Explainer and mine are somewhat contrary. While Explainer only rates the hardest needed step, my program rates the minimum number of (probably) hard steps needed. So i think that a combination of both ratings is a good measure for the toughest.

This is puzzle top1465 #77 with one extra clue in [r9c8]=3. Puzzle #77 has a full diagonal pattern.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

daj95376 wrote:This is puzzle top1465 #77 with one extra clue in [r9c8]=3. Puzzle #77 has a full diagonal pattern.

Ah, thank you, i did not notice it. I will remove it from the list. I only check new puzzles for equivalence.
As i said, i found the 10 steps with my old program version, which did not use all possible eliminations. In this case it gave a shorter solution than the 4 equivalent puzzles (with the additional clue) i tried this time.
ravel

Posts: 998
Joined: 21 February 2006

Hi Viggo,

to give a quick answer:
Without having looked at your error net in detail, i am sure, that it gives a much shorter chain. I dont believe that it it is possible, that a program could calculate the shortest possible chain so quickly (though i was impressed by the speed of programs, i.e by dukuso and gsf). On the other hand in average Explainer's chains will be same good or bad for all puzzles.

Nicolas wrote me:
For forcing-chain-like techniques, the rating also takes the length of the
implication chain into account. For instance, a simple Forcing Chain of 6
implications or less is rated 7.0. But with 45 implications it is rated 7.7.
More precisely, I add 0.1 each time the number of implications is greater
than 6, 8, 10, 14, 18, 26, 34, 50, 66, 98.

Note that all these values are arbitrary. There is no real theory behind
them, except a few experiments. I do not pretend they are "the" ratings at
all.

When the Sudoku Explainer has to use a kind of forcing-chains, it always
does an exhaustive search of all chains of that kind, and then uses the
shortest one.

...
Other questions are welcome, but do not expect me to answer quickly because
I am quite busy...

You can find his email address on his site.

Viggo wrote:However some of the steps may not be nescessary in order to solve the puzzle.

Certainly
7.5 - 8.5: Nishio
8.0 - 9.0: Cell/Region Forcing Chains
8.5 - 9.5: Dynamic Forcing Chains
9.0 - 10.0: Dynamic Forcing Chains (+)

Can anyone tell the difference between the last four lines?

As i understand it, Nishio are chains with one number only (but here i suppose they would not catch all template eliminations, because at least some need chains using x-wings)
Cell/Region Forcing Chains are, what is known as multiple forcing chains.
"Dynamic" is, what Jeff called "multiple inference", i.e. that implications use former deducted results.
I dont know yet the difference between the last 2 ones.
ravel

Posts: 998
Joined: 21 February 2006

Hi r.e.s.,

thanks for the sample with different ratings. In this case i could explain it with the fact, that uniqueness methods were used. When a pattern is "destroyed" by using another chain first, the puzzle could become harder.

Of course i agree, that parallel ratings for solutions with or without using uniqueness would be fine, but as you can see, we have still big problems to find any relevant rating. So this point has minor priority for me.
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:In this case i could explain it with the fact, that uniqueness methods were used. When a pattern is "destroyed" by using another chain first, the puzzle could become harder.

I think this wouldn't happen in a properly implemented unique-solution strategy based on unavoidable sets, because the relevant pattern (the potential unavoidable set -- not the candidate pattern) can't be destroyed that way, and would still lead to the same deductions. <This puzzle> is a case in point -- the potential 4-9-4-9 "unavoidable rectangle" there would allow deductions both before and after the candidates have been reduced by some strategy from 469-3469-49-49 to 46-9-4-9 (the puzzle wouldn't get harder at all).

Without more details about Explainer, it's hard to say what's really going on.
r.e.s.

Posts: 337
Joined: 31 August 2005

ravel wrote:Without having looked at your error net in detail, i am sure, that it gives a much shorter chain.

I have looked on the matter ones more, and there is one difference - so Ravel, you are right. When the Explainer express a chain, it do include the link between candidates inside a cell - I did not do that for the manual chain. I shall use this Explainer definition when counting links below. For the example above the Explainer chains had 54 links, and now I got 30 links manually - it may still be more than Ravel likes .

I have tried the Explainer on the top1465 #89 ones more and included the reductions as examples in the rating table:

The puzzle is: ...3..5...5..1..3...7..4..12.....4...6..9......1..6..28..7..2...9..8..5...5..9..7

I have added a few examples from Ocean #7/18 marked by *

6.5 - 7.5: Bidirectioal X-Cycles and Y-Cycles
Examples:
6.6 Continuous Nice Loop with 8 links (Y-cycle, Special case involving bivalue cells)
7.0 Continuous Nice Loop with 22 links (Y-cycle, Special case involving bivalue cells - coloring)

7.0 - 8.0: Forcing Chains, Bidirectional Cycles
Examples:
7.1 Discontinuous Nice Loop with 7 links
7.2 Discontinuous Nice Loop with 9 links
7.3 Discontinuous Nice Loop with 11 links
7.1 Continuous Nice Loop with 8 links

7.5 - 8.5: Nishio
Examples:
7.6 Discontinuous Nice Loop with 6 links including one grouped strong link
7.6 Discontinuous Nice Loop with 6 links including one grouped strong link
7.8 Discontinuous Nice Loop with 9 links including two grouped strong links

8.0 - 9.0: Cell/Region Forcing Chains
Examples:
8.4 Single Implication Network with 13 links (This is a triple implication chain from one unit. There is no more than these three single chains which all eliminate one candidate in another cell)
8.4 Single Implication Network with 13 links (This is a triple implication chain from one unit. There is no more than these three single chains which all eliminate one candidate in another cell)
8.4 Single Implication Network with 15 links (This is a triple implication chain from one cell. There is no more than these three single chains which all eliminate one candidate in another cell)
8.3 Single Implication Network with 11 links (This is a triple implication chain from one cell. There is no more than these three single chains which all eliminate one candidate in another cell)

8.5 - 9.5: Dynamic Forcing Chains
Examples:
9.0 Single Implication Network with 17 links including one grouped strong link (manually 16 links)
9.0 Single Implication Network with 16 links including one grouped strong link
9.0 Single Implication Network with 19 links including one grouped strong link (manually 31 links)
9.2 Single Implication Network with 47 links (manually 41 links)
9.3 Single Implication Network with 54 links (manually 30 links)
9.2 Single Implication Network with 33 links
9.2 Single Implication Network with 38 links (manually 34 links)
9.0 Single Implication Network with 24 links (manually 22 links)
9.2 Single Implication Network with 35 links (manually 26 links)
9.2 Single Implication Network with 39 links
9.2 Single Implication Network with 41 links
9.3 Single Implication Network with 48 links
9.2 Single Implication Network with 32 links (This was started as a triple implication chain from one cell)
8.8 Single Implication Network with 11 links
9.4* Single Implication Network with 92 links
9.5* Single Implication Network with 103 links

9.0 - 10.0: Dynamic Forcing Chains (+)
Examples:
9.9* Single Implication Network with 68 links (2 times hitten pair in chains)

ravel wrote:Nicolas wrote me:

For forcing-chain-like techniques, the rating also takes the length of the
implication chain into account. For instance, a simple Forcing Chain of 6
implications or less is rated 7.0. But with 45 implications it is rated 7.7.
More precisely, I add 0.1 each time the number of implications is greater
than 6, 8, 10, 14, 18, 26, 34, 50, 66, 98.

This is not exactly as I have discovered. Some of the examples gives 0.1 point more than this rule.

The Explainer reductions rated >=7 ends with an implication on one candidate. This candidate may true, false or both (both equals contradiction that can cause an elimination from the start assumption). The Explainer may start with triple implication chain trying every appearance of one candidate value in a unit, and the chains all eliminating one other candidate in another cell. You may reverse all these chains and start as an error net and then all candidates of one value is suppressed in the unit from the previous start point. I have therefore named such reductions below as "Single Impication Network", because the logic is the same.

Evantually I have discovered a few reductions by the Explainer starting with the three candidates of one cell in turn and leading to eliminating the same candidate in another cell. This is equivalent to a Single Implication Network leading to an empty cell. However this reduction type seems seldom by the Explainer, and I think this fact may the reason to why I'am able to discover simpler reductions manually.

The only reason why the Ocean #7/18 is rated 9.9 (and not 9.5) is, that two hidden pairs are used in one Single Implication Network. I think this is the difference between two last scaling ranges of the rating. In my opinion this difference is weighted too high on the rating.

It seems like the Explainer finds very large Single Implication Networks before it starts to use some ALS techniques.

ravel wrote:On the other hand in average Explainer's chains will be same good or bad for all puzzles.

Yes, but it adds some uncertainty on the rating, when a few too long chains can determine the rating.

ravel wrote:Note that all these values are arbitrary. There is no real theory behind them, except a few experiments. I do not pretend they are "the" ratings at all.

Please do not regard my comments as a critique. I just try to understand some of the ratings better and make my comments.

/Viggo
Viggo

Posts: 60
Joined: 21 April 2006

Thanks again, r.e.s. and Viggo, for your comments.
I invited Nicolas to read it, when he can find some time.
ravel

Posts: 998
Joined: 21 February 2006

Viggo wrote:Example from no.89 of top1465:
Code: Select all
` 1469   124    468    | 3      267    78     | 5      24689  4689   469    5      2468   | 69     1      28     | 7      3      468    39     238    7      | 5689   256    4      | 69     2689   1     ----------------------+----------------------+---------------------- 2      378    9      | 158    357    13578  | 4      1678   3568   345    6      348    | 12458  9      123578 | 138    178    358    345    3478   1      | 458    3457   6      | 389    789    2     ----------------------+----------------------+---------------------- 8      14     346    | 7      3456   135    | 2      1469   3469   7      9      2346   | 1246   8      123    | 136    5      346    1346   1234   5      | 146    2346   9      | 138    1468   7     `

My manual errornet for eliminating 3 from r7c9 is like this:
Code: Select all
`[r7c9](-3-[r7c3])       (-3-[r45c9])       (-3-[r8c9])       =9=[r7c8]-9-[r6c8]=9=[r6c7]=3=[r5c7]-3-[r5c3]=3=[r8c3]=2=[r9c2]-2-[r13c2]=2=[r2c3]           -2-[r2c6](-8-[r2c9])                    -8-[r1c6]-7-[r5c6]=7=[r5c8]=1=[r4c8]=6=[r4c9](-6-[r2c9])                                                                 -6-[r8c9]-4-[r2c9] => empty cell r2c9 => r7c9<>3`

This errornet produce the contradiction (empty cell) using 22 links.

An errornet apparently does not have a uniquely expressible contradiction, since the contradiction depends upon which multiple inference path is advanced first. For example ...
Code: Select all
`r7c9(=9=r1c9-9-r3c7-6-r2c9)    (-3-r7c3)    (-3-r89c7)     =9=r7c8-9-r6c8=9=r6c7=3=r5c7-3-r5c3=3=r8c3=2=r2c3-2-r2c6-8-(r1c6-7-r5c6=7=r5c8)                                                                 r2c9-4-r8c9=4=r9c8=6=r4c8    implies no cell for digit 1 in box 6, implies r7c9<>3`

... has the contradiction in box 6 instead of r2c9, but it's the same "net" AFAICT.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Another question:
This is the 9.5-rated puzzle, which was solved by my program in 3 steps (and therefore does not make it to the hardest list). Since i agree with Viggo, that Explainer probably would miss some ALS's, i wonder, if other programs could solve it without long chains.
Code: Select all
`7.8...3.....2.1...5.........4.....263...8.......1...9..9.6....4....7.5...........`
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:Another question:
This is the 9.5-rated puzzle, which was solved by my program in 3 steps (and therefore does not make it to the hardest list). Since i agree with Viggo, that Explainer probably would miss some ALS's, i wonder, if other programs could solve it without long chains.
Code: Select all
`7.8...3.....2.1...5.........4.....263...8.......1...9..9.6....4....7.5...........`

I think this puzzle originates from groyle's collection of 18s, and is also known as top1465 #2 (which means it scores high on dukuso's rating program). Here is the earliest reference I could find.

Solving the puzzle is discussed here:Sudoku Discussions: An interesting puzzle.
In another website it is used extensively as a GUI example for a solver program.
Also mentioned in Ruud's benchmark list.
Ocean

Posts: 442
Joined: 29 August 2005

ronk wrote:An errornet apparently does not have a uniquely expressible contradiction, since the contradiction depends upon which multiple inference path is advanced first. For example ...
Code: Select all
`r7c9(=9=r1c9-9-r3c7-6-r2c9)     (-3-r7c3)     (-3-r89c7)      =9=r7c8-9-r6c8=9=r6c7=3=r5c7-3-r5c3=3=r8c3=2=r2c3-2-r2c6-8-(r1c6-7-r5c6=7=r5c8)                                                                  r2c9-4-r8c9=4=r9c8=6=r4c8     implies no cell for digit 1 in box 6, implies r7c9<>3 `

... has the contradiction in box 6 instead of r2c9, but it's the same "net" AFAICT.

Yes, you are right, the contradiction can be made in many ways, and your net here has one link less than mine. Most of the links are the same. I am however able to reduce my error net by two links:

Code: Select all
`[r7c9](-3-[r7c3])       (-3-[r45c9])       (-3-[r8c9])       =9=[r7c8]-9-[r6c8]=9=[r6c7]=3=[r5c7]-3-[r5c3]=3=[r8c3]=2=[r2c3]           -2-[r2c6](-8-[r2c9])                    -8-[r1c6]-7-[r5c6]=7=[r5c8]=1=[r4c8]=6=[r4c9](-6-[r2c9])                                                                 -6-[r8c9]-4-[r2c9] => empty cell r2c9 => r7c9<>3`

Actually the errornet from the Explainer is also very similar. When you study the deductions in detail above the two views have the first 15 deductions equal and several more arguments are repeated. I have made the NLN-notation of the Explainer deductions below (with no repetitions):

Code: Select all
`[r7c9](=9=[r7c8]-9-[r6c8]=9=[r6c7])      (-3-[r4c9])      (-3-r5c9]=3=[r5c7]-3-[r5c3])      (-3-[r7c3]=3=[r8c3]=2=[r2c3]-2-[r2c6]-8-[r2c9])      {=9=[r1c9]-9-[r3c7](-6-[r2c9]-4-[r1c8]=4=[r9c8])                         (-6-[r1c8])                         -6-[r3c8]=6=[r4c8]}   [r2c6]-8-[r1c6]-7-[r5c6]=7=[r5c8]=1=[r4c8]=> r4c8 is both 1 and 6 (contradiction) => r7c9<>3`

When I count the links here it becomes only 31 links!

So the Explainer seems able to find a small optimized error net. However when the Explainer express the deductions, it repeat some deductions two or more times, and the repeated deductions are also used in the rating of the puzzle.

/Viggo
Viggo

Posts: 60
Joined: 21 April 2006

PreviousNext