The New Sudoku Players' Forum

[denis_berthier]

Here's a solution using only grouped nice loops. Obviously these ALS are not something I would find by hand, of course, finding a 28 element nrczt chain might be challenging as well.

Mike, thanks for your answer. Of course, using our solvers, we are pushing the limits of our techniques far beyond what human players can do with them. But doing so and discovering rare puzzles for which these techniques are not enough may lead us to a better understanding of which additional techniques can be interesting.
From your answer, I gather that introducing some form of grouped nrczt-chains (which can be considered as a very constrained form of net) may be an interesting next step.

Are you sure you need UR for this puzzle?

BTW, I've tried to solve the first 200 in top1465. There are:
- 5 that I (sorry, SudoRules) can't solve: 2, 3, 46, 89, 187;
- 3 that lead to a memory overflow: 77, 130,132

Can you solve any of them (in addition to the above #3) with the large set of rules you have implemented (preferably with no rule for uniqueness)?

[champagne]

Hi Denis

Realy difficult to have a fair discussion with you.

Code: Select all

champagne wrote:
Side question, where do you see any hidden T&E in the tagging process.

Denis wrote

I didn't read the details of your tagging algorithm ....As for T&E, it is so easy to simulate T&E with tags that the burden of proving that your algorithm doesn't is on you.
When a tagging algorithm is a clear implementation of a well defined resolution rule, things are clear, but your mixture is not.

1)You would be better of reading my procedure before accusing.
2)It's too easy to just say others are hidding T&E and then asking them to show they are not.
What I know from your process show that you are much closer to T&E that I am.
3)Tags as defined in my process are just showing strong and weak links.
The most likely, as you are working on oriented chains, tags were in your case marking T&E effects.
This could be one reason for your suspicion
4)I am ready to disclose the code I use. If you can read the C+ code, you'll see that T&E is not there.

Code: Select all

champagne wrote:
The main difference between what you are doing and tagging process is not in the taging itself, 
Denis wrote
It seems you don't understand the difference between a logic rule and an algorithm.

The way you express it, surely not, but I am still looking for somebody who caught the difference you see.

Code: Select all

champagne wrote:
but in the fact that I use groups, ALS AHS and AC2.
Denis wrote
You're forgetting nets. Fine for you if you like all this stuff.
My results show that this is very rarely needed.

Yes I forgot nets, the link with T chains.
If you don't want to use this stuff, forget really difficult puzzles. As you could see, Mike used ALS as well.

Code: Select all

Denis wrote
Anyway, as my chains can be used independently of any algorithm

,

Out of the recursive (I guess so) search for chains for sure.

Code: Select all

champagne wrote:
The tagging is just a performing way to extract AICs chains. 

Denis wrote
Which brings us back to the question you never answered : have you devised any single NEW rule?

Be fair play denis, introduction of AC2 has been a breakthrough in the solving approach for hardest puzzles.
Anyway, when you are solving all puzzles, there is no need for new rules.

Code: Select all

Denis wrote
I was just wondering if anybody has clearly defined resolution rules that can deal with the puzzle I mentioned. This question remains unanswered

.

I am afraid you will have to reject Mike proposal using the same stuff as me.
You have two answers to your question, can you explain now why they are not receivables.

[Mike Barker]

I can solve 2, 3, and 46 without Uniqueness Tests. I'm surprized you don't like UR's - they are a perfect example of a resolution rule, are one of the easiest techniques to see, and are very effective at solving moderately advanced puzzles. Also I think if you read Champangne's post, you will find that tagging has nothing to do with T&E. The tags are between strong inferences which are always valid. Unfortunately his nomenclature is even less standard than yours. I did try to translate one of his posts, but read his subsequent comments for corrections.

Anyway the solutions to 2 and 3 are nearly the same. The solution to 46 requires two ALS techniques:

Code: Select all

