Almost Locked Sets xz-rule (doubly-linked)

Advanced methods and approaches for solving Sudoku puzzles

Almost Locked Sets xz-rule (doubly-linked)

Postby ronk » Sat Apr 29, 2006 9:41 pm

Using singles, pairs, and line/box interactions ...puzzle 1038 of the top1465 can be advanced to ...
Code: Select all
002009060040001000006030400000020000009700003003000105000000680300507000400100000

 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    -12479
 3    -2689  A18    | 5     4689  7     |B29   B129  -1249
 4    -26789 A78    | 1     689   268   | 35    35   B279

 Sets: A = {r8c3,r9c3} = {178}
       B = {r8c7,r8c8,r9c9} = {1279}
       x,z = 1,7 or x,z = 7,1

 Exclusions: digit 1 from row 8 ( r8c9<>1 )
             digit 7 from row 9 ( r9c2<>7 )
             digit 8 from box 7 ( r89c2<>8 )
             digit 8 from col 3 ( r2c3<>8 ) [edit: added per Myth Jellies]
             digits 2 and 9 from box 9 ( r78c9<>2, r78c9<>9 )

Solvers using almost-locked-sets (ALS) will find the sets noted above and also find the interchangeability of x and z. But this will likely only cause eliminations r8c9<>1 and r9c2<>7.

But the very reason x and z are interchangeable means sets A and B are doubly linked. Using bennys' terminology, both x and z are "restricted common". This means both sets become "locked" and "disjoint" from the rest of the puzzle ... allowing additional exclusions.

This scenario may also be viewed as a continuous nice loop of two almost-locked sets:

-7-(ALS:r9c3=7|1=r8c3)-1-(ALS:r8c78=1|7=r9c9)-

[edit: added starting grid]
Last edited by ronk on Wed May 03, 2006 8:46 am, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Tue May 02, 2006 5:53 am

Don't forget elimination of the 8 up column 3 as well. Using this dual xz-rule, you end up with the same eliminations that subset counting gets, which is cool.

Here is one Alternating Inference Chain equivalent...
Code: Select all
 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    -12479
 3    -2689  C18    | 5     4689  7     |B29   B129  -1249
 4    -26789 A78    | 1     689   268   | 35    35   B279

A8=A7-B7=B(1&2&9)-C1=C8-A8.

Closed AIC loop means that one of the two premises on either side of each weak inference is true...

A7-B7 => remove all other 7's in row 9.
B(1&2&9)-C1 => remove all other 1's in row 8. Either way B contains 29 so eliminate all other 2's and 9's from box 9.
C8-A8 => remove all other 8's from box 7 & column 3
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Carcul » Tue May 02, 2006 8:03 am

Look also this post for another example and the "theoretical" description.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Tue May 02, 2006 12:52 pm

Myth Jellies wrote:Don't forget elimination of the 8 up column 3 as well.

Thanks, I'll add that to my post.

Myth Jellies wrote:A8=A7-B7=B(1&2&9)-C1=C8-A8.

Closed AIC loop means that one of the two premises on either side of each weak inference is true...

A7-B7 => remove all other 7's in row 9.
B(1&2&9)-C1 => remove all other 1's in row 8. Either way B contains 29 so eliminate all other 2's and 9's from box 9.
C8-A8 => remove all other 8's from box 7 & column 3

That's a pretty way of looking at it as well. I'm actually understanding that notation, so you've either changed it a bit ... or I'm getting used to it.:D

Carcul wrote:Look also this post for another example and the "theoretical" description.

As I posted there, I think the first statement of this rule was here where ...
Bob Hanson wrote:If A and B are almost-locked sets
x,y restricted common to A,B

any z common to any other candidates of A OR B may be eliminated

and

any x or y common to BOTH A AND B may be eliminated

(...)
Code: Select all
            *'
           . .
          .   .       
         X.....X
        /       \
*..z---A        B---z'...*
        \       /
         Y.....Y
          .   .       
           . .
            *'

     any * or *' may be eliminated

I've always thought it unfortunate that Bob used x and y instead of x and z, so I've been occasionally posting from the xz point of view as I did here where ...
ronk wrote:
Code: Select all
ALS xz-rule for doubly-weakly-linked sets
                x*
               . .
              .   .
             x.....x
            /       \
*a....a----A          B----b....b*
            \       /
             z.....z
              .   .
               . .
                z*

... in order to obtain some commonality and continuity in rule syntax.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Wed May 03, 2006 12:42 pm

