And something MUCH simpler...

All about puzzles in newspapers, magazines, and books

And something MUCH simpler...

Postby Sudtyro » Fri Feb 16, 2007 3:24 pm

The following candidate grid fragment was developed from puzzle #239 in “Sudoku for Dummies” (2005) after running through the basics. Note that an 8 placed anywhere else in c9 will force a conflict within the four cells shown. Hence, all other candidate 8’s can be eliminated from c9. The structure therefore seems sort of like a cross between a Wing and an ALS variant. What is this structure? And what is the Eureka notation for it? Must be something simple...once again, just can’t spot it.

Code: Select all
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
------+---------+---------
. . . |69  .  . | .  .  68
. . . | . 39  . | .  . 368
. . . | .  .  . | .  .  .
------+---------+---------
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Re: And something MUCH simpler...

Postby re'born » Fri Feb 16, 2007 4:09 pm

Sudtyro wrote:The following candidate grid fragment was developed from puzzle #239 in “Sudoku for Dummies” (2005) after running through the basics. Note that an 8 placed anywhere else in c9 will force a conflict within the four cells shown. Hence, all other candidate 8’s can be eliminated from c9. The structure therefore seems sort of like a cross between a Wing and an ALS variant. What is this structure? And what is the Eureka notation for it? Must be something simple...once again, just can’t spot it.

Code: Select all
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
------+---------+---------
. . . |69  .  . | .  .  68
. . . | . 39  . | .  . 368
. . . | .  .  . | .  .  .
------+---------+---------
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .


It looks like the ALS xz-rule to me. The sets are A={r4c4, r5c59} and B={r4c9} with restricted common x = 6 and common candidate z = 8. So any cell that sees all of the cells in A and B containing an 8 (i.e., column 9) cannot contain an 8. As 8 is also a restricted common candidate, I suppose this also shows that r4c78<>6. An easier way to make all of the deductions at once (without worrying about defining the correct ALS's is to use Subset Counting.

Edit: After reading ronk's post below, I don't know why I wrote that the ALS xz-rule only eliminates 8 in column 9. It also eliminates any other 8 in box 6.
Last edited by re'born on Fri Feb 16, 2007 7:56 pm, edited 1 time in total.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Carcul » Fri Feb 16, 2007 8:52 pm

Nice Loop: [r4c9](-6-[r5c9])-6-[r4c4]-9-[r5c5]-3-[(r5c9)]-8-[r4c9], which implies that (as Rep´nA said) r4c78<>6, all other "8s" in column 9 can be eliminated.

Remark: in these kind of continuous multiple implication nice loops, we can only make deductions with the links that involve the "multiple" node.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Fri Feb 16, 2007 10:31 pm

Maybe not "simple", but I see an ALS-chain with endnode overlap.

Code: Select all
 .  .  . |  .   .   . |  .   .    .
 .  .  . |  .   .   . |  .   .    .
 .  .  . |  .   .   . |  .   .    .
---------+------------+-------------
 .  .  . |B69   .   . |  .   . AC68
 .  .  . |  . B39   . |  .   . C368
 .  .  . |  .   .   . |  .   .    .
---------+------------+-------------
 .  .  . |  .   .   . |  .   .    .
 .  .  . |  .   .   . |  .   .    .
 .  .  . |  .   .   . |  .   .    .

 -8-A-6-B-3-C-8-     (shorthand)

 -8-r4c9-6-{ALS:r4c4=6|3=r5c5}-3-{ALS:r5c9=3|8=r45c9}-8-

 implies r1236789c9<>8 and r456c78<>8

It "hides" Carcul's multiple inference in the overlap.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: And something MUCH simpler...

Postby Sudtyro » Sat Feb 17, 2007 11:06 pm

rep'nA wrote:
It looks like the ALS xz-rule to me. The sets are A={r4c4, r5c59} and B={r4c9} with restricted common x = 6 and common candidate z = 8.


Ok...trying to learn fast, but...I though an ALS had to have cells in the same house. The cells in set A seem to lie in two houses.
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Re: And something MUCH simpler...

Postby re'born » Sun Feb 18, 2007 12:29 am

Sudtyro wrote:
rep'nA wrote:
It looks like the ALS xz-rule to me. The sets are A={r4c4, r5c59} and B={r4c9} with restricted common x = 6 and common candidate z = 8.


Ok...trying to learn fast, but...I though an ALS had to have cells in the same house. The cells in set A seem to lie in two houses.


Here is the way I think of the ALS xz-rule. You have two almost locked sets A and B. Say A has m cells (and hence m+1 candidates) and B has n cells (and hence n+1 candidates). Now assume that A and B both share candidates x and z, with the additional property that A and B cannot both contain x. Find a cell C with the candidate z that sees every cell in A and B that could be z. Assume this cell C was z. Then A and B do not have z and now A has m cells with m candidates and B has n cells with n candidates, i.e., A has become a naked m-set and B a naked n-set. But in a naked set every candidate appearing in the set must eventually be in one of the cells (think of a naked pair as an example). So x must be in both A and B, a contradiction to our assumption that x is not in both.

If you can get through the above description, you will see that there is very little limit to where the cells in A and B can lie. The biggest restriction is finding that common candidate z and the cell C that sees every occurrence of z in both A and B.

I hope this helps. If not, perhaps a better expositor and expert on ALS will step in to provide support.
re'born
 
Posts: 551
Joined: 31 May 2007

Re: And something MUCH simpler...

Postby udosuk » Sun Feb 18, 2007 5:06 pm

Sudtyro wrote:... I though an ALS had to have cells in the same house. The cells in set A seem to lie in two houses.

What is a "house"? My definition is a group of cells that doesn't have repeated values... If you look closely to [r4c49+r5c5], it's obvious that it cannot have repeated values... Therefore it is effectively a "house"...:idea:

In Killer Sudoku puzzles we have to deal with groups like these a lot (we often call these "buddy cells")... And if you can broaden your view on buddy cells/houses from merely rows/columns/blocks/diagonals/cages onto groups like the above it helps a lot...:)

