The New Sudoku Players' Forum

[ronk]

I would like to ask if the following qualifies as a doubly linked ALS? The issue might be that one of the ALSs has only one cell. It can be written (at least) two ways:

Way #1: Sets: A = {r1c156} = {1358}; B = {r2c6} = {13} linked by 13
Way #2: Sets: A = {r1c1} = {58}; B = {r1c56,r2c6} = {1358} linked by 58
Eliminations(8) = r1c279<>5, r2c5<>13, r3c5<>13, r3c6<>13

It's a special case of ALS doubly-linked xz-rule known as Two-Sector Disjoint Subsets (TSDS), perhaps more popularly known as Sue De Coq (SDC). The SDC was introduced by rubylips, who also posted using the alias Sue De Coq.

[aran]

I would like to ask if the following qualifies as a doubly linked ALS? The issue might be that one of the ALSs has only one cell. It can be written (at least) two ways:

Way #1: Sets: A = {r1c156} = {1358}; B = {r2c6} = {13} linked by 13
Way #2: Sets: A = {r1c1} = {58}; B = {r1c56,r2c6} = {1358} linked by 58
Eliminations(8) = r1c279<>5, r2c5<>13, r3c5<>13, r3c6<>13

Code: Select all

  +--------------------------------------------------------------------------------------+
  | (58)     134-57   9        | 2        (1358)   (138)    | 34-57    6        13-57    |
  | 6        1357     17       | 4        -1-359   (13)     | 2357     2379     8        |
  | 2        1345     148      | 7        -1-35689  -1-368  | 345      349      1359     |
  +--------------------------------------------------------------------------------------+
  | 589      45       248      | 569      2368     7        | 34568    1        359      |
  | 589      1457     12478    | 1569     12368    123468   | 345678   34789    3579     |
  | 3        6        1478     | 159      18       148      | 4578     4789     2        |
  +--------------------------------------------------------------------------------------+
  | 7        2        3        | 8        4        9        | 1        5        6        |
  | 1        9        6        | 3        7        5        | 28       28       4        |
  | 4        8        5        | 16       126      126      | 9        37       37       |
  +--------------------------------------------------------------------------------------+
 
     8r1  5r1  1b2  3b2 (NRC notation)

1N1: 811==511           
      |    |             
1N5: 815==515==115==315
      |         |    |   
1N6: 816=======116==316 
                |    |
2N6:           126==326
 
As cover sets:
     4 Base Sets  = {1n156 2n6}
     4 Cover Sets = {58r1 13b2}

Both versions are perfectly sound doubly linked ALS.
For interest the hidden triple version:
138(r1c56+r2c6)=5r1c1-(5=8)r1c1-(8=13)r1c6 (=> pair13 r12c6) : =><13>r2c5, r3c56 (<5> r1c2 follows on trivially).

[Myth Jellies]

A bivalue cell is N+1 digits in N cells so it qualifies. It is an Almost Locked (Naked) Single. The simplest double-linked xz-case should be the naked pair.

[ronk]

In this example, two ALSs in two boxes are doubly-linked in two different rows. In addition to the x,z eliminations in r8 and r9, eliminations due to locking of the ALSs occurs in b7 and b9.

Code: Select all


top1465_1038 after SSTS
 18    3       2     | 4     57    9     | 57    6     18
 5789  4       578   | 6     57    1     | 23579 23579 289
 1579  1579    6     | 28    3     28    | 4     1579  19
---------------------+-------------------+------------------
 1578  1578    4     | 389   2     358   | 789   79    6
 2568  258     9     | 7     1     4568  | 28    24    3
 2678  278     3     | 89    4689  468   | 1     2479  5
---------------------+-------------------+------------------
 2579  2579    157   | 239   49    234   | 6     8     147-29
 3     269-8  A18    | 5     4689  7     |B29   B129   4-129
 4     269-78 A78    | 1     689   268   | 35    35   B279