Here is another example of the ALS xz-rule (doubly-linked) from puzzle #1242 of the top1465:
Code: Select all
280006000040050820010000090020400003300005000000020509002570030100004000400100970


 2     8     359   | B379  -134   6     | 1347  145   1457
 679   4     369   | B379   5     1379  | 8     2     167
 567   1     356   | -2378  348   237   | 3467  9     4567
-------------------+--------------------+-------------------
 5689  2     1569  |  4    A168  -179   | 167   168   3
 3     679   1469  | B6789 A168   5     | 12467 1468  124678
 68    67    146   | B3678  2    -137   | 5     1468  9
-------------------+--------------------+-------------------
 69    69    2     |  5     7     8     | 14    3     14
 1     35    7     | -236   9     4     | 26    568   258
 4     35    8     |  1     36    23    | 9     7     256

 Sets: A = {r45c5} = {168}
       B = {r1256c4} = {36789}
       x,z = 6,8 or x,z = 8,6

 Elims: digits 168 from box 5 ( r4c6<>1, r6c6<>1 )
        digits 379 from col 4 ( r3c4<>3, r3c4<>7, r8c4<>3 )
        digit 1 from col 5 ( r1c5<>1 )

 Continuous ALS nice loop expression:
       -8-(ALS:r45c5=8|1|6=r45c5)-6-(ALS:r1256c4=6|379|8=r1256c4)-
[edit: fixed typo noted by Myth Jellies in nice loop expression]
Last edited by ronk on Thu May 04, 2006 5:33 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Thu May 04, 2006 3:13 am

Several possibilities here...
A6 = A(1&8) - B8 = B(3&6&7&9) - A6
A8 = A(1&6) - B6 = B(3&7&8&9) - A8

Not sure how you managed a labelled 1-link, Ronk, though I am beginning to suspect that you put in these typos on purpose so I will bump your post:)

[Edit] Wait a second...here is one with a 1-link. If you divide A up into A' and A" you can have...
A'(68) = A'1 - A"1 = A"(68). Since either A' or A" must equal 6 or 8, B cannot equal (6&8), Therefore B equals (3&7&9). You don't get the whole thing from that, but you get something.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Fri May 05, 2006 9:14 pm

Here is an example of the ALS xz-rule (doubly-linked) as used by Havard on the Fully symmetrical puzzles thread.
Code: Select all
Almost Locked Sets XZ rule
356789  567     2379    | 13789   47      13489   | 1248#a  456     45689-8
56      1       79      | 789     2       489     | 48#a    3       56
238     39      4       | 5       138     6       | 7       29      18#a
------------------------+-------------------------+---------------------------
139     47      6       | 12389   38      12389   | 5       47      123
34579   2       1379    | 3679    4567    3459    | 134-4   8       3467
13457   457     8       | 1237    4567    1234    | 9       467     123467
------------------------+-------------------------+---------------------------
123     39      5       | 4       18      7       | 6       29      38#b
467     8       237     | 236     9       235     | 234#b   1       3457-3
4679    467     12379   | 12368   56      12358   | 2348#b  457     345789-38

Additional explanation:
Code: Select all
 Sets:  a = {r12c7,r3c9} = {1248}
        b = {r7c9,r89c7} = {2348}
        x,z = 2,4 or x,z = 4,2

 Exclusions: digits 24 from col 7 ( r5c7<>4 )
             digits 18 from box 3 ( r1c9<>8 )
             digits 38 from box 9 ( r89c9<>3, r9c9<>8 )

 Two possible continuous chain expressions:
 -a(18)-4-b(38)-2-a(18)-                 

 -a(2|18|4)-b(4|38|2)-a(2|18|4)-
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Thu Dec 04, 2008 9:18 am

I recently ran across this relatively complex ALS doubly-linked xz-rule with 8 cells that yields 9 eliminations.
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      | 258      45-8    6      | 3      2478   247
 458    7      2      | 589      3459-8  3459-8 | 168    14689  469
 348    348    6      | 289      1       7      | 28     2489   5
----------------------+-------------------------+---------------------
 1      245    457    | 3       A5678   B258    | 9      2467   2467
 2347   23459  457    | 167-59  A5679   B1259   | 2567   23467  8
 6      2359   8      | 4       A579    B259    | 257    237    1
----------------------+-------------------------+---------------------
 2478   6      457    | 5789     3459-78 3459-8 | 1278   12789  2379
 478    458    1      | 56789    2       3459-8 | 678    6789   3679
 9      28     3      | 1678    A678    B18     | 4      5      267

