Questions about ALS’s and overlapping cells

Advanced methods and approaches for solving Sudoku puzzles

Questions about ALS’s and overlapping cells

Postby Sudtyro » Mon Sep 03, 2007 9:46 pm

Need help with some nagging questions about how to properly handle ALS’s and certain types of overlapping cells...

The example grid position shown below was derived from the Sudocue Nightmare for 5/20/07.
The elimination of interest is r4c4 <> 7.
Code: Select all
----------------------------------------------------
28    2378  2348 | 1     9     457 | 235   2345 6     
126   236   2346 | CD25  C234  8   | 9     7    A145   
129   2379  5    | C247  C234  6   | 123   8    A14     
-----------------+-----------------+----------------
5     26    126  | 47    16   3    | 8     9    A47     
3     689   168  | 4789  5    479  | 167   146  2   
89    4     7    | 289   16   29   | 156   156  3       
-----------------+-----------------+----------------
27    1     23   | 6     28   59   | 4     235  789       
267   5     9    | 3     248  24   | 1267  126  178     
4     2368  2368 | BD59  7    1    | 236   236  A59     
----------------------------------------------------

Define the following ALS’s:
ALS A: (14579)r2349c9
ALS B: (59)r9c4
ALS C: (23457)r23c45
ALS D: (259)r29c4 (add cell r2c4 to ALS B)

Form a (conventional) grouped AIC using ALS’s A,B, and C:
(7=1459)r2349c9 – (9=5)r9c4 – (5=2347)r23c45 => r4c4 <> 7,
which is equivalent to an ALS-XY-Wing rule move.

Now, the confusion (for me) arises when one replaces ALS B with ALS D to form the new AIC,
(7=1459)r2349c9 – (9=52)r29c4 – (5=2347)r23c45.
At first look, this new chain would appear to imply the same elimination as before (r4c4 <> 7). However, ALS D and C share a common cell (r2c4), although two different (and single-occurrence) digits, 2 and 5, form the weak link between them.
Question 1: So, is this a properly linked AIC (and deduction)?

Going a step further, one can also simply switch the positions of digits 2 and 5 in ALS D to form another new AIC,
(7=1459)r2349c9 – (9=25)r29c4 – (5=2347)r23c45.
Again, ALS D and C share the common cell, r2c4, but now the weakly linking digit (5) appears more like a true “restricted common” between ALS D and C. However, it has also been stated in this forum that overlapping ALS cells cannot contain a restricted common of the two sets, in which case the above AIC is then incorrect.
Question 2: So, is this AIC improperly linked between ALS D and C because digit 5 is a restricted common?

-------------------------------------------------------------

One other unrelated elimination of interest is r1c2 <> 2.
Code: Select all
----------------------------------------------------
G28   F2378  2348 | 1    9    457 | 235   2345 6     
126   EF236  2346 | 25   234  8   | 9     7    145   
129   2379   5    | 247  234  6   | 123   8    14     
------------------+---------------+----------------
5     EF26   126  | 47   16   3   | 8     9    47     
3     EF689  168  | 4789 5    479 | 167   146  2   
G89   4      7    | 289  16   29  | 156   156  3       
------------------+---------------+----------------
27    1      23   | 6    28   59  | 4     235  789       
267   5      9    | 3    248  24  | 1267  126  178     
4     EF2368 2368 | 59   7    1   | 236   236  59     
----------------------------------------------------

Define the following ALS’s:
ALS E: (23689)r2459c2
ALS F: (236789)r12459c2 (add cell r1c2 to ALS E)
ALS G: (289)r16c1

Form a grouped AIC using ALS’s E and G:
(2=3689)r2459c2 - (9=82)r16c1 => r1c2 <> 2 (also r3c2 <> 2).
which is equivalent to an ALS-XZ rule move.

Now, confusion again arises when one replaces ALS E with ALS F to form the new AIC,
(7=23689)r12459c2 - (9=82)r16c1.
This new chain clearly shows a strong-inference link between (single-occurrence) (7)r1c2 and (2)r1c1, which, in turn, seems to imply the desired elimination (r1c2 <> 2). However, the candidate-elimination cell, r1c2, is actually a part of (i.e., overlaps) ALS F.
Question 3: The chain is certainly valid, but does it properly imply the r1c2 <> 2 elimination?
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Re: Questions about ALS’s and overlapping cells