Edited: Mea Culpa, I misread the set of cells from rep'nA's example... [r4c49+r5c5] is indeed effectively a house, but it doesn't help in constructing the ALS... Meanwhile rep'nA's [r4c4+r5c59] is NOT a house in any sense, but is valid to act as an ALS component...
Last edited by udosuk on Mon Mar 19, 2007 4:08 pm, edited 1 time in total.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Nothing's simple it seems!

Postby Sudtyro » Sun Feb 18, 2007 11:10 pm

Thanks to Rep’nA for a clear and detailed explanation. I believe you are right about the limits on where the cells in A and B can lie. If you allow the cells of an ALS to be in different houses, then your analysis very neatly eliminates both the extra 6’s and the 8’s in this problem using a single ALS-XZ rule, and that seems fairly significant.

My only heartburn is that the Sudopedia definition of an ALS requires its cells to lie in the SAME house (and only truly makes sense to me that way). As a beginner, I rely on basic definitions like that in order to build consistent solution strategies. Your strategy clearly modifies this definition, and that leaves me feeling a bit uneasy.

In a similar vein, I am much more comfortable with Ronk’s three ALS’s, all of which strictly obey the Sudopedia definition. I had previously tried the puzzle on my own with the equivalent of Ronk’s sets B and C, but the ALS-XZ rule eliminated only the 6’s (hence this post). What I didn’t know at the time was that it’s apparently OK to overlap ALS’s (Sudopedia doesn’t say either way)!

With Ronk’s overlapping set A now included, it looks like one can apply the ALS-XY-Wing rule to sets A, B and C. With B as the pivot and with restricted commons 3 and 6, then X=8, so the 8’s are eliminated. Done! This result certainly reinforces your own observations, but it also keeps the Sudopedia ALS definition intact, at the expense of an extra ALS.
Edit: Just realized that my original ALS-XY-Wing application was wrong. Pivot B removes the 8's.:(

Carcul and Ronk...thanks also for the Nice Loop and the ALS chain. I understand the basics of Nice Loops and chains, but I’m really weak (more like bewildered) on their ALS notation conventions. Can you point to a good source for the notation? Sudopedia’s Eureka article briefly addresses ALS notation, but only in an AIC.

Udosuk...thanks for your input...let me think on this a bit. Again, it seems to be a definition issue.
Last edited by Sudtyro on Wed Feb 21, 2007 9:11 am, edited 2 times in total.
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Re: Nothing's simple it seems!