Sets:  A = {r4569c5} = {56789}
       B = {r4569c6} = {12589}
     x,z = 5,9 and x,z = 9,5

Elims: r5c4<>59, r7c5<>78, r12c5<>8, r278c6<>8 (9 elims)

Viewed as distributed disjoint subsets (DDS), all candidates of 8 cells r4569c56 are covered by 3 sectors -- 59b5, 678c5 and 128c6.

[edit: as aran noted, added a missing r7c5<>7]
Last edited by ronk on Thu Dec 04, 2008 8:06 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Thu Dec 04, 2008 2:19 pm

ronk wrote:I recently ran across this relatively complex ALS doubly-linked xz-rule with 8 cells that yields 8 eliminations.
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      | 258      45-8    6      | 3      2478   247
 458    7      2      | 589      3459-8  3459-8 | 168    14689  469
 348    348    6      | 289      1       7      | 28     2489   5
----------------------+-------------------------+---------------------
 1      245    457    | 3       A5678   B258    | 9      2467   2467
 2347   23459  457    | 167-59  A5679   B1259   | 2567   23467  8
 6      2359   8      | 4       A579    B259    | 257    237    1
----------------------+-------------------------+---------------------
 2478   6      457    | 5789     34579-8 3459-8 | 1278   12789  2379
 478    458    1      | 56789    2       3459-8 | 678    6789   3679
 9      28     3      | 1678    A678    B18     | 4      5      267

Sets:  A = {r4569c5} = {56789}
       B = {r4569c6} = {12589}
     x,z = 5,9 and x,z = 9,5

Elims: r5c4<>59, r127c5<>8, r278c6<>8 (8 elims)

Viewed as distributed disjoint subsets (DDS), all candidates of 8 cells r4569c56 are covered by 3 sectors -- 59b5, 678c5 and 128c6.


You can put the elimination count up to 9 :
7r7c5 locks set A which then overlocks set B => <7>r7c5
aran
 
Posts: 334
Joined: 02 March 2007

Postby Allan Barker » Thu Dec 04, 2008 6:02 pm

Sorry if I get this wrong, but I think it is a doubly linked als, however, one of the two als is hidden in box 8. The logic eliminates 12 candidates. Note that cover sets 8b2 and 8c4 are redundant, both producing eliminations.

als:123n4(2589) -59- hidden als:3459b8(r7c456,r8c46) =>
. (8b2) => r1c5<>8, (8b2) => r2c5<>8, (8b2) => r2c6<>8, (5c4) => r5c4<>5,
. (9c4) => r5c4<>9, (8c4) => r7c4<>8, (7n5) => r7c5<>7, (7n5) => r7c5<>8,
. (7n6) => r7c6<>8, (8c4) => r8c4<>8, (8n6) => r8c6<>8, (8c4) => r9c4<>8
Code: Select all
7 Sets   als:123n4(2589) -59- hidden als:3459b8(r7c456,r8c46)
 7+1 Links  {589c4 7n5 78n6 28b2}
     --> (8b2) => r1c5<>8, (8b2) => r2c5<>8, (8b2) => r2c6<>8, (5c4) => r5c4<>5,
         (9c4) => r5c4<>9, (8c4) => r7c4<>8, (7n5) => r7c5<>7, (7n5) => r7c5<>8,
         (7n6) => r7c6<>8, (8c4) => r8c4<>8, (8n6) => r8c6<>8, (8c4) => r9c4<>8

top1465 #247
..9..63...72..........17..51..3..9..........86.84....1.6.........1.2....9.3...45.
After SSTS +---------------------------------------------------------------------------------------+
  | 458      1        9        | A(258)   45-8      6        | 3        2478     247      |
  | 458      7        2        | A(589)   345-89    345-89   | 168      14689    469      |
  | 348      348      6        | A(289)   1        7         | 28       2489     5        |
  +---------------------------------------------------------------------------------------+
  | 1        245      457      | 3        5678     258       | 9        2467     2467     |
  | 2347     23459    457      | 1-567-9  5679     1259      | 2567     23467    8        |
  | 6        2359     8        | 4        579      259       | 257      237      1        |
  +---------------------------------------------------------------------------------------+
  | 2478     6        457      | 7-8(59) -7-8(3459) -8(3459) | 1278     12789    2379     |
  | 478      458      1        | 67-8(59)  2        -8(3459) | 678      6789     3679     |
  | 9        28       3        | 167-8     678      18       | 4        5        267      |
  +---------------------------------------------------------------------------------------+
                                    hidden als B in b8^ (r7c456,r8c46)
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Myth Jellies » Thu Dec 04, 2008 9:27 pm

ronk wrote:I recently ran across this relatively complex ALS doubly-linked xz-rule with 8 cells that yields 8 eliminations.
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      | 258      45-8    6      | 3      2478   247
 458    7      2      | 589      3459-8  3459-8 | 168    14689  469
 348    348    6      | 289      1       7      | 28     2489   5
----------------------+-------------------------+---------------------
 1      245    457    | 3       A5678   B258    | 9      2467   2467
 2347   23459  457    | 167-59  A5679   B1259   | 2567   23467  8
 6      2359   8      | 4       A579    B259    | 257    237    1
----------------------+-------------------------+---------------------
 2478   6      457    | 5789     34579-8 3459-8 | 1278   12789  2379
 478    458    1      | 56789    2       3459-8 | 678    6789   3679
 9      28     3      | 1678    A678    B18     | 4      5      267

Sets:  A = {r4569c5} = {56789}
       B = {r4569c6} = {12589}
     x,z = 5,9 and x,z = 9,5

Elims: r5c4<>59, r127c5<>8, r278c6<>8 (8 elims)

Viewed as distributed disjoint subsets (DDS), all candidates of 8 cells r4569c56 are covered by 3 sectors -- 59b5, 678c5 and 128c6.


There is an interesting locking of the eights into an x-wing there. The ALS AICs

(5&6&7&8=9)r4569c5 - (9=1&2&8&5)r4569c6 - (5=6&7&8&9)r4569c5...loop
and/or
(1&2&8&9=5)r4569c6 - (5=6&7&8&9)r4569c5 - (9=1&2&8&5)r4569c6...loop

can both be AIC representations for Ronk's double-link. Note that they attack the two columns c56 and block b5. We also have, using the same ALS cells grouped a bit differently...

(8=6|7)r9c5 - (6&7=2&5&8&9&1)r456c56 - (1=8)r9c6...loop

which attacks the eights in r9 & b8 as well as the same digits in b5

Seems like we should be able to get all of these deductions in one fell swoop, like you could if you did subset counting. Perhaps Allan has it and I just need to study his post a bit more.

I think I have it though...the fact that the 8's were just along for the ride in both of Ronk's ALS's in an AIC loop means that they have to be locked in both of those ALS's. In other words, they have to show up twice, and the only places they can show up forms an X-wing. Therefore all of the 8's deductions in c56, b58, and r49 can be made.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Fri Dec 05, 2008 1:30 am

Allan and Myth, thanks for the alternate viewpoints.

Allan Barker wrote:I think it is a doubly linked als, however, one of the two als is hidden in box 8. The logic eliminates 12 candidates. Note that cover sets 8b2 and 8c4 are redundant, both producing eliminations.

Where do you see the double link:?: It would appear to be digits 5 & 9 between set A in c4b2 and the hidden set in b8, but set A doesn't see all those digits in b8.

As to the eliminations r789c4<>8: When posting examples of the ALS [edit: doubly-linked] xz-rule, I don't try to break down the exact locations of set members. Of course, that doesn't apply to the 'x' and 'z', where all 'x' and 'z' of both sets must necessarily see each other. This occurs in b5 in this example, so the "scope of potential eliminations" is also b5.

Sets A and B are located in c5 and c6, respectively. Therefore, the scope for digits truly locked by the doubly-linked sets is also c5 and c6. IOW the middle stack might have looked like ...
Code: Select all
 .        .       B128
 .        .        .
 .        .        .
--------------------------
 .       A56789   B12589
 .       A56789   B12589
 .       A56789   B12589
--------------------------
 .        .        .
 .        .        .
 .       A678      . 

When examining the locations of set members in more detail, however, I still see these creatures as constraint sets, rather than chains. Since an exact cover -- N cover sets for N base sets -- is required for multiple eliminations, the notion of "redundant" cover sets is foreign to me. Instead, I see the union of results of using different cover sets, each of size N. For my example, for example:) ...
Code: Select all
 .        .        . 
 .        .        .
 .        .        .
--------------------------
 .       A5678    B258 
 .       A5679    B1259
 .       A579     B259 
--------------------------
 .        .        .
 .        .        .
 .       A678     B128

Base sets: (56789)r4569c5 (12589)r4569c6
Cover sets: 1) 59b5, 678c5, 128c6
            2) 59b5, 67c5, 12c6, 8b58
            3) 59b5, 67c5, 12c6, 8b5, 8r9
            4) 59b5, 67c5, 12c6, 8r4, 8b8