Postby ronk » Mon Sep 03, 2007 10:54 pm

Sudtyro wrote:Now, confusion again arises when one replaces ALS E with ALS F to form the new AIC,
(7=23689)r12459c2 - (9=82)r16c1.
This new chain clearly shows a strong-inference link between (single-occurrence) (7)r1c2 and (2)r1c1, which, in turn, seems to imply the desired elimination (r1c2 <> 2).

By itself, the derived strong inference (7)r1c2 = (2)r1c1 implies no elimination.

As to your other overlap questions, I ask ... why would you want to? You can use r2c4 in any of three ways ...

(7=1459)r2349c9 – (9=5)r9c4 – (5=2347)r23c45 => r4c4 <> 7

(7=1459)r2349c9 – (9=52)r29c4 – (2=347)[r3c4|r23c5] => r4c4 <> 7

(7=1459)r2349c9 – (9=5)r9c4 – (5=2)r2c4 - (2=347)[r3c4|r23c5] => r4c4 <> 7

... neither of which requires overlap.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Questions about ALS’s and overlapping cells

Postby Sudtyro » Tue Sep 04, 2007 1:43 am

ronk wrote:
Sudtyro wrote:Now, confusion again arises when one replaces ALS E with ALS F to form the new AIC,
(7=23689)r12459c2 - (9=82)r16c1.
This new chain clearly shows a strong-inference link between (single-occurrence) (7)r1c2 and (2)r1c1, which, in turn, seems to imply the desired elimination (r1c2 <> 2).

By itself, the derived strong inference (7)r1c2 = (2)r1c1 implies no elimination.


OK, sorry to be so slow on this...but (2)r1c2 can "see" (weakly link to) both (7)r1c2 and (2)r1c1, at least one of which must be true. So, doesn't this force the elimination, r1c2 <> 2?
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Re: Questions about ALS’s and overlapping cells

Postby ronk » Tue Sep 04, 2007 3:13 am

Sudtyro wrote:but (2)r1c2 can "see" (weakly link to) both (7)r1c2 and (2)r1c1, at least one of which must be true. So, doesn't this force the elimination, r1c2 <> 2?

You're right. If one attachs the weak inferences to the derived weak inference, we have ...

(2)r1c2 - (7)r1c2 = (2)r1c1 - (2)r1c2, implying r1c2<>2

Cannibalistic and a bit unorthodox, but valid nonetheless.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Questions about ALS’s and overlapping cells

Postby Sudtyro » Tue Sep 04, 2007 10:42 am

ronk wrote:(2)r1c2 - (7)r1c2 = (2)r1c1 - (2)r1c2, implying r1c2<>2


Yes, I’m more comfortable with the (open) AIC notation than with the equivalent (closed) Nice loops.

So, again, the full AIC (and deduction) of interest is:
(7=23689)r12459c2 - (9=82)r16c1 => r1c2 <> 2,
which we now seem to agree is valid.

However, the issue still remains that the candidate-elimination cell, r1c2, is actually a part of (i.e., overlaps) ALS F, which means that the eliminated candidate, (2)r1c2, is also part of the ALS. I haven’t seen this situation before in conventional AIC’s and would just like to confirm that it is really legitimate.
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Re: Questions about ALS’s and overlapping cells

Postby ronk » Tue Sep 04, 2007 12:00 pm

Sudtyro wrote:
ronk wrote:(2)r1c2 - (7)r1c2 = (2)r1c1 - (2)r1c2, implying r1c2<>2


Yes, I’m more comfortable with the (open) AIC notation than with the equivalent (closed) Nice loops.

No elimination can be made without closing the loop. Showing the "closure" helps one understand the elimination.

Sudtyro wrote:So, again, the full AIC (and deduction) of interest is:
(7=23689)r12459c2 - (9=82)r16c1 => r1c2 <> 2,
which we now seem to agree is valid.

However, the issue still remains that the candidate-elimination cell, r1c2, is actually a part of (i.e., overlaps) ALS F, which means that the eliminated candidate, (2)r1c2, is also part of the ALS. I haven’t seen this situation before in conventional AIC’s and would just like to confirm that it is really legitimate.

The chain is valid and the elimination is legitimate, but why introduce issues of overlap and of "cannibalism" when there is no need to do so? Is there a pot-of-gold at the end of this storm of awkwardness?