Postby ronk » Sun Feb 18, 2007 11:33 pm

Sudtyro wrote:I understand the basics of Nice Loops and chains, but I’m really weak (more like bewildered) on their ALS notation conventions. Can you point to a good source for the notation? Sudopedia’s Eureka article briefly addresses ALS notation, but only in an AIC.

I'm not sure a consensus opinion on ALS notation has ever been reached, but I'll look around.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Nothing's simple it seems!

Postby re'born » Mon Feb 19, 2007 11:31 am

Sudtyro wrote:Thanks to Rep’nA for a clear and detailed explanation. I believe you are right about the limits on where the cells in A and B can lie. If you allow the cells of an ALS to be in different houses, then your analysis very neatly eliminates both the extra 6’s and the 8’s in this problem using a single ALS-XZ rule, and that seems fairly significant.

My only heartburn is that the Sudopedia definition of an ALS requires its cells to lie in the SAME house (and only truly makes sense to me that way). As a beginner, I rely on basic definitions like that in order to build consistent solution strategies. Your strategy clearly modifies this definition, and that leaves me feeling a bit uneasy.


Perhaps I am wrong. The ALS xz-rule is not how I think about these issues and I am bound to mess up. As I mentioned in my first post, I think the way to go is with Subset Counting. With that there is no ambiguity. If you aren't familiar with the technique, let me explain it in this situation.

We have four cells r4c49, r5c59 that can contain the following candidates {3,6,8,9} where, a priori, we allow repetition. Looking at the grid, we see that there can never be more than one 3, two 6's, one 8, and one 9. So the four cells will each, if you like, choose a number out of a hat containing [3,6,6,8,9]. If we somehow removed two of those numbers ahead of time, the four cells would only be choosing from a hat containing three numbers, an impossibility. So, for instance, if r4c7 = 6 or r4c8 = 6, then none of our four cells could be a 6. This is tantamount to removing both 6's from the hat, leaving us with only three numbers for four cells, a contradiction.

The exclusion of 8's is only slightly more complicated. An 8 in box or column 9, but not in r45c9, will immediately remove 8 from the hat and force r4c9=6 which removes another 6 from the hat since the only way to get two 6's is for r4c4=6 and r5c9=6. Left with only two numbers for the remaining three cells, we get a contradiction.

Of course, this may seem rather glib and complicated compared with the ALS rules, but in practice it is (at least when given the cells) much easier to apply. Note that there is no concern here about houses or even any decision to be made about how to break up the cells into the sets A and B, etc.
re'born
 
Posts: 551
Joined: 31 May 2007

Re: Nothing's simple it seems!

Postby Sudtyro » Tue Feb 20, 2007 6:07 pm

rep'nA wrote:Of course, this may seem rather glib and complicated compared with the ALS rules, but in practice it is (at least when given the cells) much easier to apply.


I'd guess that Subset Counting is probably not any more complicated than the other techniques. The ALS rules seem to solve the problem more quickly, but, as you say, they depend on the proper choice of sets.

Among the original four cells, I count six ALS's, which would then generate something like 20 different possible 3-set combinations. Then you still have to examine each of those for the two restricted commons plus the X-common. That sounds "complicated" to me, and, if fact, I may have already erred on the ALS-XY-Wing application!

Next project: Look at Subset Counting AND think about Udosuk's definition of a "house."
Sudtyro
 
Posts: 68
Joined: 21 December 2006

re: "Sudoku for Dummies" (2005) #239

Postby Pat » Fri Jun 01, 2007 6:31 am


        can the above make sense
        when 3 posts in this topic have vanished ?

rep'nA (2007.Feb.16 at 15:09; edited once at 22:56) wrote:
Sudtyro wrote:The following candidate grid fragment was developed from puzzle #239 in “Sudoku for Dummies” (2005) after running through the basics. Note that an 8 placed anywhere else in c9 will force a conflict within the four cells shown. Hence, all other candidate 8’s can be eliminated from c9. The structure therefore seems sort of like a cross between a Wing and an ALS variant. What is this structure? And what is the Eureka notation for it? Must be something simple...once again, just can’t spot it.

