almost-locked-sets (ALS) for beginners

Advanced methods and approaches for solving Sudoku puzzles

almost-locked-sets (ALS) for beginners

Postby smoof » Mon Mar 06, 2006 6:29 pm

As a newbie to the world of Sudoku, I was trying to learn the technique of ALS and was really struggling. I finally figured out the basics based on this thread http://forum.enjoysudoku.com/viewtopic.php?t=2510 Bob Hanson's web page http://www.stolaf.edu/people/hansonr/sudoku/explain.htm some help from other members and a lot of head scratching while using Bob's solver. I have put together some rules and examples to show two basic forms of ALS that I understand. I hope it will be useful to other beginners like myself. Please let me know if you spot any errors so I can fix them.

The Rules
Consider two ALS, A and B.

If A and B have only one common candidate then no reduction is possible.

If A and B have two or more common candidates, a candidate x is a weak link (aka restricted common candidate) if all instances of x in ALS A can see all the instances of x in ALS B. If A and B do not have at least one weak link then no reduction is possible.

If A and B have only one weak link, then the other common candidate(s) can be eliminated from all cells (that are not cells of A or B) that can see all instances of the common candidate in both A and B.

If A and B have two weak links x and y, then x can be eliminated from any cells (that are not cells of A or B) that can see all the x candidates in both A and B. y can be eliminated from any cells (that are not cells of A or B) that can see all the y candidates in both A and B. A non-common candidate z contained in A can be eliminated from any cells (that are not cells of A or B) that contain an x and can see all the z candidates in A. A non-common candidate z contained in A can be eliminated from any cells (that are not cells of A or B) that contain a y and can see all the z candidates in A. This same rule applies to ALS B.


The Examples
Code: Select all
Example of two ALS with a single weak link


   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 | A 238 | B 689 |   269 || A 368 |     4 |     5 ||     7 |  A 23 |     1
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |   357 | B  67 |   567 ||     1 |    36 |     2 ||     9 |     8 |     4
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 |   238 |     1 |     4 ||     9 |     7 |    38 ||     5 |    23 |     6
===========================||=======================||=======================
r4 |     1 |     3 |   579 ||   567 |    69 |    67 ||     2 |     4 |     8
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 |    25 |     4 |     8 ||    25 |    13 |    13 ||     6 |     9 |     7
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 |     6 | B  79 |    29 ||   278 |    89 |     4 ||     1 |     5 |     3
===========================||=======================||=======================
r7 |    78 |   678 |    67 ||     4 |     2 |     9 ||     3 |     1 |     5
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 |     9 |     5 |     3 ||    78 |    18 |   178 ||     4 |     6 |     2
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 |     4 |     2 |     1 ||    36 |     5 |    36 ||     8 |     7 |     9
.............................................................................


A={2368} at r1c1, r1c4, r1c8
B={6789} at r1c2, r2c2, r6c2

1. The common candidates of A and B are 6 and 8.

2. A and B are weakly linked by 8 because all the 8 in A can see all the 8 in B. They can not be weakly linked by 6 because the 6 of B in r2c2 can not see the 6 of A in r1c4. This also explains why r6c2 had to be used in B instead of r7c2. If r7c2 was used, the 6 and 8 in r7c2 would not be able to see all (or any in this case) of the 6 and 8 in A.

3. The other common candidate of A and B is 6. The list of cells (that are not in A or B) that can see the 6 in all cells of both A and B is r1c3. The 6 can be removed from r1c3.



Code: Select all
Example of two ALS with two weak links.  This example is from Bob Hanson's web page (http://www.stolaf.edu/people/hansonr/sudoku/explain.htm). 


   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 |    37 |     9 |     8 ||     6 |     1 |     2 || A  37 |     4 |     5
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |     5 |     6 |     2 ||     3 |    48 |   478 || A  19 | A 178 | A 789
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 |   347 |     1 |    34 ||    78 |     5 |     9 || B 237 |  3678 |  2678
===========================||=======================||=======================
r4 |   489 |   258 |   459 ||   478 |  2348 | 34578 ||     6 |   378 |     1
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 |    48 |     3 |     6 ||  1478 |   248 |  1478 ||     5 |     9 |  2478
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 |     1 |   258 |     7 ||     9 |     6 |  3458 || B  23 |    38 |   248
===========================||=======================||=======================
r7 |  3689 |    58 |   359 ||     2 |   349 |    34 ||    19 |   167 |   679
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 |     2 |     7 |    19 ||    18 |    89 |     6 ||     4 |     5 |     3
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 |   369 |     4 |   139 ||     5 |     7 |    13 ||     8 |     2 |    69
.............................................................................