You've already pointed out a better ALS xz-rule alternative that raises neither of these issues, specifically ...

(2=3689)r2459c2 - (9=82)r16c1 => r1c2 <> 2
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Questions about ALS’s and overlapping cells

Postby Sudtyro » Wed Sep 05, 2007 10:11 am

ronk wrote:As to your other overlap questions, I ask ... why would you want to?

That’s a fair question, and there is a simple answer. In learning about ALS’s, I had been investigating a manual solving procedure that utilized ALS’s whose (weakly) linking digits occur only once in the ALS. The technique is discussed in detail here. Use of these special ALS’s occasionally leads to an “awkward” AIC configuration with overlapping cells. This post was intended to ask for help in how to properly handle the links in those shared cells.

Answers to Questions 1 and 2 would still be of interest to me.

ronk wrote:Is there a pot of gold at the end of this storm of awkwardness?

Well, maybe not a pot of gold, but certainly a (small) jar of pennies!:)
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Postby Mike Barker » Wed Sep 05, 2007 12:55 pm

I think much of what you are interested in was discussed in the common cells thread. ALS can share common cells as long as they don't contain the linking digits and yes overlap in nodes of a simple or grouped nice loop (ALS included) is very useful - maybe the pennies are silver.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Sudtyro » Wed Sep 05, 2007 7:37 pm

Mike Barker wrote:ALS can share common cells as long as they don't contain the linking digits...

So, it would appear that each of the AIC's referred to in Questions 1 and 2 is improperly linked, since the common cell (r2c4) does in fact contain the linking digit(s). Would you agree with that assessment?

And thanks for the common cells link...I had not see that before!
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Postby Mike Barker » Thu Sep 06, 2007 3:37 am

Yes, they are improperly formed. Consider if r9c4=259. The same ALS exist, but the chain is no longer valid since if r9c9=9 and r9c4=2, then there are still 4 candidates available for "C"
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Sudtyro » Thu Sep 06, 2007 3:41 pm

Thanks, Mike...we’re getting closer, but I’m still fuzzy in spots, and it could just be a matter of ALS semantics. Please bear with me!

If we add a 2 to cell r9c4, then I certainly agree that the AIC for Question 1 is improperly linked. However, that’s also a completely different grid position, even though the ALS’s and the AIC “look” the same. Maybe this is the issue?

So, let’s back up a notch. The grouped AIC for Question 1 is derived from ALS’s A,D and C as:
(7=1459)r2349c9 – (9=52)r29c4 – (5=2347)r23c45 => r4c4 <> 7.

It is then vital to note in this chain that the linking digits occur only once in all three ALS’s. Hence, there exist three “derived” (in ronk’s terminology) strong inferences among six unique candidates in the grid:
(7)r4c9 = (9)r9c9 [call this 7A = 9A]
(9)r9c4 = (2)r2c4 [call this 9D = 2D]
(5)r2c4 = (7)r3c4 [call this 5C = 7C]

There are also unambiguous weak links between 9A and 9D, and between 2D and 5C. Hence, I can immediately form the following AIC:
7A = 9A – 9D = 2D – 5C = 7C => r4c4 <> 7.

So, how can this (apparently) valid chain now also be “improperly formed” when written as the grouped AIC
(7=1459)r2349c9 – (9=52)r29c4 – (5=2347)r23c45 => r4c4 <> 7?
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Postby Mike Barker » Fri Sep 07, 2007 12:56 pm

Sudtyro wrote:So, how can this (apparently) valid chain now also be “improperly formed” when written as the grouped AIC
(7=1459)r2349c9 – (9=52)r29c4 – (5=2347)r23c45 => r4c4 <> 7?

The issue is being right for the wrong reason. The elimination is valid because of the ABC ALS chain or Ron's AIC, not because of the ADC ALS chain or the grouped AIC specifically because the grouped AIC contains a common cell between adjacent ALS (adjacent is key - if they weren't adjacent then common cells would be okay). It is not a question of does the elimination appear to be valid here, but is such an elimination generally valid. The answer is "no" as can be seen if r9c4 = 259.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Sudtyro » Sat Sep 08, 2007 6:03 pm

Thanks, Mike ... I’m following you pretty well now, but, just so I won’t rant too much more, can you first confirm that:

1. Those three derived strong inferences are valid?

2. The AIC, 7A = 9A – 9D = 2D – 5C = 7C, is valid?
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Postby Mike Barker » Sat Sep 08, 2007 11:21 pm

Sudtyro wrote:Can you first confirm that:

1. Those three derived strong inferences are valid?
(7)r4c9 = (9)r9c9 [call this 7A = 9A]
(9)r9c4 = (2)r2c4 [call this 9D = 2D]
(5)r2c4 = (7)r3c4 [call this 5C = 7C]

2. The AIC, 7A = 9A – 9D = 2D – 5C = 7C, is valid?


The derived strong inferences are valid since each is derived from a separate ALS. Of course so is:
(9)r9c4 = (2)r9c4 [call this 9B = 5B]

The AIC is correct, but why? The trick is that with A=9, there is a subset of D which does not include the common cell which must contain the linking digit to "C", that is, "5". If this was not the case then we could place the linking digit in the common cell and no contradiction would occur. Therefore there exists a subset of D, call it "D1" such that (9)r9c4 = (5)D1. Thus a simpler AIC is
7A = 9A – 9D = 5D1 – 5C = 7C
and there is no common cell. Thus the AIC is valid because it contains superfluous information which has no bearing on the conclusion. This is a fancy and hopefully valid and understandable way of saying that the correct AIC is A-B-C (D1 is B) not A-D-C. I think another clue that something unusual is going on is the weak link 2D-5C. Normally when dealing at a cell level (for example, with nice loops which is normally adequate for ALS links) the candidates will be the same on both sides of the link (except at a discontinuity). Something else at the candidate level is occurring here to make the labels different.
Code: Select all
----------------------------------------------------
28    2378  2348 | 1     9     457 | 235   2345 6     
126   236   2346 | CD25  C234  8   | 9     7    A145   
129   2379  5    | C247  C234  6   | 123   8    A14     
-----------------+-----------------+----------------
5     26    126  | 47    16   3    | 8     9    A47     
3     689   168  | 4789  5    479  | 167   146  2   
89    4     7    | 289   16   29   | 156   156  3       
-----------------+-----------------+----------------
27    1     23   | 6     28   59   | 4     235  789       
267   5     9    | 3     248  24   | 1267  126  178     
4     2368  2368 | BD59  7    1    | 236   236  A59     
----------------------------------------------------
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Sudtyro » Mon Sep 10, 2007 11:25 am

Mike,
In all honesty, a lot of what you’ve skillfully and patiently said here is just a tad too subtle for me to fully comprehend at my current experience level. However, my gut feeling now is that it’s also all very correct and proper, especially when one considers that much wiser and more experienced brains than mine have been contemplating these issues for some time.

Having said that, I would suggest only that one not be too quick to fully dismiss the A-D-C (vice A-B-C) type of AIC configuration with one all-encompassing “rule.” This is because, having found an ADC-type chain, it now appears that there must also exist at least one “properly formed” ABC-type chain lurking nearby.

As you can probably surmise, my approach to ALS-based eliminations has relied on what I call “conditional” ALS’s...meaning those whose linking digits are single-occurrence within the ALS. Those two single digits then automatically have a derived strong inference in the grid. One can then simply look for weak links among those digits from within the set of conditional ALS’s, and there are no multiple-occurrence digits in the weak links to worry about. Lastly, form the AIC’s and check for eliminations. The only fly in the ointment (so far) has been this special case in which two adjacent conditional ALS’s are weakly linked in a common cell. Hence, Question 1 of the head post.

One might ask, “Why use only conditional ALS’s?” For me, it’s purely a matter of numbers and how ALS’s are weakly linked. In the example grid position, I counted only about 40 conditional ALS’s (excluding bivalue cells), out of the total number of ALS’s possible for the entire grid (which I would estimate to be at least a hundred or so). All one now needs to do is to look for (single-digit) weak links among those 40 ALS’s. For example, in the Question-3 chains it was MUCH easier for me to spot conditional ALS F (by simply eliminating cell r3c2 from c2) than to find (conventional) ALS E and then have to deal with its multiple-occurrence 2-digit. It’s just a matter of personal preference...I look at a pool of a hundred ALS’s and simply have no idea where to start.

I think I’ll go home now and recount that penny.:)

Many well-deserved thanks to you and Ronk for working this thread!
Sudtyro
 
Posts: 68
Joined: 21 December 2006


Return to Advanced solving techniques

cron