Hidden Pair in a box: r13c9 => r1c9=35,r3c9=35,r4c9<>35,r5c9<>35,r6c9<>35
Hidden Pair in a box: r56c8 => r5c8=35,r6c8=35
Hidden Pair in a box: r23c7 => r2c7=16,r3c7=16,r46c7<>1,r9c7<>6
Locked Column Line/Box: r78c6 => r456c6<>1
Locked Column Line/Box: r456c9 => r8c9<>1
Locked Column Line/Box: r45c9 => r9c9<>2
Locked Column Box/Box: r1346c56 => r9c5<>9,r89c6<>9
3-element Strong Nice Loop: r7c4 -5- r7c13 =5= r9c3 =9= r9c4 ~6~ r7c4 => r9c4<>6
4-element Grouped Advanced Colouring: r8c6 =1= r8c8 =7= r9c8 =2= r9c2 =3= r8c12 ~3~ r8c6 => r8c6<>3
A=1 cell ALS xz-mer: r9c7 -48- r789c4|r9c56 => r9c239<>4,r9c239<>8,r7c6<>5,r78c6<>6
+--------------------------+----------------------+---------------+
|     6       47      479  |    1   3459    3459  |  2   8    35  |
|   248        5        3  |   26    468    2468  |  1   9     7  |
|   289      128      189  |    7   3589   23589  |  6   4    35  |
+--------------------------+----------------------+---------------+
|  3457     1347     1457  |    8   1359   23579  | 49   6   124  |
|  3458        9    14568  | 2356   1356    2356  |  7  35  1248  |
|  3578    13678        2  |    4  13569   35679  | 89  35    18  |
+--------------------------+----------------------+---------------+
|  2458     2468     4568  |   56b     7  148-56  |  3  12     9  |
| 34789    34678    46789  |  369b     2   148-6  |  5  17   468  |
|     1  2367-48  5679-48  |  359b 34568b  34568b | 48* 27  6-48  |
+--------------------------+----------------------+---------------+
Hidden Pair in a box: r9c7|r8c9 => r8c9=48
Locked Column Line/Box: r78c4 => r25c4<>6
Naked Row Pair: r5c48 => r5c1<>35,r5c3<>5,r5c5<>35,r5c6<>35
Naked Column Pair: r25c1 => r3c1<>8,r4c1<>4,r6c1<>8,r7c1<>48,r8c1<>48
4-element Advanced Colouring: r8c8 =7= r9c8 =2= r7c8 -2- r7c1 =2= r3c1 =9= r8c1 ~7~ r8c8 => r8c1<>7
Locked Column Box/Box: r189c23 => r46c2<>7,r4c3<>7
4-element Strong Nice Loop: r3c3 =1= r3c2 =2= r3c1 -2- r7c1 -5- r46c1 =5= r4c3 ~1~ r3c3 => r4c3<>1
B=1 cell ALS xy-rule: r6c79 -9- r4c7 -4- r46c1|r4c23 => r6c2<>1,r4c9<>1
+--------------------+--------------------+---------------+
|   6     47    479  |   1   3459   3459  |  2   8    35  |
|  48      5      3  |   2    468    468  |  1   9     7  |
|  29    128    189  |   7   3589   3589  |  6   4    35  |
+--------------------+--------------------+---------------+
| 357c   134c    45c |   8   1359  23579  | 49*  6  24-1  |
|  48      9   1468  |  35     16     26  |  7  35  1248  |
| 357c 368-1      2  |   4  13569  35679  | 89b 35    18b |
+--------------------+--------------------+---------------+
|  25   2468   4568  |  56      7    148  |  3  12     9  |
|  39  34678  46789  | 369      2    148  |  5  17    48  |
|   1    237    579  | 359   3458   3458  | 48  27     6  |
+--------------------+--------------------+---------------+
4-element Grouped Advanced Colouring: r4c2 =1= r3c2 =2= r3c1 =9= r8c1 =3= r46c1 ~3~ r4c2 => r4c2<>3
3-element Strong Nice Loop: r5c4 -3- r4c56 =3= r4c1 =7= r4c6 ~5~ r5c4 => r4c6<>5
3-element Strong Nice Loop: r6c8 -3- r6c12 =3= r4c1 =7= r6c1 ~5~ r6c8 => r6c1<>5
Locked Row Line/Box: r4c13 => r4c5<>5
3-element Strong Nice Loop: r5c4 -3- r4c56 =3= r4c1 =5= r7c1 ~5~  => r7c4<>5
Locked Row Line/Box: r9c456 => r9c3<>5
Naked Row Pair: r8c14 => r8c2<>3,r8c3<>9
Row Finned X-Wing: r4c156|r8c14 => r5c4<>3
Naked Block Pair: r89c4 => r9c56<>3
3-element Advanced Colouring: r7c1 =2= r3c1 =9= r8c1 =3= r9c2 ~2~ r7c1 => r9c2<>2
8-node XY-chain: r7c1 -2- r3c1 -9- r8c1 -3- r9c2 -7- r1c2 -4- r2c1 -8- r5c1 -4- r4c3 -5-  => r4c1<>5,r7c3<>5
Column Finned X-Wing: r48c2|r49c7 => r8c9<>4
The Solution is completed

[denis_berthier]

I can solve 2, 3, and 46 without Uniqueness Tests.

Can you solve the other 5 ones if you use uniqueness?
I considered only the first 200 because I currently don't have much time for Sudoku. Are there any other puzzles in these first 200 (or in the whole collection) that you can't solve without uniqueness?

I'm surprized you don't like UR's - they are a perfect example of a resolution rule, are one of the easiest techniques to see, and are very effective at solving moderately advanced puzzles.

In order to avoid ambiguities:
- as I defined it, a resolution rule has to be a logical consequence of the Sudoku axioms, which do not include Uniqueness;
- a U-resolution rule has to be a logical consequence of the Sudoku axioms plus the axiom of Uniqueness; thus, URs, BUGs,…, are U-resolution rules but not resolution rules.
Once defined, the two types of rules can be used in exactly the same way but, intuitively, the two types of axioms are very different:
- Sudoku axioms are constraints on the solution, given the entries (whichever these are); they are constraints the player must satisfy;
- Uniqueness is a constraint on the entries; it is a constraint the puzzle creator must satisfy and the player may use if he trusts the puzzle creator; for the player, it is like an oracle on the puzzle.
Technically (when you write them as logical formulæ), they are also very different.

Using rules based on uniqueness may be considered as a matter of taste (as for many rules). But I wouldn't say I don't like them. It's rather that not using them provides the proof of uniqueness at the same time as the solution.

Also I think if you read Champangne's post, you will find that tagging has nothing to do with T&E. The tags are between strong inferences which are always valid. Unfortunately his nomenclature is even less standard than yours. I did try to translate one of his posts, but read his subsequent comments for corrections.

What I mean is that, when we use resolution rules, we know we are not using T&E, or, if we do, we know we are doing it. See my solution for EM.