A = {13789} at r1c7, r2c7, r2c8, r2c9
B = {237} at r3c7, r6c7

1. The common candidates of A and B are 3 and 7.

2. A and B are weakly linked by 3 because all the cells of A and B that contain a 3 can see each other (col 7). A and B are weakly linked by 7 because all the cells of A and B than contain a 7 can see each other (block 3).

3. The list of all cells (not in A or B) that can see all the 3 in A and B is r45789c7. There is not a 3 in any of those cells so no reduction is possible.

4. The list of all cells (not in A or B) that can see all the 7 in A and B is r1c89, r3c89. The 7 can be removed from r3c8 and r3c9.

5. The non-common candidates of A are {189}. The list of cells (not in A or B) that can see all instances of 1 in A are r2c123456, r1c89, r3c89. Of those cells, the ones that contain a 3 or 7 are r2c6, r3c8, r3c9. None of these cells contain a 1 so no reduction is possible.

6. The list of cells (not in A or B) that can see all instances of 8 in A are r2c123456, r1c89, r3c89. Of those cells, the ones that contain a 3 or 7 are r2c6, r3c8, r3c9. 8 can be removed from r2c6, r3c8, r3c9.

7. The list of cells (not in A or B) that can see all instances of 9 in A are r2c123456, r1c89, r3c89. Of those cells, the ones that contain a 3 or 7 are r2c6, r3c8, r3c9. None of these cells contain a 9 so no reduction is possible.

8. The non-common candidate of B is 2. The list of cells (not in A or B) that can see all instances of 2 in B is r45789c2. Of those cells, none contain a 3 or 7 so no reduction is possible.
smoof
 
Posts: 5
Joined: 03 March 2006

Postby tarek » Mon Mar 06, 2006 7:59 pm

This thread should hopefully clear some of the confusion about ALS:

What you described smoof will cause some confusion on these boards, the reasons:

As most of our examples regarding benny's ALS xz rule (2 ALS with 1 restricted candidate [link]), & the ALS xy rule (3 ALSs, 2 of which share a restricted candidate [link] with the 3rd).......

Having 2 links now & still having the x, y, z on top of that is causing me a headache already.........

Tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Re: almost-locked-sets (ALS) for beginners

Postby aeb » Mon Mar 06, 2006 10:49 pm

smoof wrote:
Code: Select all
Example of two ALS with a single weak link

 A 238 B 689   269 | A 368     4     5 |     7  A 23     1
   357 B  67   567 |     1    36     2 |     9     8     4
   238     1     4 |     9     7    38 |     5    23     6
-------------------+-------------------+------------------
     1     3   579 |   567    69    67 |     2     4     8
    25     4     8 |    25    13    13 |     6     9     7
     6 B  79    29 |   278    89     4 |     1     5     3
-------------------+-------------------+------------------
    78   678    67 |     4     2     9 |     3     1     5
     9     5     3 |    78    18   178 |     4     6     2
     4     2     1 |    36     5    36 |     8     7     9


A={2368} at r1c1, r1c4, r1c8
B={6789} at r1c2, r2c2, r6c2

Let me try to understand this my way. Look at the set C of size 6 containing r1c1, r1c4, r1c8, r1c2, r2c2, r6c2. The candidate digits here are 236789, with maximal multiplicities 112111 (digit 6 can occur twice, the other digits at most once), for a total of 7. Any choice outside that wipes out two candidates can be eliminated.
But (1,3)6 does eliminate all digits 6 from C, impossible. So (1,3)!6.

smoof wrote:
Code: Select all
Example of two ALS with two weak links.

    37     9     8 |     6     1     2 | A  37     4     5
     5     6     2 |     3    48   478 | A  19 A 178 A 789
   347     1    34 |    78     5     9 | B 237  3678  2678
-------------------+-------------------+------------------
   489   258   459 |   478  2348 34578 |     6   378     1
    48     3     6 |  1478   248  1478 |     5     9  2478
     1   258     7 |     9     6  3458 | B  23    38   248
-------------------+-------------------+------------------
  3689    58   359 |     2   349    34 |    19   167   679
     2     7    19 |    18    89     6 |     4     5     3
   369     4   139 |     5     7    13 |     8     2    69
 

