## Almost Locked Sets xz-rule (doubly-linked)

Advanced methods and approaches for solving Sudoku puzzles
Allan Barker wrote: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.
ronk
2012 Supporter

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

Allan Barker wrote: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).
Last edited by aran on Tue Dec 09, 2008 10:28 am, edited 1 time in total.
aran

Posts: 334
Joined: 02 March 2007

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.
Myth Jellies

Posts: 593
Joined: 19 September 2005

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   B279Sets: A = {r89c3} = {178}; B = {r8c78,r9c9} = {1279}    x,z = 1,7 and x,z = 7,1Elims: 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, 29b9As continuous nice loop:als:(r9c3 =7|8|1= r8c3) -1- als:(r8c78 =1|29|7= r9c9) -7- continuousSame eliminations as above`
ronk
2012 Supporter

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

ronk wrote: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   B279Sets: A = {r89c3} = {178}; B = {r8c78,r9c9} = {1279}    x,z = 1,7 and x,z = 7,1Elims: 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, 29b9As continuous nice loop:als:(r9c3 =7|8|1= r8c3) -1- als:(r8c78 =1|29|7= r9c9) -7- continuousSame eliminations as above`

And <8> r2c3
aran

Posts: 334
Joined: 02 March 2007

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?
PIsaacson

Posts: 249
Joined: 02 July 2008

PIsaacson wrote: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.
ronk
2012 Supporter

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

Hi PIsaacson,

Ronk wrote: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?
Allan Barker

Posts: 266
Joined: 20 February 2008

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.
Steve K

Posts: 98
Joined: 18 January 2007

Steve K wrote: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.
ronk
2012 Supporter

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

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
Steve K

Posts: 98
Joined: 18 January 2007

Steve K wrote: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.

Allan Barker wrote: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.
ronk
2012 Supporter

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

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?
PIsaacson

Posts: 249
Joined: 02 July 2008

PIsaacson wrote: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.
aran

Posts: 334
Joined: 02 March 2007

PIsaacson wrote: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.

PIsaacson wrote: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.
Last edited by ronk on Sun Jan 18, 2009 1:23 am, edited 1 time in total.
ronk
2012 Supporter

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

PreviousNext