The New Sudoku Players' Forum

[Havard]

great stuff Mike!
How many on top1465 do you do now?

Havard

[Mike Barker]

1265 at last count. I still can't solve #77 which Carcul was able to do so there is still room for improvement. I'm planning on expanding the Kraken techniques to allow for longer "tentacles" (the current limit is only 2 elements per) and to look at continuous networks more along the lines of multiple inference nice loops or some of Steve K's ideas.

[Ocean]

There have been several changes since the last time I updated my method hierarchy results. ...

Thank you Mike for the statistics! I'm impressed how many solving techniques you have implemented. And interesting results.

If I may request: When you find time for it, maybe you could run a similar statistics on a few publicly available lists? In addition to the top1465, here are a few suggestions:

1. Gsf's catalog of 651 puzzles from hard threads.
Reasons: Contains many of those that made it to ravel's hardest list, over a long period of time (except a few gaps, for instance the period dml delivered his contributions). The 99.98% is expected to fall drastically, but it would be interesting to see if any of the newer techniques are helpful in cracking previously unsolvable puzzles.
2. The Effortless Extremes.
To see the correlation between your 'hardest needed' compared to the listed 'extreme technique'.
3. This list of 10117 fully symmetric 20s.
Rather biased with respect to clues pattern (only 14 different). Does this imply clustering of specific solution techniques?
4. Ruud's top50000.
Again, the potential of 'new' techniques, since puzzles solvable with traditional methods obviously are filtered out.

I would expect the five mentioned lists to produce rather different statistics ....

[gsf]

1. Gsf's catalog of 651 puzzles from hard threads.
Reasons: Contains many of those that made it to ravel's hardest list, over a long period of time (except a few gaps, for instance the period dml delivered his contributions). The 99.98% is expected to fall drastically, but it would be interesting to see if any of the newer techniques are helpful in cracking previously unsolvable puzzles.

I wouldn't mind filling in the gaps -- do you have a time range for dml's puzzles
I'll also add in the "unsolvables" from top1465 and top50000

[ravel]

I wouldn't mind filling in the gaps -- do you have a time range for dml's puzzles

This is a collection i have from the hardest thread. At least some of them are not in your list:

000001020300040500000600007002000001080090030400000800500002000090030400006700000 Ocean's New Year's present for RW
003000009400000020080600100200004000090800007005030000000900800000005030070010006 dml 1/07
100050080000009003000200400004000900030000007800600050002800060500010000070004000 dml20
003400080000009200000060001007010000060002000500800040010000900800000030004500007 dml 3/07
100050000006009000080200004040030008007000060900000100030800002000004050000010700 dml11
003900000040070001600002000800000002070050030009000400200001008000040050000600900 dml12
000001020300040500000600007002000006050030080400000900900002000080050400001700000 Ocean's Christmas present for gsf
100300000020090400005007000800000100040000020007060003000400800000020090006005007 dml161
100007000020080000004300500005400001080000020900000300000005007000020060003100900 dml48
100007000040050020006800000005090003020000040700000100000003005090040060000100800 dml9
900004000050080070001200000002600009030000040700000500000009002080050030000700600 dml8
100007000020030500004900000008006001090000020700000300000001008030050060000400700 dml45
003400000050009200700060000200000700090000010008005004000300008010002900000070060 dml 5/07
003200000040090000600008010200000003010006040007000500000001002090040060000500700 dml15
000001020300040500000600001001000007050030040800000900400002000090050800006700000 Ocean's New Year's present for ravel #1
800003000070060090004500000002000004030001070500000800000009001060070030000200500 dml4
020400000006080100700003000000060300000200005090007040300000800001000090040500002 dml50
002600000030080000500009100006000002080000030700001400000004005010020080000700900 dml16
001002000030040050600700800008000007010000040900000500004001008020030010000600900 Ocean #6/gold list
900004000080020030005700000001000004060080070300000500000005001070030090000600200 dml6
400009000030010020006700000001000004050200070800000600000004008070030010000500900 dml1
020000600400080007009000010005006000300040900010200000000700004000001050800090300 dml31
003400000050009000700020006200070010000300008000005400001060007090000300800000020 dml 14/07
002900000030070000500004100008000002090000030600500400000003008000060070100200500 dml52
002400006030010000500008000007000002010000030900600400000007001000090080400200500 dml19
000050700400009020000100006010600000008020000900003050070000800500040030002000001 dml 8/07
000001020300040500000600007001000006040080090500000300800002000050090400006700000 Ocean's New Year's present for ravel #2
100006080050700000009030000007000050030000002600001400000040900800005060000200007 dml25
000400080000009200700060005001030000090002000600800040030000006800500070002000100 dml 9/07
003000600400009070080000001200070040000600800000003005060010000007500000900004020 dml 11/07
003007000400100200080060000200000900060008050007000003000030004000005060900200100 dml 12/07
003400000050009000700020010040300900000070020000005006002000008600000070090001500 dml 15/07
100009000020060000003500400005000001060080020700000300080001009000020060000400700 dml53
000007080006100200000030004090040000300008070001600000002000090800005300040000006 dml 4/07
800003000070060090004500000005000004090002070100000800000009003020010060000700500 dml2
100000009006000070080300400200010060000004005000700800030800000007060010900005000 dml 19/07
020000600400000007009030010000005004060010020000800300005700000010020900800004000 dml 6/07
003000009400000070080006500005001800060200000900070000000090040000800003010005200 dml 10/07


