ALS's in AIC's and the use of ALS subsets

Advanced methods and approaches for solving Sudoku puzzles

ALS's in AIC's and the use of ALS subsets

Postby Myth Jellies » Wed May 03, 2006 7:00 am

Alternating Inference Chains, Almost Locked Sets, and Almost Locked Subsets

This is a continuation of work started by Carcul, Bennys, Jeff, Ronk, and others. It turns out that Alternating Inference Chains (AICs) and Almost Locked Sets (ALS) work together in a harmonious and intuitive fashion (IMO). Most ALS can be described as a candidate premise which looks something like...

- Sa = S(b & c & ...) -

...Here, the '=' represents a strong inference, and the '-' represent a weak inference. The 'S' denotes the set of cells which make up an ALS. If digit 'a' is false in the ALS cells, then all of the remaining digits must be true in S. Also, if not all of the non-'a' digits are true in the ALS, then 'a' must be true. The relationship is actually a conjugate one. One could also form a weak link between 'a' and the remainder of the digits in S, but that does not tend to be as useful. Here is a real life example...

Code: Select all
 *--------------------------------------------------------------------*
 | 2379   6      49     | 5      28     48     | 3789   1      389    |
 | 259    179    159    | 3      1268   168    | 589    79     4      |
 | 35     14     8      | 7      9      14     | 2      356    356    |
 |----------------------+----------------------+----------------------|
 | 4     A139    7      | 2      1568  -1368   | 359    3569   3569   |
 |A69     5     A169    | 146    7     B36     | 349    8      2      |
 | 8      23     26     | 46     56     9      | 1      3456   7      |
 |----------------------+----------------------+----------------------|
 | 59     79     3      | 18     4      2      | 6      579    18     |
 | 1      249    24569  | 689    36     7      | 34589  3459   3589   |
 | 679    8      469    | 169    136    5      | 3479   2      139    |
 *--------------------------------------------------------------------*

A3=A(1&6&9)-B6=B3; => all cells which see all A3's and B3 cannot be 3

If you look at the weak inference between the sixes, you see that we can form one because the six in B can see all of the sixes in A. In general, this is the rule. If you want to form a weak link between an outside candidate and an ALS candidate, the outside candidate needs to "see" every instance of that ALS candidate in the ALS. If the cells marked with 'A' are your ALS cells...
Code: Select all
 |----------------------+----------------------+----------------------|
 | 59     79     3      | 18     4      2      | 6      579    18     |
 | 1      249    24569  |A689   A36     7      |A34589 A3459  A3589   |
 | 679    8      469    | 169    136    5      | 3479   2      139    |
 *--------------------------------------------------------------------*

...then you can obviously form weak links with all the ALS digits (345689) along the middle row. You can also form a weak link with 6's in the middle box, and weak links with 4 or 5 in the right box.

Exceptions to the general weak link rule: ALS Subsets in AIC's

Now, back in the day, when I used to play with the Pattern Overlay Method, I found that I got a huge number of good deduction equations when I had a series of cells in a group which looked something like this....
Code: Select all
 | ab     bc     bcd    | bcde   bcdef  .      | .      .      .      |

...Until recently, I hadn't ever really noted another advanced method that could make the same reductions that I could with POM on this structure. Then I combined AICs with ALSs and noted the following...
Code: Select all
 | ab'    bc'    bcd'   | bcde'  bcdef' .      | .      .      .      |

AICs:
a=b'              => a and/or b' is true
a=b'-b=c'         => a and/or c' is true
a=b'-(b&c)=d'     => a and/or d' is true
a=b'-(b&c&d)=e'   => a and/or e' is true
a=b'-(b&c&d&e)=f' => a and/or f' is true

Take these inferences altogether, and you can form and use the following strong inference...

a=(b'&c'&d'&e'&f')

Now, I don't need to limit my weak links to the ALS via digit d to that row. I can use any d which "sees" d' as a weak link to the ALS. So, if I have the following...
Code: Select all
 | ab'    bc'    bcd'   | bcde'  bcdef' .      | .      .      .      |
 |----------------------+----------------------+----------------------|
 | .      .      dg     | .      fg     .      | .      .      .      |

I then have the AIC...
a=(b'&c'&d'&e'&f')-d=g-g=f-(b'&c'&d'&e'&f')=a
...which proves 'a' is true. Or if you'd rather, you have...
d'-d=g-g=f-f'
...and since the d and/or f is true, then the premise (d'&f') must be false, which also proves 'a' is true.

Another possibility might be...
Code: Select all
 | ab'    bc'    bcd'   | bcde'  bcdef' .      | .      .      .      |
 |----------------------+----------------------+----------------------|
 | aX     .      .      | ae     .      .      | .      .      .      |

...which has the AIC: a=(b'&c'&d'&e'&f')-e=a, eliminating the 'a' in the aX-cell.

Exceptions to the general weak link rule: ALS Subsets in AIC's

I mentioned ALS subsets above, but haven't defined them. ALS Subsets are a shortcut to seeing the combined strong inferences without forming all of the AIC's and then combining them together. You form a subset by eliminating one digit from the ALS candidates and then see if you have any naked singles or sets that you can isolate. You can then remove those digits and continue until there are no more revealed singles or sets. For example, if you are coming into the following ALS via some weak candidate 'a' link...
Code: Select all
 | abc    bc     abcg   | bcdef  bcdef  .      | abceg  .      .      |

...you can take away the 'a's from your ALS, leaving...
Code: Select all
 | bc     bc     bcg    | bcdef  bcdef  .      | bceg   .      .      |

...the naked bc pair eliminates all other 'b's and 'c's...
Code: Select all
 | bc     bc     g      | def    def    .      | eg     .      .      |

...the single 'g' and then the single 'e', and we are left with the relevent digits in this ALS...
Code: Select all
 | bc     bc     g      | df     df     .      | e      .      .      |

...putting primes on the relevent digits, we finally have...
Code: Select all
 | ab'c'  b'c'   abcg'  | bcd'ef' bcd'ef' .      | abce'g .      .      |

...thus, the AIC can continue ...a-a=(b'&c'&d'&e'&f'&g'), and the primed candidates are the only ones we have to consider in our further weak links with the ALS.

Don't have any real world examples of this yet, but I will keep my eyes open.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Thu May 25, 2006 8:10 am

Here is a theoretical problem based on one posed by r.e.s. in a post from awhile back. Given the following snippet...
Code: Select all
           |
      A23  | B24
      D35  | C45
-----------+----------

Most folk familiar with chains and loops will see something like the following loop...
Code: Select all
A3=A2-B2=B4-C4=C5-D5=D3-A3

...and deduce that these cells can contain the only 2's in the AB row, the only 3's in the AD column and box, the only 4's in the BC column and box, and the only 5's in the CD row.

Now when this setup is modified slightly...
Code: Select all
            |
      A2'3' | A234
      C35   | B45
------------+----------

Those familiar with using ALS's in chains will probably note something like the following...
Code: Select all
A(2&3)=A4-B4=B5-C5=C3

...from which you can deduce that no cell which sees all the 3's in A and C can be a 3. But this is only part of what you can do. The ALS in the A cells can be split into a strong link in three different ways...
A(2&3)=A4,
A(2'&4)=A3, and
A(3'&4)=A2.
Note that in these other two cases, ALS subsets apply, and, where indicated, only the ticked digits need to be included in the strong link. From the second strong link we can create the following chain...
Code: Select all
A3=A(2'&4)-B4=B5-C5=C3

...but, aside from giving us extra chaining options off of 2', this gives us no new reductions here. However, if we use the final link, we can create the following...
Code: Select all
A2=A(3'&4)-B4=B5-C5=C3-A(3'&4)=A2

...This is a long-winded way of showing that A must contain 2, thus 2's can be eliminated from any cell seeing all the 2's in A. (I call it long-winded because you can shave off the ends of this chain and come up with the same deduction. The longer chain was given because I think it shows the deduction more clearly.)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Sat May 27, 2006 5:53 pm

AIC candidate premises can involve cells that span multiple houses as long as you are careful. Take the following hypothetical snippet...
Code: Select all
 *--------------------------------------------------------------------*
 | .      .      .      | .     D12347  .      | .     A37'    .      |
 | .      .      .      |C125    .      .      | .      .      .      |
 | .      .      .      |C125    .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .     C345    .      | .      .      .      |
 | .      .      .      | .     C345    .      | .      .      .      |
 | .      .      .      |B56     .      .      | .     A367    .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
*--------------------------------------------------------------------*

A3 = A(6&7') - B6 = B5 - C5 = C(1&2&3&4) - D(1234) = D7 - A(6&7') = A3
Thus we show that the A cells must contain 3 (or cannot be 6&7), therefore we can remove all other 3's from that column.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Sat May 27, 2006 9:45 pm

Is D -- a single cell with 5 candidates -- an AAAALS (almost-almost-almost-almost-locked set)?:D

Considering sets B, C, and D as one ALS would be more in keeping with your thread title.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Sat May 27, 2006 11:51 pm

ronk wrote:Is D -- a single cell with 5 candidates -- an AAAALS (almost-almost-almost-almost-locked set)?:D


Should I have gone for the gold?:)
Code: Select all
 *--------------------------------------------------------------------*
 | .      .      .      |C1256  D12346789 .    | .     A37'    .      |
 | .      .      .      |C1256   .      .      | .      .      .      |
 | .      .      .      |C1256   .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .     C345    .      | .      .      .      |
 | .      .      .      | .     C345    .      | .      .      .      |
 | .      .      .      |B56     .      .      | .     A367    .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .     C3489   .      | .      .      .      |
 | .      .      .      | .     C3489   .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 *--------------------------------------------------------------------*

ronk wrote:Considering sets B, C, and D as one ALS would be more in keeping with your thread title.


The weak links between B - C - D are fairly straightforward. I'm not so sure if you lump them together that it is that obvious that at least one of r1c5=7 or r6c4=6 must be true. Coming up with some rules for identifying ALS's that cannot be encompassed by a single house might be fruitful though. My question back would be what enables us to consider the original combined BCD as a single ALS of 7 candidates in 6 cells not all in one house?
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Mon May 29, 2006 12:08 pm

Myth Jellies wrote:The weak links between B - C - D are fairly straightforward. I'm not so sure if you lump them together that it is that obvious that at least one of r1c5=7 or r6c4=6 must be true.

I was subtly suggesting that your set C be treated as two sets (E and F below), not that the deduction would be found any differently. Once found, however, it makes more sense to combine BDEF instead of EF, primairly because there's only one in-link and one out-link.
Code: Select all
            5-E-12   
           /      \   
       -6-B        D-7-
           \      /   
            5-F-34   
The diagram is only valid when read left-to-right. IOW while "if B<>6, then D=7" is true, the converse is not.

Myth Jellies wrote:Coming up with some rules for identifying ALS's that cannot be encompassed by a single house might be fruitful though.

I think one in-link and one out-link would be a place to start, but suspect you mean finding multi-house ALSs.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Wed May 31, 2006 5:00 am

ronk wrote:...I was subtly suggesting that your set C be treated as two sets (E and F below)...


As you pointed out, splitting C down to E and F results in something that is not bi-directional. C is bi-directional, forms a single-threaded chain as opposed to a net, and has weak linkages that are reasonably simple to follow. If you manage to make an AIC loop, weak links can fuel reductions. Here is a hypothetical example using the simplest two-house ALS...

Code: Select all
 *--------------------------------------------------------------------*
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      |A14    B13     .      | .      .      .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      |B12    C235    .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      |E46    D56     .      | .      .      .      |
 *--------------------------------------------------------------------*

A4 = A1 - B1 = B(2&3) - C(23) = C5 - D5 = D6 - E6 = E4 (- A4)

The loop is closed, so one side or the other of each weak link must be true, therefore r12c4 <> 1, c5 has no other 5's, r9 & b8 has no other 6's, and c4 has no other 4's. You could miss the reduction on the 1's if you combine A, B, and C.

Two-House ALS's
The most simple and straightforward two-house ALS's useful for chains seem to have the following qualities.
    N+1 digits in N cells.
    Only one of the digits has a possible multiplicity = 2 (i.e. could be placed in both houses
    There is at least one cell which sees all of the ALS and another cell which sees all cases of the potentially doubled digit

Simplest examples (in all cases below, X & Y represent any random digits, and B denotes cells that are part of the two-house ALS, and 1 is the digit that can occupy both houses)
Code: Select all
 *--------------------------------------------------------------------*
 |A1X     .      .      | .     B12     .      | .      .      .      |
 | .      .     B13     |C23Y    .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+

AX = A1 - B1 = B(2&3) - C(23) = CY
Code: Select all
 *--------------------------------------------------------------------*
 |A1X     .      .      | .     B12     .      | .      .      .      |
 |B134    .     B134    |C234Y   .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+

AX = A1 - B1 = B(2&3&4) - C(234) = CY

Here is one in row and column...
Code: Select all
 *--------------------------------------------------------------------*
 |A1X     .      .      | .     B123    .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .     B23     .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .      .      .      | .      .      .      |
 |B145    .      .      | .     C2345Y  .      |B45     .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 *--------------------------------------------------------------------*

AX = A1 - B1 = B(2&3&4&5) - C(2345) = CY

Of course, if you get more elaborate with your A set, you can have more than one digit that can occupy both houses.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Wed May 31, 2006 2:35 pm

Myth Jellies wrote:As you pointed out, splitting C down to E and F results in something that is not bi-directional. C is bi-directional ...
(...)
You could miss the reduction on the 1's if you combine A, B, and C.

I see both points.

Simplest examples (in all cases below, X & Y represent any random digits, and B denotes cells that are part of the two-house ALS, and 1 is the digit that can occupy both houses) ...

I think X & Y may each represent one or more random digits and X may equal Y.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Thu Jun 01, 2006 3:05 am

Here is a subset example I happened to come across. It doesn't do much, and there are many easier & more useful chains, but it's out there.
Code: Select all
 *--------------------------------------------------------------------*
 | 689    3689   389    | 146    1346   7      | 2      5      14689  |
 | 679    1     D29     | 5      8     C24     | 4679  B46     3      |
 | 5      23678  4      | 126   -1236   9      | 67    A168   A168    |
 |----------------------+----------------------+----------------------|
 | 468    468    7      |G1248' G1'24   3      | 5      9      26     |
 | 3      4689  E89     |F248    5     F248    | 1      26     7      |
 | 2      5      1      | 9      7      6      | 34     348    48     |
 |----------------------+----------------------+----------------------|
 | 479    2479   6      | 3      249    124    | 8      124    5      |
 | 489    23489  23589  | 2468   2469   12458  | 3469   7      12469  |
 | 1      23489  23589  | 7      2469   2458   | 3469   2346   2469   |
 *--------------------------------------------------------------------*

A1 = A(6&8) - B6 = B4 - C4 = C2 - D2 = D9 - E9 = E8 - F8 = F(2&4) - G(2or4) = G(1'&8'); => r3c5 <> 1;
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Thu Jun 01, 2006 3:43 am

ronk wrote:
Simplest examples (in all cases below, X & Y represent any random digits, and B denotes cells that are part of the two-house ALS, and 1 is the digit that can occupy both houses) ...

I think X & Y may each represent one or more random digits and X may equal Y.


That's what I was trying to say, but you've stated it much better. I'll edit that eventually.

One of the marginally worrisome things is that Y can actually equal nothing.

Code: Select all
 *--------------------------------------------------------------------*
 |A1X     .      .      | .     B123    .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .     B23     .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+
 | .      .      .      | .      .      .      | .      .      .      |
 |B145    .      .      | .     C2345   .      |B45     .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 *--------------------------------------------------------------------*

In this "Y = nothing" case you can use subset counting on the cells marked with B and C. B&C have 5 digits in 5 cells, 12345, with respective multiplicities of 21111. Thus any placement which eliminates both instances of the 1's must be invalid, so you can eliminate 1 from A without using the chain.

Here is a hypothetical two-house ALS example which has 2 digits with double multiplicity. Note that now B has N+2 different digits in N cells.
Code: Select all
 *--------------------------------------------------------------------*
 |A12X   A12X    .      | .     B1234  B1234   | .      .      .      |
 | .      .      .      | .      .      .      | .      .      .      |
 |B1256   B1256  .      |C3456Y  .      .      | .      .      .      |
 +----------------------+----------------------+----------------------+

AX = A(1&2) - B(12) = B(3&4&5&6) - C(3456) = CY
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: ALS's in AIC's and the use of ALS subsets

Postby Myth Jellies » Thu Jun 15, 2006 9:38 am

Myth Jellies wrote:Don't have any real world examples of this yet, but I will keep my eyes open.


Well, now I do. These techniques were used in solving M. Mepham's unsolveable #14
Myth Jellies
 
Posts: 593
Joined: 19 September 2005


Return to Advanced solving techniques