A = {13789} at r1c7, r2c7, r2c8, r2c9
B = {237} at r3c7, r6c7

Look at the set C of size 6 containing r1c7, r2c7, r2c8, r2c9, r3c7, r6c7. The candidate digits here are 123789 with maximal multiplicities 111111, for a total of 6. Any choice outside that wipes out one candidate can be eliminated.
In particular, (2,6)!8, (3,8)!7, (3,8)!8, (3,9)!7, (3,9)!8.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby ronk » Mon Mar 06, 2006 10:50 pm

tarek wrote:Having 2 links now & still having the x, y, z on top of that is causing me a headache already.........

Since it's a variant of the xz-rule, I think it would be helpful to only use placeholders x and z, and instead of y, add a and b to represent the extra candidates in sets A and B, respectively. Modifying Bob Hanson's diagram a little ...
Code: Select all
ALS xz-rule for doubly-weakly-linked sets
                x*
               . .
              .   .
             x.....x
            /       \
*a....a----A          B----b....b*
            \       /
             z.....z
              .   .
               . .
                z*

In other words, both x and z are common restricted candidates. Extra candidates 'a' belong to set A, and extra candidates b belong to set B. I think any or all of the digits in 'a' may be the same as digits in b.

The '/' and '\' and '-' indicate the association of the candidates within the sets (strong nodes). The '.....' indicates weak links. The x*, z*, a*, and b* are the possible eliminations. The triangulated weak links for x* and z* indicates elimination candidates must see ALL of x and z, respectively, in both sets.

Note that if both 'a' and b are null (empty), then this xz-rule variant has degenerated into the simple naked pair.