Sets: A = {r89c3} = {178}; B = {r8c78,r9c9} = {1279}
    x,z = 1,7 and x,z = 7,1

Elims: r8c9<>1, r9c2<>7, r89c2<>8, r78c9<>29 (8 elims)

Other perspectives:

Code: Select all

As constraint sets: 5  base sets: r89c3,r8c78,r9c9
                    5 cover sets: 1r8, 7r9, 8b7, 29b9

As continuous nice loop:

als:(r9c3 =7|8|1= r8c3) -1- als:(r8c78 =1|29|7= r9c9) -7- continuous

Same eliminations as above

[aran]

In this example, two ALSs in two boxes are doubly-linked in two different rows. In addition to the x,z eliminations in r8 and r9, eliminations due to locking of the ALSs occurs in b7 and b9.

Code: Select all


top1465_1038 after SSTS
 18    3       2     | 4     57    9     | 57    6     18
 5789  4       578   | 6     57    1     | 23579 23579 289
 1579  1579    6     | 28    3     28    | 4     1579  19
---------------------+-------------------+------------------
 1578  1578    4     | 389   2     358   | 789   79    6
 2568  258     9     | 7     1     4568  | 28    24    3
 2678  278     3     | 89    4689  468   | 1     2479  5
---------------------+-------------------+------------------
 2579  2579    157   | 239   49    234   | 6     8     147-29
 3     269-8  A18    | 5     4689  7     |B29   B129   4-129
 4     269-78 A78    | 1     689   268   | 35    35   B279

Sets: A = {r89c3} = {178}; B = {r8c78,r9c9} = {1279}
    x,z = 1,7 and x,z = 7,1

Elims: r8c9<>1, r9c2<>7, r89c2<>8, r78c9<>29 (8 elims)

Other perspectives:

Code: Select all

As constraint sets: 5  base sets: r89c3,r8c78,r9c9
                    5 cover sets: 1r8, 7r9, 8b7, 29b9

As continuous nice loop:

als:(r9c3 =7|8|1= r8c3) -1- als:(r8c78 =1|29|7= r9c9) -7- continuous

Same eliminations as above

And <8> r2c3

[PIsaacson]

Code: Select all

top1465 #247
..9..63...72..........17..51..3..9..........86.84....1.6.........1.2....9.3...45.

After SSTS
 
 *-----------------------------------------------------------------------------*
 | 458     1       9       | A258     45-8    6      | 3       2478    247     |
 | 458     7       2       | A589     3459-8  3459-8 | 168     14689   469     |
 | 348     348     6       | A289     1       7      | 28      2489    5       |
 |-------------------------+-------------------------+-------------------------|
 | 1       245     457     | 3       5678    258     | 9       2467    2467    |
 | 2347    23459   457     | 167-59  5679    1259    | 2567    23467   8       |
 | 6       2359    8       | 4       579     259     | 257     237     1       |
 |-------------------------+-------------------------+-------------------------|
 | 2478    6       457     | B579-8   3459-78 3459-8 | 1278    12789   2379    |
 | 478     458     1       | B5679-8  2       3459-8 | 678     6789    3679    |
 | 9       28      3       | B167-8  B678    B18     | 4       5       267     |
 *-----------------------------------------------------------------------------*

Sets:  A = {r123c4} = {2589}
       B = {r78c4,r9c456} = {156789}

       dual linked {59}

Eliminates:  r1c5<>8, r2c56<>8, r5c4<>59, r789c4<>8, r7c5<>78, r78c6<>8

       12 eliminations, but notice that r789c4<>8 is cannibalistic

I was comparing my solver with the prior listed dual-linked ALS chains and obtained identical results when restricting it to an ALS max 5 candidates. When I set the max to 6 candidates, my ALS chain method found the above dual-linked ALS chain with 12 candidate eliminations. What concerns me is that there are 3 eliminations within the B ALS. I've reviewed my code and the rules for dual-linked eliminations, and this appears to be legal, although disconcerting. The reductions are all valid and the final solution is correct, so my question is, am I violating some un-written rule or is this okay? I've inserted code to detect when the eliminations are self-consuming and for dual-linked ALSs I'm hitting this often enough that if it's illegal, it should be triggering invalid solutions, but it's not. Clearly the 8's in question do indeed see all of the 8's in the A ALS, but is that sufficient or am I just lucky because there are additional existant 8s in the B ALS?

[ronk]

When I set the max to 6 candidates, my ALS chain method found the above dual-linked ALS chain with 12 candidate eliminations. What concerns me is that there are 3 eliminations within the B ALS. I've reviewed my code and the rules for dual-linked eliminations, and this appears to be legal, although disconcerting. The reductions are all valid and the final solution is correct, so my question is, am I violating some un-written rule or is this okay?

I'm quite sure the deduction for your posted pattern is perfectly valid.

I posted a similar deduction recently, which had only one cannibalistic elimination. After Allan Barker pointed out via PM a smaller pattern which made the same elimination non-cannibalisticly, I quickly deleted the post. If there's a similar smaller pattern for your three 8s, I can't find it.

[Allan Barker]

Hi PIsaacson,

I posted a similar deduction recently, which had only one cannibalistic elimination. After Allan Barker pointed out via PM a smaller pattern which made the same elimination non-cannibalisticly, I quickly deleted the post. If there's a similar smaller pattern for your three 8s, I can't find it.

I'm not qualified to comment on rules or common practice, as I often don't know myself. However, there are "sub-solutions" in your solution that will eliminate the 8s non-cannibalistically. It takes 3 slightly different solutions to eliminate them one at a time. One example is, first in terms of "cell sets":

Sets: A = {r123c4} = {2589}
B = {r7c4,r9c456} = {156789}

Then in terms of base/cover sets:

PIXA 22 Nodes, Raw Rank = 1 (linksets - sets)
7 Sets = {12379N4 9N5 9N6}
8 Links = {589c4 2b2 1678b8}
--> (8c4*8b8) => r8c4<>8,

In terms of base/cover sets, there are 7 base and 8 cover sets so any two cover sets that overlap can cause an elimination, in this case column set 8c4 overlaps box set 8b8 thus => r8c4<>8, one of your (now exorcized) cannibalized victims.

Curiously, there is a 13th elimination, r9c2, due to a particular cover set group. This is eliminated by row set 8r9, which is part of this cover set group.

PIXB 27 Nodes, Raw Rank = 0 (linksets - sets)
8 Sets = {123789N4 9N5 9N6}
8 Links = {8r9 589c4 2b2 167b8}
--> r5c4<>5, r5c4<>9, r7c5<>7, r9c2<>8], r9c4<>8,

Maybe the cannibalized candidates should be considered collateral eliminations?

[Steve K]

By theorem, in a case like this, there must be an [almost hidden set cross almost naked set] usage that dodges the cannibalism but still gets the eliminations:

(nt258=9)r123c4 - (9)r789c4 = (ht349-ht345)r7c56,r8c6 = (5)r789c4 - (5=nt289)r123c4 => loop

Of course, there is also a [hidden set x hidden set] usage that does not get all the eliminations, but does lock the 8s after making the eliminations.

[ronk]

By theorem, in a case like this, there must be an [almost hidden set cross almost naked set] usage that dodges the cannibalism but still gets the eliminations:

(nt258=9)r123c4 - (9)r789c4 = (ht349-ht345)r7c56,r8c6 = (5)r789c4 - (5=nt289)r123c4 => loop

The only AHS I see in that AIC is {r7c456,r8c46} = {3459}, five cells with four candidates. Since two of the deductions (r78c4<>8) are in two cells of that AHS, how can you say that cannibalism has been dodged?

Code: Select all

 458    1      9      |A258    458     6      | 3      2478   247
 458    7      2      |A589    34589   34589  | 168    14689  469
 348    348    6      |A289    1       7      | 28     2489   5
----------------------+-----------------------+---------------------
 1      245    457    | 3      5678    258    | 9      2467   2467
 2347   23459  457    | 167-59 5679    1259   | 2567   23467  8
 6      2359   8      | 4      579     259    | 257    237    1
----------------------+-----------------------+---------------------
 2478   6      457    |B579-8 B3459-78 3459-8 | 1278   12789  2379
 478    458    1      |B5679-8 2      B3459-8 | 678    6789   3679
 9      28     3      | 167-8  678     18     | 4      5      267

After the eliminations, there is an ALS in r7c56,r8c6}, so there must have been a hidden ALS before. How might that fit into the deduction? Hmmm, I don't know.

[Steve K]

Ronk: The sis considered are: (2589)r123c4, (3459)Box8. No member of these sis is eliminated. I see no cannibalism.
A formal treatment could be;
S1 (2589)r123c4 - one degree of freedom ALS
S2(34)r7c56, r8c6 - one degree of freedom AHS
Doubly linked: (5)S2=(5)column4Box8-(5)S1 = (9)S1 - (9)column4Box8 = (9)S2

[ronk]

The sis considered are: (2589)r123c4, (3459)Box8. No member of these sis is eliminated. I see no cannibalism.

OK, basing cannibalism strictly on the candidates, while ignoring their locations, works for me.

Maybe the cannibalized candidates should be considered collateral eliminations?

Not bad. With fish, the term remora has been used for the smaller fish that picked off "cannibalized candidates" of larger fish. Hence, a food name for both remora and its host might be appropriate too.

[PIsaacson]

I'm starting to believe that after constructing an ALS chain, especially a dual-linked variety, I should use subset counting or base/cover analysis to locate the complete set of candidate eliminations. If so, then the r9c2<>8 reduction can be included based on subset counting of my ALS cannibalistic example, raising the total to 13 eliminations.

However, I'm still uncertain whether or not there is agreement on allowing ALS chains to exhibit cannibalism, regardless of how they can be redefined or expressed in alternative POVs. Clearly, the ALSs that I presented performed an act of self immolation. I believe that everyone who's look at this thinks this particular case is okay, but is that sufficient to generalize to an all encompassing rule?

[aran]

I'm starting to believe that after constructing an ALS chain, especially a dual-linked variety, I should use subset counting or base/cover analysis to locate the complete set of candidate eliminations. If so, then the r9c2<>8 reduction can be included based on subset counting of my ALS cannibalistic example, raising the total to 13 eliminations.

However, I'm still uncertain whether or not there is agreement on allowing ALS chains to exhibit cannibalism, regardless of how they can be redefined or expressed in alternative POVs. Clearly, the ALSs that I presented performed an act of self immolation. I believe that everyone who's look at this thinks this particular case is okay, but is that sufficient to generalize to an all encompassing rule?

I'm not clear why anybody would want to avoid the cannibalizing brethren. They do a very good job.
The logic is well-founded, and the principle is this :
if any candidate in one ALS, other than both dual-linking candidates, see all instances of that candidate in the other ALS, then it is eliminated.

[ronk]

I'm starting to believe that after constructing an ALS chain, especially a dual-linked variety, I should use subset counting or base/cover analysis to locate the complete set of candidate eliminations. If so, then the r9c2<>8 reduction can be included based on subset counting of my ALS cannibalistic example, raising the total to 13 eliminations.

While it makes for a more impressive example when posting, I don't think it's worth the trouble for a programmed solver. Such eliminations will be picked up by a locked candidates technique (aka box/line interaction), which programmed solvers will likely execute whether or not there's an elimination left to be found.

I'm still uncertain whether or not there is agreement on allowing ALS chains to exhibit cannibalism, regardless of how they can be redefined or expressed in alternative POVs.

If you exhaustively search for ALS xz-rule eliminations of size N (and smaller), I don't think there will be any cannibalistic ALS xz-rule eliminations of size N+1 remaining. Here N is the total number of cells in the two sets.

But anytime a cannibalistic elimination is encountered, take it.