With an algorithm, unless it is proven to be the implementation of clearly defined resolution rules and nothing more, we can't know a priori.
I'm not sure Champagne's algorithm is just the mere kind of tagging you're describing. He speaks of layers and merging of layers: that's where T&E may slip in.

Anyway, he keeps refusing to answer the only question that I'm really interested in: does he have any single NEW rule that any of us could apply without all the tagging stuff? If not, I already congratulated him for having an efficient implementation of known rules. If yes, where is it written?

[champagne]

Code: Select all

Denis wrote

Anyway, he keeps refusing to answer the only question that I'm really interested in: does he have any single NEW rule that any of us could apply without all the tagging stuff? If not, I already congratulated him for having an efficient implementation of known rules. If yes, where is it written?

Sorry Denis, this will be my last post on that stupid discussion.

None of the rules I apply are requesting tagging.

- AICs are well known from everybody working in that field,
- ALS/AHS are now familiar to many of us,
- The two rules I apply on Choices have been described long ago by others, not users of tagging,
- Nothing difficult in AC2s and no need of tagging to re use the tool.

Again tagging is just a way to simplify the search. The rules are inside these four topics.

I really don't catch your point. AICs ALS/AHS, AC2 are not tagging stuff, but stuff with some logic in it. You accept use of ALS from Mike, you denie the right to use it associated with tagging. This is very surprising.

[Mike Barker]

There are 11 that my solver couldn't solve with uniqueness (I don't know if there are more without - my experience is that uniqueness only adds a small number to the total solved.) In addition to 77 (9.8), 89 (9.3), 130 (9.3), 132 (9.2), and 187 (9.4), my solver couldn't solve 113 (9.4), 125 (9.3), 181 (9.3), 182 (9.4), 197 (9.1), 200 (9.1) where the number in parens is the Sudoku Explainer rating.

[denis_berthier]

Again tagging is just a way to simplify the search. The rules are inside these four topics.

OK: no new rule.

I really don't catch your point. AICs ALS/AHS, AC2 are not tagging stuff, but stuff with some logic in it. You accept use of ALS from Mike, you denie the right to use it associated with tagging. This is very surprising.

First, I'm not denying anybody the right to use the rules he wants and I'm not denyig that rules based on ALS are logic (although more naturally 2nd than 1st order - in the mathematical sense of these terms). I'm interested in Mike's results because they point to what might usefully be added to my set of rules. As there is much overlap between the possibilities offered by the t and z extensions and by ALSs, I certainly don't want to have both in my solver. But grouped nrczt-chains may be an interesting restricted form of using ALSs.
As for your tagging algorithm, you said it yourself: it is an (efficient) implementation of known rules. As I don't want to use tagging, what else can I gather from it? What exactly do you expect from me? Congratulations, again, for your efficient implementation? Then, sincere congratulations.

[denis_berthier]

There are 11 that my solver couldn't solve with uniqueness (I don't know if there are more without - my experience is that uniqueness only adds a small number to the total solved.) In addition to 77 (9.8), 89 (9.3), 130 (9.3), 132 (9.2), and 187 (9.4), my solver couldn't solve 113 (9.4), 125 (9.3), 181 (9.3), 182 (9.4), 197 (9.1), 200 (9.1) where the number in parens is the Sudoku Explainer rating.

Thanks, Mike. This confirms that the zt extension and the use of subsets are very close (though not equivalent). There are only few puzzles that can't be solved by both our solvers: 14 / 200 taken from top 1465 (which would be epsilon if taken from a list of random minimal puzzles. BTW, does there remain any puzzle in Sudogen0 that you can't solve?). 1/3 of these (77, 89, 130, 132, 187) can't be solved by any of the two solvers.
Moreover, the few puzzles that you can't solve but I can are among the most difficult for my rules (is the converse also true?):
# 113 needs 2 nrczt16 and 2 nrczt17 lassos (not for human players)
# 125 needs several nrczt15 and nrczt16 chains
# 181 needs "only" nrczt14
curiously, # 197 and # 200 are done with nrczt11

I had forgotten one that leads to a memory overflow (I checked again: nothing else forgotten): # 182, which activates several nrczt15,16,17,19 and 2 nrczt22 before memory explodes.

For both solvers, the break point is around ER 9.2-9.3. But I personally can't give this a clear meaning in terms of patterns.

It'd interesting to know exactly which rule unblocks the situation in a solver after the other is blocked. Unfortunately, SudoRules accepts only values as inputs. If I want to eliminate candidates to simulate the situation obtained by another solver, I have to write a rule that lists them all (as I did for Steve's rule in EM); this may be a long and tedious work. Does your solver accept candidates in its input?

[Mike Barker]

If you wanted to give me a PM I can paste it into my solver and see what technique is used for the next step (assuming there is one).

One thing I think we need to keep in mind is not only what rules can solve a puzzle, but the techniques used to uncover those rules in a puzzle. Tagging is a good technique for finding simple, grouped and multi-inference nice loops/AICs. I would think it could be extended to nrczt chains. The issue then is which is easier to find (grouped and multi-inference nice loops or nrczt-chains) by a hand solver which trumps the discussion of which approach can solve more of the hardest puzzles.

[denis_berthier]

If you wanted to give me a PM I can paste it into my solver and see what technique is used for the next step (assuming there is one).