[edit: For comparison purposes, here is a singly-weakly-linked diagram:
Code: Select all
ALS xz-rule for singly-weakly-linked sets
             x........x
            /          \
      a----A             B----b     
            \          /
             z...z*...z

The difference in potential eliminations is considerable. However, that's likely offset by a considerable difference in the number of occurrences.]

Ron
Last edited by ronk on Tue Mar 07, 2006 9:34 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Tue Mar 07, 2006 11:18 am

Bob Hansons example is not the best for ALS:
You have a conjugated pair of 7 in box 3/column 7, which already kills the 7 in r23c89.
The triple 189 then in r2c789 kills the 8 in r2c56, and the x-wing in 7 in r13c17 the 7 in r3c4.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Tue Mar 07, 2006 12:45 pm

ravel wrote:Bob Hansons example is not the best for ALS:
You have a conjugated pair of 7 in box 3/column 7, which already kills the 7 in r23c89.
The triple 189 then in r2c789 kills the 8 in r2c56, and the x-wing in 7 in r13c17 the 7 in r3c4.

It's certainly possible that a doubly-weakly-linked example of the xz-rule doesn't survive the application of "basic techniques". If that's the case, we could simply 'fuggedaboutit'.:) But I believe "valid" examples exist.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Tue Mar 07, 2006 1:09 pm

ronk wrote:...
Code: Select all
                x*
               . .
              .   .
             x.....x
            /       \
*a....a----A          B----b....b*
            \       /
             z.....z
              .   .
               . .
                z*


This is a fantastic diagram..... I still remember those from the ALS thread, however your FISH diagram -to me- still stands out:D

Tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ronk » Tue Mar 07, 2006 1:41 pm

tarek wrote:This is a fantastic diagram..... I still remember those from the ALS thread

Thanks. For comparison purposes, I added a diagram for for singly-weakly-linked ALS xz-rule to that post.

tarek wrote:however your FISH diagram -to me- still stands out:D

:DI had forgotten about that.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Wed Mar 08, 2006 12:12 pm

ravel wrote:Bob Hansons example is not the best for ALS

This one is better:
Code: Select all
 189  B129   3     | 4     125   259   | 6     7     2589
 5    B1269 -12689 | 189   1267  2679  | 3     4     289
 7     4    A26    | 89    2356  2356  | 189   189   25
-------------------+-------------------+------------------
 6    -1259  12459 | 3     1258  2459  | 2589  289   7
 139   8     7     | 19    1256  2569  | 259   36    4
 349  -2359  2459  | 7     2568  24569 | 2589  36    1
-------------------+-------------------+------------------
 2    B19    1489  | 6     37    37    | 1489  5     89
 134  -13567 1456  | 25    9     8     | 1247  12    36
 389  -35679 5689  | 25    4     1     | 2789  289   36

 Set A = {r3c3} = {26}
 Set B = {r1c2,r2c2,r7c2} = {1269}
     x = 2
     z = 6

 Excepting the sets: 26 may be eliminated from b1 and 19 from c2, i.e.,

 r2c3<>2, r2c3<>6, r4c2<>1, r4c2<>9, r6c2<>9, r8c2<>1 and r9c2<>9
[edit: '-' elimination markers added to grid]

The starting grid for #65 of the top1465 is:
..3...67.5.....3...4.......6..3......8......4...7....12......5.....98.......41...

Ron

P.S. Sets A and B may also be viewed as a 'Sue De Coq'.
Last edited by ronk on Wed Mar 08, 2006 11:49 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Wed Mar 08, 2006 12:53 pm

ronk wrote:P.S. Sets A and B may also be viewed as a 'Sue De Coq'.


& a nice generalized WXYZ wing.........

Tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ronk » Wed Mar 08, 2006 1:22 pm

tarek wrote:& a nice generalized WXYZ wing.........

True, but why "generalized"? Since it has a 4-candidate "pilot cell", it looks like a special case of a classical wxyz-wing to me.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aeb » Wed Mar 08, 2006 9:29 pm

ronk wrote:
Code: Select all
 189  B129   3     | 4     125   259   | 6     7     2589
 5    B1269 -12689 | 189   1267  2679  | 3     4     289
 7     4    A26    | 89    2356  2356  | 189   189   25
-------------------+-------------------+------------------
 6    -1259  12459 | 3     1258  2459  | 2589  289   7
 139   8     7     | 19    1256  2569  | 259   36    4
 349  -2359  2459  | 7     2568  24569 | 2589  36    1
-------------------+-------------------+------------------
 2    B19    1489  | 6     37    37    | 1489  5     89
 134  -13567 1456  | 25    9     8     | 1247  12    36
 389  -35679 5689  | 25    4     1     | 2789  289   36

 Set A = {r3c3} = {26}
 Set B = {r1c2,r2c2,r7c2} = {1269}
     x = 2
     z = 6

 Excepting the sets: 26 may be eliminated from b1 and 19 from c2, i.e.,

 r2c3<>2, r2c3<>6, r4c2<>1, r4c2<>9, r6c2<>9, r8c2<>1 and r9c2<>9

P.S. Sets A and B may also be viewed as a 'Sue De Coq'.

And the version without separate sets A and B and special points x and z:
Consider the set of size 4 containing r3c3,r1c2,r2c2,r7c2. The digits that can occur there are 1269 with max multiplicities 1111, so this is a locked set, and any choice that would remove one of these digits from the set is wrong and can be eliminated.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby ronk » Wed Mar 08, 2006 9:35 pm

aeb wrote:Consider the set of size 4 containing r3c3,r1c2,r2c2,r7c2.

http://forum.enjoysudoku.com/viewtopic.php?p=22381#p22381
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Thu Mar 09, 2006 12:17 am

ronk wrote:a special case of a classical wxyz-wing to me.

You're right, it has a four cell pilot & more than one cell has an x

Tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ronk » Thu Mar 09, 2006 11:55 am

tarek wrote:a nice generalized WXYZ wing.........

An ALS xz-rule for doubly-weakly-linked sets that might be referred to as a "generalized" VWXYZ wing.
Code: Select all
 5     3     178  | 168   2    167  |  9     14678  B146   
 678   2     4    | 1689  3    1679 |  67    5      B16     
 678   168   9    | 1568  4    1567 |  23    1678    23     
------------------+-----------------+----------------------
 69    69    35   | 35    1    4    |  8     2       7     
 2348  1458  1358 | 7     6    235  | A35    9      B345   
 2347  45    357  | 235   9    8    |  1     46     B3456   
------------------+-----------------+----------------------
 49    49    358  | 123   78   123  |  2567  167    -1256   
 38    58    6    | 4     78   123  |  257   17      9     
 1     7     2    | 69    5    69   |  4     3       8     

 Set A = {r5c7} = {35}
 Set B = {r1c9,r2c9,r5c9,r6c9} = {13456}
    xz = 46

 r7c9<>1 is the lone elimination

Note the absence of a VWXYZ pilot cell. The starting grid for this (#207 of the top1465) is:
53..2.9...24.3..5...9..........1.827...7.........981.............64....91.2.5.43.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques