ALS and its complement, the weak ALS

Advanced methods and approaches for solving Sudoku puzzles

ALS and its complement, the weak ALS

Postby Myth Jellies » Sat Sep 16, 2006 7:46 am

ALS and its complement, the weak ALS

First some background stuff. The typical ALS is defined as a set of N cells containing N+1 digits, where all N cells are part of the same house.

Say we have four cells, labeled set A, which contain a total of five different digits, a, b, c, d, and e. It is easy to see that if one digit was taken away from the set, then the remaining four digits would be locked in the set of four cells. Thus you can say that either a particular digit is part of the set, or all the remaining digits are locked in the set. This is a strong inference relationship. Actually it is a conjugate relationship because it is also true that if four digits are locked in the set, then the leftover digit cannot be part of the set.

Thus, we can always write (using AIC notation)...

a[set A] = (b&c&d&e)[set A] ('=' means strong relationship)

as well as...

a[set A] - (b&c&d&e)[set A] ('-' means weak relationship)

The strong inference relationship is very useful for AICs and Nice Loops. The chain can continue on using any one of the and'ed digits.

Here is a fanciful hypothetical example
Code: Select all
| B1234567   B234567    B234567   |A12   *    *  | *    *    *  |
| B234567    B234567    B234567   | *    *    *  | *    *    *  |
| C123456789 C123456789 C12345678 |D2*  D2*  D2* | **   **   ** |


Assume * can be anything, but ** can be anything except a 2

Noting the ALS in set B, we can make the following AIC / Nice Loop

in various notations
2['A'] = 1['A'] - 1['B'] = (3&4&5&6&7&2)['B'] - 2['C'] = 2['D']...
r1c4 -1- r1c1 =1|2= r12c123 -2- r3c123 =2= r3c456 -2- r1c4...
(2=1)r1c4 - (1=3&4&5&6&7&2)r12c123 - (2)r3c123 = (2)r3c456...

This is an AIC loop, or a closed continuous nice loop. Therefore all links in the loop can be converted into conjugate links, so you can remove all 2's in box 2 that are not part of A or D for example.

But, sometimes, it is hard to see these ALS's, especially the big ones. It can also be hard to tell if they are useful. Also there is another deduction available in this loop, namely all the 3's, 4's, 5's, 6's, and 7's, can be removed from set C which can easily be missed with this approach unless you invoke some slippery linking logic.

Enter the Weak ALS

It turns out that every ALS has a complementary Weak ALS which obeys the following rule...

The Weak ALS is defined as a set of N' cells containing N'-1 locked digits (digits that cannot be found elsewhere in the house outside of the set.) For a complementary weak ALS,

N' = 9 - number of solved cells in house - N (number of cells in the ALS)

The N' complementary Weak ALS cells are just the remaining unsolved cells in the house that are not part of the ALS. The locked digits in the complementary Weak ALS are the unsolved digits which do not appear in the ALS. In the example above, the ALS is set B and its complementary Weak ALS is set C with locked digits 8 and 9.

The Weak ALS has one very useful property. Because of the locked digits, every non-locked digit candidate in the set excludes (is weakly linked to) every other non-locked digit candidate.

Thus, instead of using the ALS in our loop, we can use the Weak ALS
Code: Select all
| B1234567    234567     234567   |A12   *    *  | *    *    *  |
|  234567     234567     234567   | *    *    *  | *    *    *  |
| C123456789 C123456789 C12345678 |D2*  D2*  D2* | **   **   ** |


2['A'] = 1['A'] - 1['B'] = (1&8&9)['C'] - (8&9&2)['C'] = 2['D']...
or
(2=1)r1c4 - (1)r1c1 = ((1&8&9)-(8&9&2))r3c123 = (2)r3c456...

In the notation here, I have and'ed the non-locked digits with the locked ones so that you can one can understand better why the weak link is valid.

Now in these cases, when the loop converts the weak links to conjugate links, it becomes very obvious that the Weak ALS, set C, can only contain the digits 1289.

Other than as an alternate way of working with & finding ALS's, I'm not sure if anything new can come out of this. Still, even if it only is an alternate view, sometimes that helps you see things you might otherwise miss.

Any single unsolved cell, which is not a naked or hidden single, satisfies the requirement for a Weak ALS (1 cell & 0 locked digits), therefore if you make a set by excluding 1 unsolved cell from a house, that set is an ALS.

For a final thought, the smallest ALS is a bivalue cell. Noting that the non-locked digits in the Weak ALS are equal to the digits in its complementary ALS, imagine if you will a sprinkling of small ALS's sharing a group with a couple multi-digit cells. The Weak ALS links mean pairings of non-locked digits in those cells inhibit each other...can anyone say APE (aligned pair exclusions)? APE could really be thought of as a multi-threaded forcing net involving multiple Weak ALS links.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby daj95376 » Sat Sep 16, 2006 3:56 pm

Myth Jellies, please forgive me for interrupting your topic, but I have a question. Your definition for an ALS matches others that I've read, but it bothers me. Consider the following four cells and their five candidates: 12 13 23 45. It meets your typical definition of an ALS. Is it an ALS?

I keep thinking that the definition of an ALS should be: an n-tuple with one extra candidate. You don't even need to add the caveat restricting it to one house because an n-tuple is restricted to one house by definition!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Sat Sep 16, 2006 4:29 pm

daj95376 wrote:Consider the following four cells and their five candidates: 12 13 23 45. It meets your typical definition of an ALS. Is it an ALS?

Although your example fits the definition, an ALS containing a naked n-tuple as a subset is not useful AFAIK.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Sat Sep 16, 2006 6:53 pm

12 13 23 45

is both an ALS (N + 1 digits in N cells)

and a Weak ALS (N - 1 locked digits in N cells)

and is worthless in either case.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Mike Barker » Sun Sep 17, 2006 1:14 am

Very interesting although I would have written the nice loop as:
Code: Select all
r1c4-1-ALS:r12c123-2-GSL:r3c123=2=r3c456-2-r1c4

This allows eliminations of 1 in r1c56789 and 2 in the * cells of box 2. In addition, because this is a continuous nice loop, the mutual exclusion rule applies. This means that a candidate which is not one of the link labels (equivalent to the doubly restricted common) can be deleted from any cell which can see all of the cells of the ALS which contain the candidate. Thus 34567 can be eliminated from r3c123. This doesn't invalidate the weak ALS. Its just not needed here.
Mike Barker
 
Posts: 458
Joined: 22 January 2006


Return to Advanced solving techniques

cron