For #3, after the eliminations below (SudoRules stops at this point):
hidden-single-in-a-block ==> r6c9 = 3
row r2 interaction-with-block b3 ==> r3c9 <> 8, r3c8 <> 8, r3c7 <> 8, r3c9 <> 7, r3c8 <> 7, r3c7 <> 7
block b6 interaction-with-column c7 ==> r9c7 <> 8, r7c7 <> 8, r2c7 <> 8
block b6 interaction-with-row r5 ==> r5c6 <> 5, r5c4 <> 5, r5c3 <> 5, r5c2 <> 5
hidden-pairs-in-a-row {n7 n8}r3{c4 c6} ==> r3c6 <> 9, r3c6 <> 4, r3c6 <> 3, r3c6 <> 2, r3c4 <> 9, r3c4 <> 4, r3c4 <> 3
block b2 interaction-with-column c5 ==> r9c5 <> 3, r7c5 <> 3, r4c5 <> 3
nrczt4-chain n9{r2c1 r4c1} - {n9 n5}r4c5 - n5{r2c5 r2c8} - n8{r2c8 r2c9} ==> r2c9 <> 9
nrczt4-chain n6{r1c2 r3c3} - n6{r5c3 r5c6} - n6{r6c5 r7c5} - n6{r7c7 r9c7} ==> r9c2 <> 6
nrczt6-lr-lasso n7{r9c3 r9c2} - n7{r9c9 r2c9} - n8{r2c9 r2c8} - n5{r2c8 r2c5} - {n5 n9}r4c5 - n9{r4c1 r4c3} ==> r5c3 <> 7
nrczt11-chain n6{r9c1 r6c1} - n6{r6c5 r9c5} - n1{r9c5 r7c5} - {n1 n8}r7c1 - n8{r4c1 r6c2} - n5{r6c2 r9c2} - n7{r9c2 r5c2} - n7{r9c2 r9c3} - n7{r9c9 r2c9} - n7{r2c8 r7c8} - {n7 n6}r7c7 ==> r7c3 <> 6
nrczt28-lr-lasso n5{r6c3 r4c3} - n5{r7c3 r7c5} - n1{r7c5 r9c5} - n6{r9c5 r6c5} - n2{r6c5 r5c6} - n4{r5c6 r5c4} - n4{r6c6 r6c7} - n8{r6c7 r4c7} - n1{r4c7 r4c1} - n9{r4c1 r2c1} - n9{r3c3 r5c3} - n6{r5c3 r5c2} - n6{r1c2 r1c8} - n6{r3c7 r3c3} - n4{r3c3 r2c3} - n4{r2c8 r3c8} - n4{r3c5 r1c5} - {n4 n9}r1c6 - {n9 n5}r1c4n5{r9c4 r9c2} - n7{r9c2 r6c2} - n8{r6c2 r8c2} - {n8 n6}r7c1 - n6{r7c7 r9c7} - n9{r9c7 r3c7} - n2{r3c7 r2c7} - {n2 n1}r3c9 - {n1 n2}r1c9 ==> r6c6 <> 5
GRID 3 NOT SOLVED. 62 VALUES MISSING.

here is the situation (is this what you call the PM?):

Code: Select all

+--------------------------+----------------------+---------------------+
|     7      126        8  |  459   2459   24569  |      3  1456  1259  |
|   249       23     2349  |    6  23459       1  |   2479  4578  2578  |
|     5     1236   123469  |   78  23459      78  |  12469   146   129  |
+--------------------------+----------------------+---------------------+
|   189        4     1579  | 3579     59    3579  |    178     2     6  |
|     3     1267     1269  |  479      8   24679  |    147  1457  1457  |
|   268    25678     2567  |    1   2456    2467  |   2478     9     3  |
+--------------------------+----------------------+---------------------+
|   168        9     1357  |     2   156    3568  |    167  13678     4 |
| 12468    12368    12346  |  3489     7   34689  |      5   1368  1289 |
| 12468   123578  1234567  | 34589 14569  345689  |  12679  13678 12789 |
+--------------------------+----------------------+---------------------+


One thing I think we need to keep in mind is not only what rules can solve a puzzle, but the techniques used to uncover those rules in a puzzle.

Sure.

Tagging is a good technique for finding simple, grouped and multi-inference nice loops/AICs. I would think it could be extended to nrczt chains. The issue then is which is easier to find (grouped and multi-inference nice loops or nrczt-chains) by a hand solver which trumps the discussion of which approach can solve more of the hardest puzzles.

I did define an nrczt-tagging algorithm. But I don't think it is necessary to use it. Additional candidates can be discarded on the fly. One thing to notice is that most of the time:
- we need only short chains (less than 7, 8 or 9 cells),
- there are few cells with additional candidates and in each of these there are few additional candidates,
- the t-links needed to justify the t-candidates link cells not very far apart in the chain,
- the composability property can be used to assemble larger nrczt-chains from smaller ones; this is not as good as reversibility, but it can be very useful; one can create a set of minimal nrczt chunks and combine them as one would do for AICs.