Myth's generalized x-wing appears in combos 2 thru 4, I think. Obviously, other combinations of cover sets exist as well.

[edit: added 'doubly-linked' qualifier in 2nd paragraph]
Last edited by ronk on Fri Dec 05, 2008 3:25 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aran » Fri Dec 05, 2008 4:23 am

ronk wrote:I recently ran across this relatively complex ALS doubly-linked xz-rule with 8 cells that yields 9 eliminations.
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      | 258      45-8    6      | 3      2478   247
 458    7      2      | 589      3459-8  3459-8 | 168    14689  469
 348    348    6      | 289      1       7      | 28     2489   5
----------------------+-------------------------+---------------------
 1      245    457    | 3       A5678   B258    | 9      2467   2467
 2347   23459  457    | 167-59  A5679   B1259   | 2567   23467  8
 6      2359   8      | 4       A579    B259    | 257    237    1
----------------------+-------------------------+---------------------
 2478   6      457    | 5789     3459-78 3459-8 | 1278   12789  2379
 478    458    1      | 56789    2       3459-8 | 678    6789   3679
 9      28     3      | 1678    A678    B18     | 4      5      267

Sets:  A = {r4569c5} = {56789}
       B = {r4569c6} = {12589}
     x,z = 5,9 and x,z = 9,5

Elims: r5c4<>59, r7c5<>78, r12c5<>8, r278c6<>8 (9 elims)

Viewed as distributed disjoint subsets (DDS), all candidates of 8 cells r4569c56 are covered by 3 sectors -- 59b5, 678c5 and 128c6.

[edit: as aran noted, added a missing r7c5<>7]


Further to the original and subsequent posts : the manner (which I presented elsewhere) of looking at these als chains (Ronk disapproving) still strikes me as a simple way of viewing the picture and of reasoning eliminations.
That is : present the almost locked sets A and B as {678 59} {59 128} where the restricted commons are in bold.
Now use this logic :
any outside candidate which locks any of 678 in A or any of 128 in B is false (because of the double RC).
This immediately eliminates the extraneous 8s in columns 5 and 6, the extraneous 7 in column 5, and will equally eliminate any candidate at a remove which brings this about.
Such as : 8r789c4.
(edit : 1r5c4 not being such a candidate)
Last edited by aran on Fri Dec 05, 2008 2:05 am, edited 1 time in total.
aran
 
Posts: 334
Joined: 02 March 2007

Postby Allan Barker » Fri Dec 05, 2008 5:25 am

Ronk wrote:Where do you see the double link ? It would appear to be digits 5 & 9 between set A in c4b2 and the hidden set in b8, but set A doesn't see all those digits in b8.

1) Yes, the double link is in 59c4.

2) OK, now I see, what I presented is a continuous nice loop of two almost-locked sets where one is hidden in b8, it is not covered by the (doubly-linked) Almost Locked Sets xz-rule.

Ronk wrote:When examining the locations of set members in more detail, however, I still see these creatures as constraint sets, rather than chains. Since an exact cover -- N cover sets for N base sets -- is required for multiple eliminations, the notion of "redundant" cover sets is foreign to me. Instead, I see the union of results of using different cover sets, each of size N. For my example, for example:) ...

My use of redundant in this case was purely ad hoc and your view is of course, correct.

Looking at your base/cover sets, I see that the union of cover sets results in a total of 13 candidate eliminations. (and see aran has already concluded the same). Further 8b5 and 8r4 are not both required to get all eliminations.

.Thumbs 13 eliminations as base/cover sets.
Image

Edit:
aran wrote:But now look at 1r5c4 : true, this forces 1r9c6 which from the above logic is false.
Hence <1>r5c4.


I spoke too fast, the 13 eliminations from the base/cover sets do not include <1>r5c4. so perhaps there are 14 eliminations.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby aran » Fri Dec 05, 2008 5:58 am

Allan I went a little too quick.
Idea good but implementation awful...1r5c4 needs to produce a 1 outside the als B, whereas alas 1r9c6 is part of the als =>1r5c4 is still in place.

Will edit earlier post for that.
PS are you considering <8>r9c2 as inherent in the elimination chain, or merely as a by-product of the pointing pair 8r9c56 resulting from earlier eliminations ?
Last edited by aran on Fri Dec 05, 2008 2:13 am, edited 1 time in total.
aran
 
Posts: 334
Joined: 02 March 2007

Next

Return to Advanced solving techniques