[Added:] If you want them all (also the ones i have filtered out because my own rating was low): dml posted them between Sun Nov 26 2006 and Sun Jan 14, 2007. But there were a lot of equivalents (including one equivalent to a puzzle Ocean has posted before) and many dont have a "name".

[gsf]

[Added:] If you want them all (also the ones i have filtered out because my own rating was low): dml posted them between Sun Nov 26 2006 and Sun Jan 14, 2007. But there were a lot of equivalents (including one equivalent to a puzzle Ocean has posted before) and many dont have a "name".

why don't we start from a combination of your list and mine
with an implicit assumption of no duplicates
we can synthesize omitted names using submitter+date+sequence-for-date

[Mike Barker]

I'm not sure of how many of the hardest I can solve. My experience is that my solver starts to break down around SER 9.0 or 9.1 so saying my solver solved 99.98% should be equivalent to saying that the probability of a puzzle with SER>9.0 is ~.02%. Has anyone ever gone through and looked at a probability distribution of puzzle difficultly for randomly generated puzzles?

[Ocean]

My experience is that my solver starts to break down around SER 9.0 or 9.1 so saying my solver solved 99.98% should be equivalent to saying that the probability of a puzzle with SER>9.0 is ~.02%.

Seems you can solve most of what Explainer calls "Forcing Chains", while not the so-called "Dynamic Forcing Chains" - except when alternative techniques are available; and such cases are interesting.

Has anyone ever gone through and looked at a probability distribution of puzzle difficultly for randomly generated puzzles?

Isn't this just what you did when posting your statistics above?

The hardest puzzles (say, SER>10.0, and also SER>9.0) are so rare that generators should be tuned specifically to look for certain properties, in order to find such puzzles. To me it does not make much sense to talk about probability distribution for extreme cases. It's like looking for big mountains: If we go to the Alps, the Andes or Himalaya, there are plenty of chances to find some. If we randomly pick a spot on the globe, the probability is much less.

Anyway, for the normal cases... To illustrate how my logical solver is grouping puzzles from the various files/collections, and also some pseudorandom (symmetrical) puzzles, here is my statistics (four different groups are defined):

Code: Select all

+---------------+-------+-------+-------+-------+
| File          |Singles|Tups/XW|xychain|  more |
+---------------+-------+-------+-------+-------+
| g17           |  46 % |  40 % |   9 % |   5 % |
| gsfhard       |   2 % |   2 % |   1 % |  95 % |
| ruud_top50000 |   0 % |  0.2% |  14 % |  86 % |
| fullsym_20s   |  38 % |     (36 %)    |  26 % |
+---------------+-------+-------+-------+-------+
| FF (Type I) * |  50 % |  21 % |  13 % |  16 % |
| LL (Type II)  |  58 % |  16 % |  12 % |  14 % |
| PP (Type III) |  61 % |  19 % |  12 % |   8 % |
| XX (Type IV)  |  51 % |  17 % |  14 % |  18 % |
| RR (Type V)   |  60 % |  15 % |  13 % |  12 % |
| HH (Type VI)  |  60 % |  19 % |  12 % |   9 % |
| DD (Type VII) |  53 % |  17 % |  14 % |  16 % |
+---------------+-------+-------+-------+-------+

(*)Random generated symmetrical puzzles, ordered by symmetry type (labeled I to VII). Treshold set to 24 clues or less. Sample sizes 10000. Repeatability roughly within +/- 1%.

There seems to be a significant difference between the set of minimal 17s and the random symmetrical -24s. The 20s are also harder than the 24s. The gsfhard and ruud_top50000 sets are clearly biased, because the easiest puzzles are deliberately taken away.
#
An observation: Puzzles with diagonal symmetry (Type I, IV and VII) seem to be harder than other symmetries, on the average.

[Mike Barker]

I was curious about how Sudoku Explainer rates a set of randomly generated puzzles (using suexg). The following list the number of puzzles with a given rating out of 100000. The results are not that different from my solver. One notatable exception is the number of X-wings. The difference here, I believe, is that my solver uses both basic and finned X-wings. The reduced number of X-wings with Explainer also reduces the number of XY-wing rated puzzles. My rating also has locked candidates higher, because my solver combines pointing, claiming, direct point, direct claiming, and some naked and hidden pairs as one technique. The message remains basically the same - singles, pairs, locked candidates, short nice loops/AICs, and Type 1 URs (UR+1) are key solving techniques. To this list I would add X-wings and XY-wings which are actually short nice loops or, in the case of finned X-wings, grouped nice loops.

The other thing I was interested in was the number of extremely tough puzzles (>9.0) which are randomly generated by suexg. Based on these results the number is slightly more than 0.1%. Also the maximum rating in this set of 100000 is 9.2 with a .001% probability. Makes you appreciate the effort people go through to create the hardest puzzles!

Results are sorted two ways. The first list sorts the results by the number of times a puzzle is solved with each rating. The second list sorts directly by the rating. Note that Explainer combines multiple techniques into one rating. For this list I haven't separated ratings by techniques. Also I don't have a precise definition for what I called "steps". Explainer uses a combination of the number of steps in a solution and the number of chains minus two to come up with the "step" count. Note, CRCD stands for Cell/Region/Contradiction/Double forcing chain solving techniques

Code: Select all

SE Rating  Solved   Description
1.50       25341    Hidden Single in line
2.00       21227    Direct Hidden Pair
7.10       7761     Forcing Chain or Bidirectional Cycle (5-6 steps)
7.20       7091     Forcing Chain or Bidirectional Cycle (7-8 steps)
2.60       6211     Pointing
6.60       5777     Forcing X-chain or Turbot Fish or Bidirectional Y-Cycle (5-6 steps)
4.20       4235     XY-Wing
2.30       3583     Naked Single
4.50       2036     UR Types 1 or 2 or 4 or 3 w/ hidden pair
1.20       1928     Hidden Single in box
7.30       1840     Forcing Chain or Bidirectional Cycle (9-12 steps)
1.70       1595     Direct Pointing
2.80       1499     Claiming
3.00       1252     Naked Pair
8.30       1140     Multiple (9-12 steps) Cell/Region Forcing Chains
2.50       1074     Direct Hidden Triplet
3.40       857      Hidden Pair
5.60       832      BUG Type 1
8.40       650      Multiple (13-16 steps) Cell/Region Forcing Chains
4.40       571      XYZ-Wing
6.69       529      Forcing X-Chain (7-8 steps)
6.80       396      Forcing X-Chain or Bidirectional Y-cycle (9-12 steps)
3.20       211      X-Wing
6.70       193      Bidirectional Y-cycle (7-8 steps)
8.50       191      Multiple (17-24 steps) Cell/Region Forcing Chains
4.60       188      UR Type 3 w/ naked pair or hidden triplet or UL Types 1 or 2 or 4 or 3 w/ hidden pair (6 cells)
3.60       180      Naked Triplet
6.90       153      Forcing X-Chain or Bidirectional Y-cycle (13-16 steps)
7.00       152      Forcing Chain or Bidirectional Cycle (1-4 steps) or Bidirectional Y-cycle (17-24 steps)
8.20       150      Multiple (7-8 steps) Region Forcing Chains
7.60       148      Forcing Chain (25-36 steps) or Nishio Forcing Chain (5-6 steps)
7.80       140      Nishio Forcing Chain (9-12 steps)
8.90       122      Dynamic (13-16 steps) CRCD Forcing Chains
5.70       108      BUG Type 2 or 4
7.70       91       Nishio Forcing Chain (7-8 steps)
9.00       91       Dynamic (17-24 steps) CRCD Forcing Chains
7.40       86       Forcing Chain (13-16 steps)
4.00       66       Hidden Triplet
8.80       53       Dynamic (9-12 steps) CRCD Forcing Chains
7.50       51       Forcing Chain (17-24 steps) or Aligned Triplet Exclusion
6.20       41       Aligned Pair Exclusion
6.50       38       Bidirectional X-Cycle or Bidirectional Y-Cycle (1-4 steps)
7.90       22       Nishio Forcing Chain (13-16 steps)
3.80       22       Swordfish
8.60       19       Multiple (25-36 steps) or Dynamic (5-6 steps) Cell/Region Forcing Chains
9.10       16       Dynamic (25-36 steps) CRCD Forcing Chains
4.70       12       UR Type 3 w/ naked triplet or hidden quad or UL Types 1 or 2 or 4 or 3 w/ hidden pair (8 cells)
5.00       9        Naked Quad or UL 1 or 2 or 4 (>=10 cells)
8.00       7        Nishio Forcing Chain (17-24 steps)
5.80       4        BUG Type 3 w/ naked pair
5.90       3        BUG Type 3 w/ naked triplet
4.69       2        UL Type 3 w/ a naked pair or hidden triplet (6 cells)
5.40       2        Hidden Quad
8.70       1        Dynamic (7-8 steps) Cell/Region Forcing Chains
9.20       1        Dynamic (37-48 steps) CRCD Forcing Chains
6.00       1        BUG Type 3 w/ naked quad
5.20       1        Jellyfish

Code: Select all

SE Rating  Solved   Description
1.20       1928     Hidden Single in box
1.50       25341    Hidden Single in line
1.70       1595     Direct Pointing
2.00       21227    Direct Hidden Pair
2.30       3583     Naked Single
2.50       1074     Direct Hidden Triplet
2.60       6211     Pointing
2.80       1499     Claiming
3.00       1252     Naked Pair
3.20       211      X-Wing
3.40       857      Hidden Pair
3.60       180      Naked Triplet
3.80       22       Swordfish
4.00       66       Hidden Triplet
4.20       4235     XY-Wing
4.40       571      XYZ-Wing
4.50       2036     UR Types 1 or 2 or 4 or 3 w/ hidden pair
4.60       188      UR Type 3 w/ naked pair or hidden triplet or UL Types 1 or 2 or 4 or 3 w/ hidden pair (6 cells)
4.69       2        UL Type 3 w/ a naked pair or hidden triplet (6 cells)
4.70       12       UR Type 3 w/ naked triplet or hidden quad or UL Types 1 or 2 or 4 or 3 w/ hidden pair (8 cells)
5.00       9        Naked Quad or UL 1 or 2 or 4 (>=10 cells)
5.20       1        Jellyfish
5.40       2        Hidden Quad
5.60       832      BUG Type 1
5.70       108      BUG Type 2 or 4
5.80       4        BUG Type 3 w/ naked pair
5.90       3        BUG Type 3 w/ naked triplet
6.00       1        BUG Type 3 w/ naked quad
6.20       41       Aligned Pair Exclusion
6.50       38       Bidirectional X-Cycle or Bidirectional Y-Cycle (1-4 steps)
6.60       5777     Forcing X-chain or Turbot Fish or Bidirectional Y-Cycle (5-6 steps)
6.69       529      Forcing X-Chain (7-8 steps)
6.70       193      Bidirectional Y-cycle (7-8 steps)
6.80       396      Forcing X-Chain or Bidirectional Y-cycle (9-12 steps)
6.90       153      Forcing X-Chain or Bidirectional Y-cycle (13-16 steps)
7.00       152      Forcing Chain or Bidirectional Cycle (1-4 steps) or Bidirectional Y-cycle (17-24 steps)
7.10       7761     Forcing Chain or Bidirectional Cycle (5-6 steps)
7.20       7091     Forcing Chain or Bidirectional Cycle (7-8 steps)
7.30       1840     Forcing Chain or Bidirectional Cycle (9-12 steps)
7.40       86       Forcing Chain (13-16 steps)
7.50       51       Forcing Chain (17-24 steps) or Aligned Triplet Exclusion
7.60       148      Forcing Chain (25-36 steps) or Nishio Forcing Chain (5-6 steps)
7.70       91       Nishio Forcing Chain (7-8 steps)
7.80       140      Nishio Forcing Chain (9-12 steps)
7.90       22       Nishio Forcing Chain (13-16 steps)
8.00       7        Nishio Forcing Chain (17-24 steps)
8.20       150      Multiple (7-8 steps) Region Forcing Chains
8.30       1140     Multiple (9-12 steps) Cell/Region Forcing Chains
8.40       650      Multiple (13-16 steps) Cell/Region Forcing Chains
8.50       191      Multiple (17-24 steps) Cell/Region Forcing Chains
8.60       19       Multiple (25-36 steps) or Dynamic (5-6 steps) Cell/Region Forcing Chains
8.70       1        Dynamic (7-8 steps) Cell/Region Forcing Chains
8.80       53       Dynamic (9-12 steps) CRCD Forcing Chains
8.90       122      Dynamic (13-16 steps) CRCD Forcing Chains
9.00       91       Dynamic (17-24 steps) CRCD Forcing Chains
9.10       16       Dynamic (25-36 steps) CRCD Forcing Chains
9.20       1        Dynamic (37-48 steps) CRCD Forcing Chains

[Mike Barker]

Something else I've been wondering is the added benifit of using Denis' nrct chains over simple and grouped nice loops/AICs. To this end I implemented nrct-chains in my solver and set the hierarchy so that an n-element nrct-chain was evaluated following an (2n-1)-element xy-chain (bivalues only), n-element simple advanced coloring (bilocals only), n-element nice loop (bilocals and bivalues only), n-element grouped advanced coloring (bilocals and grouped strong links only), and n-element strong grouped nice loops (bivalues, bilocals, and grouped strong links only) with different fish and UR's thrown into the mix as well. This analysis only looks at nrct-chains which like nice loops begin with a bilocal unit or bivalue cell.

The first observation was that my solver found fixed length nrct-chains much quicker than the same length nice loop. This probably doesn't say much about my nice loop finder, but does address a question raised eariler about nrc-chains, that is, that there are just too many. I think the issue previously was that the algorithm searched for all possible nrc-chains. By limiting to a fixed length the number of occurances is much smaller and the algorithm is much quicker. One thing I haven't investigated is when there are too many nrct chains.

As far as effectivenss, even located after nice loops, etc, my solver still found a reasonable number of nrct-chains. Here's a sample 3-element (in this case three strong link) nrct chain showing how the extra t-link turns row 7 into an effective bilocal. In this case and the several others it took a one element longer nice loop to solve the puzzle. I don't know how general this result is.

Code: Select all

4564: 3-element NRCT chain: r7c3 =9= r9c1 -9- r9c7 =9= r5c7 -9- (r6c1)r6c8 =9= r6c5 ~9~  => r7c5<>9
+----------------+--------------+----------------+
|    4  16  136  |   2  136  9  |  5     7    8  |
|  138   5    2  |  18   13  7  |  4     6    9  |
|    7   9   68  |  48   46  5  |  1    23   23  |
+----------------+--------------+----------------+
|  169   3  569  | 159    2  8  |  7   459  146  |
| 1289  16  568  | 159    7  4  | 39* 2359  136  |
|  129x  7    4  |   3  159* 6  |  8   259*  12  |
+----------------+--------------+----------------+
|    5   2   39* |   7  4-9  1  |  6     8   34  |
|   16   8   16  | 459  459  3  |  2    49    7  |
|   39*  4    7  |   6    8  2  | 39*    1    5  |
+----------------+--------------+----------------+

Here's another example with a four element nrct chain where t-links create a bivalue from a multi-valued cell.

Code: Select all

7893: 4-element NRCT chain: r6c3 =5= r3c3 -5- r3c9 -7- (5)r3c7 -3- r6c7 ~7~ r6c3 => r6c3<>7
+---------------------+-----------------+---------------+
|  346    456      1  | 3679    37  47  |   8  359   2  |
|    7     24      8  |   39    12   5  |   6  139  34  |
| 2346      9    456* |  368    12  48  |35x7*  14  57* |
+---------------------+-----------------+---------------+
|   12     12      9  |   38  3578  78  |   4    6  57  |
|   68   5678      3  |    4   567   1  | 257  258   9  |
|  468  45678  456-7* |    2   567   9  |  37*  38   1  |
+---------------------+-----------------+---------------+
| 1468      3    467  |  578     9   2  |  15   45  68  |
|    9    168     26  |   58     4   3  | 125    7  68  |
|    5    478    247  |    1    78   6  |   9  234  34  |
+---------------------+-----------------+---------------+

As the length of the chain gets longer the effectiveness of nrct chains increases. For three elements only 3 nrct chains solve a puzzle while 622 simple and grouped advanced coloring and simple and strong grouped nice loops solved puzzles. At four elements the values are 64 vs. 512; at five, 58 vs. 104; at six, 39 vs. 13, etc. My algorithm only looks for nrct-chains using bilocals and bivalues which either exist are the start of the elimination or are created by t-links. I imagine use of grouped strong links in nrct chains would increase the number of puzzles solved.

As another comparison, the longest nice loop which solved a puzzle was 7 elements, while one puzzle was solved with a 12 element nrct chain. I'm not sure who would look for a 12 element nrct chain, but it does indicate additional capability. In addition, my solver solved one more puzzle (9998 out of 10000) than before without nrct chains. Also only 4 puzzles required "kraken" techniques vs 44 for a previous evaluation. This probably represents an overall simplification given the conceptual simplicity of nrct chains.

My conclusion from all of this is that nrct chains are a useful extension of nice loops where the approach would be to create links where none would otherwise exist near the end of moderate length nice loops.

Here's a summary of the number of puzzles solved for each technqiue where the first number represents the order in my solving hierarchy and the second the number of puzzles solved. I used Denis' Sudogen0 data set for this analysis:

Code: Select all

  2 (4148):    L_HIDDEN1    'hidden single
  3 (1185):    L_LOCKED1    'include line/box and box/box eliminations
 10 ( 759):    L_XWING      'X-wing (basic and finned)
 11 ( 478):    L_XY         'XY-wing (3-node XY-chain)
  4 ( 360):    L_NAKED2     'naked pair
 35 ( 337):    L_XYCHAIN4   '4-node XY-chain
 43 ( 330):    L_NICE3      '3-element nice loop (strong links/bivalue cells)
 41 ( 231):    L_XYCHAIN5   '5-node XY-chain
 57 ( 224):    L_NICE4      '4-element nice loop (strong links/bivalue cells)
 42 ( 203):    L_ADVANCED3  '3-element advanced coloring
 56 ( 201):    L_ADVANCED4  '4-element advanced coloring
  5 ( 184):    L_NAKED3     'naked triple
 14 ( 129):    L_UNIQUE1    'UR+1 (type 1)
  1 (  99):    L_NAKED1     'naked single
 45 (  74):    L_STRONG3G   '3-element strong nice loop (GSL/BV)
 49 (  72):    L_XYCHAIN6   '6-node XY-chain
 33 (  71):    L_XYZ        'generalized XYZ-wing (2-3 candidate pilots)
 18 (  66):    L_UNIQUE4    'UR+2(X,D,B)/1SL, UR+2C/2SL (types 4/4B,...)
 60 (  64):    L_NRCT4      '4-element nrct-chain (strong links/bivalue cells)
 74 (  58):    L_NRCT5      '5-element nrct-chain (strong links/bivalue cells)
  6 (  49):    L_HIDDEN2    'hidden pair
 71 (  44):    L_NICE5      '5-element nice loop (strong links/bivalue cells)
 13 (  40):    L_BUG1       'BUG+1 eliminations
 70 (  39):    L_ADVANCED5  '5-element advanced coloring
 84 (  39):    L_NRCT6      '6-element nrct-chain (strong links/bivalue cells)
 12 (  38):    L_EMPTY      'empty rectangle
 36 (  38):    L_SWORDFISH  'swordfish (basic and finned)
 59 (  36):    L_STRONG4G   '4-element strong nice loop (GSL/BV)
 55 (  29):    L_XYCHAIN7   '7-node XY-chain
 58 (  29):    L_ADVANCED4G '4-element grouped advanced coloring
 91 (  29):    L_NRCT7      '7-element nrct-chain (strong links/bivalue cells)
 40 (  27):    L_XYRING5    '5-node XY-ring
 17 (  23):    L_UNIQUE3    'UR+2X (types 3/3B)
 38 (  23):    L_STRONG3    'three strong links (basic and grouped)
 15 (  19):    L_UNIQUE2    'UR+2x (types 2/2B)
 47 (  19):    L_WXYZ       'generalized WXYZ-wing (2-4 candidate pilots)
 23 (  17):    L_BUGLITE2   'basic 2-line BUG-lite
 44 (  17):    L_ADVANCED3G '3-element grouped advanced coloring
 48 (  17):    L_XYRING6    '6-node XY-ring
 26 (  16):    L_STRONG2    'two strong links (basic and grouped)
 21 (  14):    L_BUG2       'BUG+n(x,X) eliminations
 24 (  13):    L_BUGLITE3   'basic 3-line BUG-lite
 94 (  12):    L_NRCT8      '8-element nrct-chain (strong links/bivalue cells)
 34 (  11):    L_XYRING4    '4-node XY-ring
 72 (  11):    L_ADVANCED5G '5-element grouped advanced coloring
 73 (  10):    L_STRONG5G   '5-element strong nice loop (GSL/BV)
 96 (   8):    L_NRCT9      '9-element nrct-chain (strong links/bivalue cells)
  7 (   7):    L_HIDDEN3    'hidden triple
 81 (   6):    L_NICE6      '6-element nice loop (strong links/bivalue cells)
 97 (   6):    L_NRCT10     '10-element nrct-chain (strong links/bivalue cells)
 37 (   4):    L_FRANK3     'Franken Swordfish
 80 (   4):    L_ADVANCED6  '6-element advanced coloring
 46 (   3):    L_NRCT3      '3-element nrct-chain (strong links/bivalue cells)
 54 (   3):    L_XYRING7    '7-node XY-ring
 61 (   3):    L_VWXYZ      'generalized VWXYZ-wing (2-5 candidate pilots)
 69 (   2):    L_XYCHAIN9   '9-node XY-chain
 83 (   2):    L_STRONG6G   '6-element strong nice loop (GSL/BV)
 88 (   2):    L_NICE7      '7-element nice loop (strong links/bivalue cells)
116 (   2):    L_NICE3G     '3-element grouped nice loop (GSL/ALS)
164 (   2):    L_SUM2CELL3  '3-valued/2-element kraken Blossom
185 (   2):    L_SUM2ALS    '2-element kraken ALS
  8 (   1):    L_NAKED4     'naked quadruple
 19 (   1):    L_UNIQUE6    'UR+2r(x,d)
 20 (   1):    L_UNIQUE9    'UR+2k(x,d)
 22 (   1):    L_BUG3       'strong link BUG eliminations
 63 (   1):    L_XYRING8    '8-node XY-ring
 64 (   1):    L_XYCHAIN8   '8-node XY-chain
 82 (   1):    L_ADVANCED6G '6-element grouped advanced coloring
 98 (   1):    L_NRCT11     '11-element nrct-chain (strong links/bivalue cells)
 99 (   1):    L_NRCT12     '12-element nrct-chain (strong links/bivalue cells)
110 (   1):    L_ALS1xy     'B=1 cell ALS xy-rule

[denis_berthier]

Great work, Mike.
Could you easily add nrczt chains to your program? It'd be great to have a second solver with such a capability.

From the computations I reported in this forum and in the second edition of HLS, they allow solving many more puzzles than nrct alone (they solve all the puzzles in Sudogen0, without Uniqueness rules, ALS or grouped chains).
In the "supersymmetric chains" thread, I've just posted my recent results for the first 30 puzzles in Ruud's top 10,000: all are now solved with nrczt chains (or lassos).

Some people don't like the z-extension, but:
- from a practical POV, it seems to me it is intuitively justified when one has some reason to focus on a candidate (in order to eliminate it); in this case, the z extension should be no harder to use than the t-extension;
- from a theoretical POV, given a candidate, nrczt chains are the most general first order chain pattern that can allow its elimination.

[Mike Barker]

Here are a few more results of Sudoku Explainer ratings. The first set is the results from dukuso's Top 1465, the second from Ruud's Top 10000. These are both biased sets selected for being "hard". The first as I recall was constructed to challenge backtracking solvers; the second, from puzzles requiring Tabling is Ruud's solver. Listed are the SE ratings, the number of occurances in the set, the first puzzle with the rating, and my interpretation of the rating. I don't know if I'll ever get through the Top10000 with my solver, its just not quick enough.

Code: Select all

Top1465
SE Rating  Solved  Puzzle  Description
2.00       5       471     Direct Hidden Pair
2.30       2       1014    Naked Single
2.50       1       1403    Direct Hidden Triplet
2.60       118     58      Pointing
2.80       28      122     Claiming
3.00       33      15      Naked Pair
3.40       99      4       Hidden Pair
3.60       8       14      Naked Triplet
4.00       16      11      Hidden Triplet
4.20       10      158     XY-Wing
4.40       3       701     XYZ-Wing
4.50       22      64      UR Types 1 or 2 or 4 or 3 w/ hidden pair
5.60       1       603     BUG Type 1
6.60       68      81      Forcing X-chain or Turbot Fish or Bidirectional Y-Cycle (5-6 nodes)
6.69       6       94      Forcing X-Chain (7-8 nodes)
6.80       1       226     Forcing X-Chain or Bidirectional Y-cycle (9-12 nodes)
6.90       1       755     Forcing X-Chain or Bidirectional Y-cycle (13-16 nodes)
7.10       88      16      Forcing Chain or Bidirectional Cycle (5-6 nodes)
7.20       93      41      Forcing Chain or Bidirectional Cycle (7-8 nodes)
7.30       41      134     Forcing Chain or Bidirectional Cycle (9-12 nodes)
7.40       2       767     Forcing Chain (13-16 nodes)
7.50       5       114     Forcing Chain (17-24 nodes) or Aligned Triplet Exclusion
7.60       23      309     Forcing Chain (25-36 nodes) or Nishio Forcing Chain (5-6 nodes)
7.70       12      266     Nishio Forcing Chain (7-8 nodes)
7.80       28      156     Nishio Forcing Chain (9-12 nodes)
7.90       10      250     Nishio Forcing Chain (13-16 nodes)
8.00       1       1380    Nishio Forcing Chain (17-24 nodes)
8.20       9       481     Multiple (7-8 nodes) Region Forcing Chains
8.30       117     12      Multiple (9-12 nodes) Cell/Region Forcing Chains
8.40       91      42      Multiple (13-16 nodes) Cell/Region Forcing Chains
8.50       53      56      Multiple (17-24 nodes) Cell/Region Forcing Chains
8.60       1       1241    Multiple (25-36 nodes) or Dynamic (5-6 nodes) Cell/Region Forcing Chains
8.70       4       808     Dynamic (7-8 nodes) Cell/Region Forcing Chains
8.80       41      35      Dynamic (9-12 nodes) CRCD Forcing Chains
8.90       93      38      Dynamic (13-16 nodes) CRCD Forcing Chains
9.00       197     1       Dynamic (17-24 nodes) CRCD Forcing Chains
9.10       76      29      Dynamic (25-36 nodes) CRCD Forcing Chains
9.20       37      7       Dynamic (37-48 nodes) CRCD Forcing Chains
9.30       14      89      Dynamic (49-72 nodes) or Dynamic + (9-12 nodes) CRCD Forcing Chains
9.40       4       113     Dynamic (73-96 nodes) or Dynamic + (13-16 nodes) CRCD Forcing Chains
9.50       1       2       Dynamic + (17-24 nodes) CRCD Forcing Chains
9.60       1       3       Dynamic + (25-36 nodes) CRCD Forcing Chains
9.80       1       77      Dynamic + (49-72 nodes) CRCD Forcing Chains

Code: Select all

Top10000
SE Rating  Solved  Puzzle  Description
4.60       2       5989    UR Type 3 w/ naked pair or hidden triplet or UL Types 1 or 2 or 4 or 3 w/ hidden pair (6 cells)
7.10       6       1393    Forcing Chain or Bidirectional Cycle (5-6 nodes)
7.20       17      3097    Forcing Chain or Bidirectional Cycle (7-8 nodes)
7.30       69      766     Forcing Chain or Bidirectional Cycle (9-12 nodes)
7.40       46      345     Forcing Chain (13-16 nodes)
7.50       26      516     Forcing Chain (17-24 nodes) or Aligned Triplet Exclusion
7.60       10      566     Forcing Chain (25-36 nodes) or Nishio Forcing Chain (5-6 nodes)
7.70       5       3810    Nishio Forcing Chain (7-8 nodes)
7.80       8       186     Nishio Forcing Chain (9-12 nodes)
7.90       2       5343    Nishio Forcing Chain (13-16 nodes)
8.00       1       9439    Nishio Forcing Chain (17-24 nodes)
8.20       71      361     Multiple (7-8 nodes) Region Forcing Chains
8.30       3142    11      Multiple (9-12 nodes) Cell/Region Forcing Chains
8.40       3340    9       Multiple (13-16 nodes) Cell/Region Forcing Chains
8.50       1270    5       Multiple (17-24 nodes) Cell/Region Forcing Chains
8.60       102     45      Multiple (25-36 nodes) or Dynamic (5-6 nodes) Cell/Region Forcing Chains
8.70       28      136     Dynamic (7-8 nodes) Cell/Region Forcing Chains
8.80       244     28      Dynamic (9-12 nodes) CRCD Forcing Chains
8.90       733     7       Dynamic (13-16 nodes) CRCD Forcing Chains
9.00       766     2       Dynamic (17-24 nodes) CRCD Forcing Chains
9.10       92      19      Dynamic (25-36 nodes) CRCD Forcing Chains
9.20       18      1       Dynamic (37-48 nodes) CRCD Forcing Chains
9.30       2       55      Dynamic (49-72 nodes) or Dynamic + (9-12 nodes) CRCD Forcing Chains

[champagne]

I have seen in this thread a list of dml hard puzzles. I made a quick check to see how they behave with my solver.
The first number is the time in milliseconds to count the number of solutions reflecting "structural" difficulty.
The second one is the processing time asking the solver to start at level 3.
This is normally the most representative of the difficulty to solve it in full tagging.
The last number is the processing time forcing level 4 at the start. This is the way to detect SK loop in "relatively" easy puzzles.
This set seems to have a relatively low "structural" complexity, however, "Ocean's New Year's present for ravel #2" is nearly as difficult to solve as Golden Nugget.
Several examples in that list of puzzles easily solved at level 3 and requesting a long way at level 4.
This comes mainly when the level 4 generates a lot of "couple tags" clearings that are not compulsory to crack the puzzle;

78 30s312 42s718 Ocean's New Year's present for RW
63 29s188 37s829 dml 1/07
46 28s187 27s296 dml20
32 21s500 34s891 dml 3/07
63 28s969 29s203 dml11
16 40s860 49s266 dml12
47 32s140 47s937 Ocean's Christmas present for gsf
32 17s406 35s0 dml161
32 16s250 44s391 dml48
31 14s641 31s625 dml9
31 16s94 45s16 dml8
31 37s15 37s46 dml45
32 26s844 33s438 dml 5/07
31 37s360 53s937 dml15
79 47s953 52s141 Ocean's New Year's present for ravel #1
47 53s718 60s609 dml4
47 21s516 33s63 dml50
47 26s891 47s62 dml16
32 13s625 23s969 Ocean #6/gold list
31 10s359 33s141 dml6
78 29s172 31s531 dml1
31 32s484 66s31 dml31
47 21s282 37s625 dml 14/07
47 15s437 44s891 dml52
62 24s984 38s156 dml19
47 17s688 21s797 dml 8/07
47 93s609 107s156 Ocean's New Year's present for ravel #2
47 11s735 20s797 dml25
31 16s562 22s375 dml 9/07
16 10s391 28s531 dml 11/07
16 13s78 27s563 dml 12/07
47 9s516 47s797 dml 15/07
31 14s781 45s719 dml53
31 23s922 33s140 dml 4/07
47 40s328 48s188 dml2
31 14s390 40s109 dml 19/07
63 23s579 24s141 dml 6/07
15 12s93 65s250 dml 10/07