On the (French) Sudoku-factory.com forum, nrczt-chains (renamed t-chains) are used everyday (their notation is awful but they still use the # sign for the additional t-candidates). They do not use tagging for finding them.
They freely mix the t-extension and ALSs in the same chains.

[Mike Barker]

Denis, thanks for the link to the French site. A little translation ("/" -> "-", "-" -> "=", "#" -> "<>") and I could pretty much follow the eliminations. The solution I looked at used a dynamic forcing chain, but I could also see examples of t-chains. I especially like the clear indication of the extra links. It was also fun to see our own JPF with a French rendition of the Easter Monster (not that I understood much of what he wrote).

Here are a few eliminations at the point you posted the Pencil Marks minus the naked singles. Champagne may be able to provide some AC (basically AHS) examples as well.

Code: Select all

2-element Grouped Nice Loop: ALS:r4c456 -9- ALS:r5c4789 ~7~  => r5c6<>7
+-------------------------+-----------------------+----------------------+
|     7     126        8  |   459   2459    2459  |     3   1456   1259  |
|   249      23     2349  |     6  23459       1  |  2479   4578   2578  |
|     5    1236   123469  |    78   2349      78  | 12469    146    129  |
+-------------------------+-----------------------+----------------------+
|   189       4     1579  |  3579*    59*   3579* |   178      2      6  |
|     3    1267     1269  |  479*b     8  2469-7  |  147*b 1457*b  157*b |
|   268   25678     2567  |     1   2456    2467  |   478      9      3  |
+-------------------------+-----------------------+----------------------+
|   168       9     1357  |     2    156    3568  |   167  13678      4  |
| 12468   12368    12346  |  3489      7   34689  |     5   1368   1289  |
| 12468  123578  1234567  | 34589  14569  345689  | 12679  13678  12789  |
+-------------------------+-----------------------+----------------------+

Overlap 3-element Grouped Nice Loop: ALS:r2c1237 -7- r456c7 =7= r5c89 -7- ALS:r1235c2 ~3~  => r3c3<>3
+-------------------------+-----------------------+----------------------+
|     7    126*d       8  |   459   2459    2459  |     3   1456   1259  |
|   249*    23*d    2349* |     6  23459       1  |  2479*  4578   2578  |
|     5   1236*d 12469-3  |    78   2349      78  | 12469    146    129  |
+-------------------------+-----------------------+----------------------+
|   189       4     1579  |  3579     59    3579  |  178*b     2      6  |
|     3   1267*d    1269  |   479      8   24679  |  147*b 1457*c  157*c |
|   268   25678     2567  |     1   2456    2467  |  478*b     9      3  |
+-------------------------+-----------------------+----------------------+
|   168       9     1357  |     2    156    3568  |   167  13678      4  |
| 12468   12368    12346  |  3489      7   34689  |     5   1368   1289  |
| 12468  123578  1234567  | 34589  14569  345689  | 12679  13678  12789  |
+-------------------------+-----------------------+----------------------+

Overlap 4-element Grouped Nice Loop: ALS:r2c1235 -5- r4c5 -9- r4c13 =9= r5c3 -9- r23c3 =9= r2c1 ~9~ 
   => r2c7<>9
+-------------------------+-----------------------+----------------------+
|     7     126        8  |   459   2459    2459  |     3   1456   1259  |
|  249*c     23*   2349*c |     6  23459*      1  | 247-9   4578   2578  |
|     5    1236   123469* |    78   2349      78  | 12469    146    129  |
+-------------------------+-----------------------+----------------------+
|  189*b      4    1579*b |  3579     59*   3579  |   178      2      6  |
|     3    1267     1269* |   479      8   24679  |   147   1457    157  |
|   268   25678     2567  |     1   2456    2467  |   478      9      3  |
+-------------------------+-----------------------+----------------------+
|   168       9     1357  |     2    156    3568  |   167  13678      4  |
| 12468   12368    12346  |  3489      7   34689  |     5   1368   1289  |
| 12468  123578  1234567  | 34589  14569  345689  | 12679  13678  12789  |
+-------------------------+-----------------------+----------------------+

4-element grouped nice loop ( -7- r5c4789 -9- r4c5 -5- r2c5 -9- r2c12357 -7- r456c7 =7= r5c89 -7- ): r2c5=23459
   => r5c26<>7
+--------------------------+-----------------------+---------------------------+
|      7     126        8  |   459   2459    2459  |       3     1456    1259  |
|    249b     23b    2349b |     6  23459b      1  |    2479b    4578    2578  |
|      5    1236   123469  |    78   2349      78  |   12469      146     129  |
+--------------------------+-----------------------+---------------------------+
|    189       4     1579  |  3579     59e   3579  |     178c       2       6  |
|      3   126-7     1269  |   479e     8  2469-7  |     147c    1457c    157c |
|    268   25678     2567  |     1   2456    2467  |     478c       9       3  |
+--------------------------+-----------------------+---------------------------+
|    168       9     1357  |     2    156    3568  |     167    13678       4  |
|  12468   12368    12346  |  3489      7   34689  |       5     1368    1289  |
|  12468  123578  1234567  | 34589  14569  345689  |   12679    13678   12789  |
+--------------------------+-----------------------+---------------------------+

And just for something a little esoteric a Kraken ALS (similar to the traditional ALS but with a multi-inference node at the ALS (in this case two chains linking the 7's in the ALS):

Code: Select all

1-element Kraken ALS (r5c9 -7- r456c7 -1- , r89c9 -78- r7c78|r89c8 -1- ): r13589c9=78 => r9c7<>1
+-------------------------+-----------------------+------------------------+
|     7     126        8  |   459   2459    2459  |      3    1456   1259* |
|   249      23     2349  |     6  23459       1  |   2479    4578   2578  |
|     5    1236   123469  |    78   2349      78  |  12469     146    129* |
+-------------------------+-----------------------+------------------------+
|   189       4     1579  |  3579     59    3579  |    178b      2      6  |
|     3    1267     1269  |   479      8   24679  |    147b   1457    157* |
|   268   25678     2567  |     1   2456    2467  |    478b      9      3  |
+-------------------------+-----------------------+------------------------+
|   168       9     1357  |     2    156    3568  |   167cd 13678cd     4  |
| 12468   12368    12346  |  3489      7   34689  |      5   1368cd  1289* |
| 12468  123578  1234567  | 34589  14569  345689  | 2679-1  13678cd 12789* |
+-------------------------+-----------------------+------------------------+

[denis_berthier]

Denis, thanks for the link to the French site. A little translation ("/" -> "-", "-" -> "=", "#" -> "<>") and I could pretty much follow the eliminations.

Some participants use # instead of our usual <>. But, for participants who use nrczt-chains, my notation is also used: # for the t-candidates and * for the z-candiidates (see e.g. dxp here: http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=765)

The solution I looked at used a dynamic forcing chain, but I could also see examples of t-chains. I especially like the clear indication of the extra links.

The nrc notation has two variants:
- the sloppy one: only the left- and right- linking candidates are displayed; this is the version output by SudoRules; (for technical reasons, it'd make SudoRules less efficient if it had to keep the extra information about the t and z candidates);
- the strict one: the t- and z- candidates are also displayed, followed resp. by the # or * sign; after the # sign one can write either the number of the justifying candidate in the chain or the candidate itself (e.g. n1r1c1).
In some sense, the sloppy version is incomplete. But:
- details can easily be re-built from the PM. What's hard is not re-building these details, it's finding the chains;
- when you progressively build the chain, you have to deal with the t and z candidates of the current step but, after this, you can forget them: the next candidates in the chain depend only on the previous (right) linking candidates.
Both versions insist that nrczt chains are chains and not any kind of nets.
On the sudoku-factory forum, some participants prefer a net notation. I personally don't like this, because it completely hides the difference between nrczt-chains and nrczt-nets. (OK, I don't use nrczt-nets, but, if one accepts nets, it's easy to define them as extensions of nrczt-chains - and they obviously subsume Grouped NLs).

Here are a few eliminations at the point you posted the Pencil Marks minus the naked singles.

As I did the eliminations by hand, I forgot 2 Singles. The first PM in your last post is the correct starting point (where SudoRules gets stuck).
This is a very interesting situation for me: for the first time, with your first elimination, we have an example of a short grouped NL that cannot be replaced by any nrczt-chain. I need your first 4 rules before nrczt chains (upto length 12) can finish the puzzle.


Conversely, it'd be interesting to have an explicit example of a situation where none of the rules in your solver (a very impressive set of rules) applies, but an nrczt-chain unblocks the situation.
If you wanted to post the final situation you reach for any of #113, #125 or #181, I could give an nrczt-chain that unblocks this situation.

[Mike Barker]

Here's the grid for #113. Note that although I have many techniques in my solver they are not all fully implemented. I need to speed things up substantially for a fuller implementation. For example my grouped nice loops are only up to 7 elements with limitations on ALS size and my multi-inference eliminations are limited to two elements per chain from the kraken node. Also my t-chains are only up to 12 elements (none were used in to get to this point in the solution). Champagne could probably solve all 1465 with his solver and he, Carcul, Steve, and others could solve all with shear mental prowess (Carcul already solved the toughest #77).

Code: Select all

+----------------------+---------------------+--------------------+
|     5   4678  14689  |    2    169    179  |    3   178    147  |
|   134   3467   1346  |  567      8    157  | 1257     9  12457  |
|   189     78      2  |  579      3      4  | 1578  1578      6  |
+----------------------+---------------------+--------------------+
|     6  23458    348  |    1    245    278  |    9   357   2357  |
|  2389      1    389  |  678   2569   2789  | 2567     4   2357  |
|   249    245      7  | 4569  24569      3  | 1256   156      8  |
+----------------------+---------------------+--------------------+
|     7    268    168  |    3   1259  12589  |    4   568     15  |
|  1348      9  13468  |  458      7    158  | 1568     2    135  |
| 12348   2348      5  |   48    124      6  |  178  1378      9  |
+----------------------+---------------------+--------------------+

[denis_berthier]

Here's the grid for #113. Note that although I have many techniques in my solver they are not all fully implemented. I need to speed things up substantially for a fuller implementation. For example my grouped nice loops are only up to 7 elements with limitations on ALS size and my multi-inference eliminations are limited to two elements per chain from the kraken node. Also my t-chains are only up to 12 elements (none were used in to get to this point in the solution).

Complex patterns, such as unrestricted chains of ALSs, not speaking of AAAAAAHHHH-LSs, have a computational cost (time and memory). The same is of course true for complex nrczt chains. It is therefore natural that you put such limitations in your solver, especially as I don't think a human solver, unless being exceptionally clever and spending days on them, could solve any of the extreme puzzles we are discussing.

Here are the first nrczt-rules that apply in the situation described in your post for top1465#113:

Code: Select all

+----------------------+---------------------+--------------------+
|     5   4678  14689  |    2    169    179  |    3   178    147  |
|   134   3467   1346  |  567      8    157  | 1257     9  12457  |
|   189     78      2  |  579      3      4  | 1578  1578      6  |
+----------------------+---------------------+--------------------+
|     6  23458    348  |    1    245    278  |    9   357   2357  |
|  2389      1    389  |  678   2569   2789  | 2567     4   2357  |
|   249    245      7  | 4569  24569      3  | 1256   156      8  |
+----------------------+---------------------+--------------------+
|     7    268    168  |    3   1259  12589  |    4   568     15  |
|  1348      9  13468  |  458      7    158  | 1568     2    135  |
| 12348   2348      5  |   48    124      6  |  178  1378      9  |
+----------------------+---------------------+--------------------+


I've used the strict nrc notation, with all the additional candidates added manually together with the explicit references to their justifying candidates. Perhaps, given these chains, you may see corresponding ALS more complex than those you have programmed? As I'm not an expert in ALS, I can't.

nrczt9-chain n1r3{c8 c1} - n9{r3c1 r1c3} - n4r1{c3 c2 c9*} - n8r1{c2 c8 c3#n9r1c3} - n8r3{c7 c2 c1#n1r3c1 c8#n8r1c8} - n7{r3 r2 r1#n4r1c2}c2 - n6{r2 r7 r1#n4r1c2}c2 - {n6 n5 n8#n8r1c8}r7c8 - {n5 n1}r7c9 ==> r1c9 <> 1
nrczt11-chain n9r7{c5 c6} - n2r7{c6 c2 c5*} - n2r9{c1 c5 c2#n2r7c2} - n1{r9 r1 r7*}c5 - n9r1{c5 c3 c6#n9r7c6} - n6r1{c3 c2 c5#n1r1c5} - n8r1{c2 c8 c3#n9r1c3} - n8r7{c8 c3 c2#n2r7c2 c6#n9r7c6} - {n8 n3 n9#n9r1c3}r5c3 - {n3 n4 n8#n8r7c3}r4c3 - {n4 n5 n2#n2r9c5}r4c5 ==> r7c5 <> 5
column c5 interaction-with-block b5 ==> r6c4 <> 5

Now comes a very long nrczt chain with a long distance interaction (a rare event) between the first and the last but one cells.
It is also an example of how z-candidates can be present in the first cell of 3D-chains (which is not possible in the 2D chains). Notice that this possibility allowed by the general definition is very rarely needed and it has a high computational cost.

nrczt15-chain n5{r8c4 r7c6 r8c6*} - n9r7{c6 c5} - n2r7{c5 c2 c6#n5r7c6} - n2{r7c6 r9c5 r7c4#n2r7c5} - n1{r9 r1 r7#n9r7c5}c5 - {n1 n7 n5#n5r7c6}r2c6 - {n7 n9 n1#n1r1c5}r1c6 - n9{r1c3 r3c1} - {n9 n5 n7#n7r2c6}r3c4 - {n5 n6 n7#n7r2c6}r2c4 - n6{r2 r1 r7#n2r7c2}c2 - n7{r1 r3 r2#n7r2c6}c2 - n8{r3c2 r1c3 r1c2#n6r1c2 r3c1#n9r3c1} - n8r7{c3 c8 c2#n2r7c2 c6#n5r7c6} - n6{r7c8 r8c7} ==> r8c7 <> 5

As I don't have much time and I'm not sure such details would be useful for you, let me revert to the sloppy nrc notation for the next steps (the longest chains in the resolution path):
nrczt16-rl-lasso n1{r6c7 r6c8} - n6{r6c8 r7c8} - {n6 n8}r8c7 - {n8 n7}r9c7 - {n7 n5}r3c7 - n1{r3c7 r3c1} - n1{r9c1 r9c5} - {n1 n5}r8c6 - {n5 n4}r8c4 - {n4 n8}r9c4 - n8{r9c1 r5c1} - n9{r5c1 r6c1} - {n9 n3}r5c3 - {n3 n4}r4c3 - {n4 n6}r2c3 - n6{r8c3 r8c7} ==> r2c7 <> 1
nrczt16-lr-lasso n5{r8c4 r7c6} - n9{r7c6 r7c5} - n2{r7c5 r9c5} - n1{r9c5 r1c5} - n6{r1c5 r2c4} - n5{r2c4 r2c7} - n5{r5c7 r5c5} - n6{r5c5 r5c7} - n6{r8c7 r8c3} - n3{r8c3 r8c1} - n3{r9c2 r9c8} - n7{r9c8 r9c7} - n1{r9c7 r9c1} - {n1 n4}r2c1 - n4{r1c3 r4c3} - {n4 n2}r4c5 ==> r8c9 <> 5
row r8 interaction-with-block b8 ==> r7c6 <> 5
nrczt17-lr-lasso n1{r6c7 r6c8} - n6{r6c8 r7c8} - n5{r7c8 r7c9} - n1{r7c9 r2c9} - {n1 n3}r8c9 - n3{r9c8 r4c8} - n5{r4c8 r3c8} - n1{r3c8 r3c1} - n9{r3c1 r1c3} - n1{r1c3 r7c3} - n1{r9c1 r9c5} - {n1 n6}r1c5 - n6{r1c2 r2c2} - n3{r2c2 r9c2} - n2{r9c2 r9c1} - {n2 n8}r7c2 - n8{r1c2 r3c2} ==> r8c7 <> 1
nrczt17-lr-lasso {n4 n8}r9c4 - {n8 n5}r8c4 - {n5 n1}r8c6 - n1{r7c5 r1c5} - n6{r1c5 r2c4} - {n6 n7}r5c4 - {n7 n9}r3c4 - {n9 n7}r1c6 - {n7 n8}r1c8 - n8{r3c7 r8c7} - n6{r8c7 r7c8} - n5{r7c8 r7c9} - n1{r7c9 r2c9} - n1{r2c3 r7c3} - n1{r9c1 r3c1} - n8{r3c1 r3c2} - n8{r7c2 r7c6} ==> r9c5 <> 4

The end of the path to the solution is much easier.

(Carcul already solved the toughest #77).

Just for fun, would you like trying to solve it with the combination of our two solvers?

The puzzle is:
700000400
020070080
003008009
000500300
060020090
001007006
000300900
030040060
009001005

Here are the first (hard) eliminations before I run out of memory:
***** SudoRules version 13 *****
hidden-single-in-a-row ==> r9c8 = 3
row r9 interaction-with-block b7 ==> r7c3 <> 4, r7c2 <> 4, r7c1 <> 4
nrczt12-lr-lasso n4{r9c1 r9c2} - n4{r3c2 r3c4} - n4{r2c6 r4c6} - {n4 n3}r5c6 - n3{r6c5 r6c1} - n4{r6c1 r6c8} - n2{r6c8 r6c7} - n2{r3c7 r3c8} - n7{r3c8 r3c7} - {n7 n8}r9c7 - {n8 n6}r9c5 - n6{r4c5 r4c6} ==> r5c1 <> 4
nrczt12-lr-lasso n6{r4c6 r4c5} - {n6 n8}r9c5 - {n8 n5}r7c5 - {n5 n2}r7c6 - n6{r7c6 r9c4} - n6{r1c4 r1c3} - n6{r3c1 r3c7} - n7{r3c7 r3c8} - n2{r3c8 r3c4} - n4{r3c4 r2c4} - {n4 n5}r2c3 - n5{r3c1 r3c2} ==> r2c6 <> 6
nrczt13-lr-lasso {n8 n6}r9c5 - {n6 n5}r7c5 - {n5 n1}r3c5 - {n1 n9}r4c5 - {n9 n4}r6c4 - {n4 n3}r5c6 - n3{r5c1 r6c1} - n9{r6c1 r2c1} - {n9 n6}r2c4 - n6{r1c6 r1c3} - n8{r1c3 r1c2} - n1{r1c2 r7c2} - n1{r3c2 r3c1} ==> r6c5 <> 8
nrczt15-lr-lasso {n4 n3}r5c6 - n3{r5c1 r6c1} - {n3 n9}r6c5 - {n9 n6}r4c6 - n4{r4c6 r2c6} - n4{r2c3 r4c3} - n4{r6c2 r6c8} - n2{r6c8 r6c7} - n5{r6c7 r5c7} - n1{r5c7 r5c9} - {n1 n3}r2c9 - {n3 n2}r1c9 - n2{r3c8 r3c4} - n2{r9c4 r9c1} - n2{r4c1 r4c3} ==> r5c4 <> 4
nrczt16-lr-lasso n6{r2c7 r3c7} - n7{r3c7 r3c8} - n2{r3c8 r3c4} - n4{r3c4 r6c4} - {n4 n3}r5c6 - {n3 n9}r6c5 - {n9 n6}r4c6 - n4{r4c6 r2c6} - {n4 n5}r2c3 - n5{r2c7 r1c8} - {n5 n9}r1c6 - {n9 n1}r1c4 - {n1 n8}r5c4 - {n8 n5}r5c1 - {n5 n8}r6c2 - {n8 n1}r1c2 ==> r2c4 <> 6
.

[Mike Barker]

Cool idea, alas my solver could make no more progress from the point you left off.

As far as finding ALS, my guess is that it is very unlikely since it looks like all of your chains include z-links which removes an extra candidate. Without this there are probably few equivalent nice loops. For #77, my solver did find one nice loop which starts off the same way as one of your lassos.

Code: Select all

4-element Grouped Nice Loop: r4c6 =6= r4c5 -6- ALS:r379c5 -1- ALS:r3c12|r2c3 -6- r1c3 =6= r1c456 ~6~  => r2c6<>6
+----------------------+------------------------+---------------------+
|      7  1589    568* |  1269d  13569d  23569d |     4   125    123  |
|  14569     2    456c |  1469       7  3459-6  |   156     8     13  |
|   1456c  145c     3  |  1246     156b      8  | 12567  1257      9  |
+----------------------+------------------------+---------------------+
|   2489  4789   2478  |     5    1689*    469* |     3  1247  12478  |
|   3458     6   4578  |   148       2      34  |  1578     9   1478  |
| 234589  4589      1  |   489     389       7  |   258   245      6  |
+----------------------+------------------------+---------------------+
|  12568  1578  25678  |     3     568b    256  |     9  1247  12478  |
|   1258     3   2578  |  2789       4     259  |  1278     6   1278  |
|   2468   478      9  |  2678      68b      1  |   278     3      5  |
+----------------------+------------------------+---------------------+

nrczt12-lr-lasso n6{r4c6 r4c5} - {n6 n8}r9c5 - {n8 n5}r7c5 - {n5 n2}r7c6 - n6{r7c6 r9c4} - n6{r1c4 r1c3} - n6{r3c1 r3c7} - n7{r3c7 r3c8} - n2{r3c8 r3c4} - n4{r3c4 r2c4} - {n4 n5}r2c3 - n5{r3c1 r3c2} ==> r2c6 <> 6