Code: Select all
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
------+---------+---------
. . . |69  .  . | .  .  68
. . . | . 39  . | .  . 368
. . . | .  .  . | .  .  .
------+---------+---------
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .
. . . | .  .  . | .  .  .



It looks like the ALS xz-rule to me. The sets are A={r4c4, r5c59} and B={r4c9} with restricted common x = 6 and common candidate z = 8. So any cell that sees all of the cells in A and B containing an 8 (i.e., column 9) cannot contain an 8. As 8 is also a restricted common candidate, I suppose this also shows that r4c78<>6. An easier way to make all of the deductions at once (without worrying about defining the correct ALS's is to use Subset Counting.

Edit: After reading ronk's post below, I don't know why I wrote that the ALS xz-rule only eliminates 8 in column 9. It also eliminates any other 8 in box 6.




rep'nA (2007.Feb.17 at 23:29) wrote:
Sudtyro wrote:
rep'nA wrote:
It looks like the ALS xz-rule to me. The sets are A={r4c4, r5c59} and B={r4c9} with restricted common x = 6 and common candidate z = 8.


Ok...trying to learn fast, but...I though an ALS had to have cells in the same house. The cells in set A seem to lie in two houses.


Here is the way I think of the ALS xz-rule. You have two almost locked sets A and B. Say A has m cells (and hence m+1 candidates) and B has n cells (and hence n+1 candidates). Now assume that A and B both share candidates x and z, with the additional property that A and B cannot both contain x. Find a cell C with the candidate z that sees every cell in A and B that could be z. Assume this cell C was z. Then A and B do not have z and now A has m cells with m candidates and B has n cells with n candidates, i.e., A has become a naked m-set and B a naked n-set. But in a naked set every candidate appearing in the set must eventually be in one of the cells (think of a naked pair as an example). So x must be in both A and B, a contradiction to our assumption that x is not in both.

If you can get through the above description, you will see that there is very little limit to where the cells in A and B can lie. The biggest restriction is finding that common candidate z and the cell C that sees every occurrence of z in both A and B.

I hope this helps. If not, perhaps a better expositor and expert on ALS will step in to provide support.




rep'nA (2007.Feb.19 at 10:31) wrote:
Sudtyro wrote:Thanks to Rep’nA for a clear and detailed explanation. I believe you are right about the limits on where the cells in A and B can lie. If you allow the cells of an ALS to be in different houses, then your analysis very neatly eliminates both the extra 6’s and the 8’s in this problem using a single ALS-XZ rule, and that seems fairly significant.

My only heartburn is that the Sudopedia definition of an ALS requires its cells to lie in the SAME house (and only truly makes sense to me that way). As a beginner, I rely on basic definitions like that in order to build consistent solution strategies. Your strategy clearly modifies this definition, and that leaves me feeling a bit uneasy.


Perhaps I am wrong. The ALS xz-rule is not how I think about these issues and I am bound to mess up. As I mentioned in my first post, I think the way to go is with Subset Counting. With that there is no ambiguity. If you aren't familiar with the technique, let me explain it in this situation.

We have four cells r4c49, r5c59 that can contain the following candidates {3,6,8,9} where, a priori, we allow repetition. Looking at the grid, we see that there can never be more than one 3, two 6's, one 8, and one 9. So the four cells will each, if you like, choose a number out of a hat containing [3,6,6,8,9]. If we somehow removed two of those numbers ahead of time, the four cells would only be choosing from a hat containing three numbers, an impossibility. So, for instance, if r4c7 = 6 or r4c8 = 6, then none of our four cells could be a 6. This is tantamount to removing both 6's from the hat, leaving us with only three numbers for four cells, a contradiction.

The exclusion of 8's is only slightly more complicated. An 8 in box or column 9, but not in r45c9, will immediately remove 8 from the hat and force r4c9=6 which removes another 6 from the hat since the only way to get two 6's is for r4c4=6 and r5c9=6. Left with only two numbers for the remaining three cells, we get a contradiction.

Of course, this may seem rather glib and complicated compared with the ALS rules, but in practice it is (at least when given the cells) much easier to apply. Note that there is no concern here about houses or even any decision to be made about how to break up the cells into the sets A and B, etc.
User avatar
Pat
 
Posts: 3295
Joined: 18 July 2005


Return to Published puzzles