dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

More on Almost Locked Sets

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Mon Sep 04, 2006 5:21 pm    Post subject: More on Almost Locked Sets Reply with quote

Ruud's "theme week" is officially over on his excellent "Nightmare" web site. I still haven't learned how to find those pesky "ALS" formations. But I'm happy to report that all 7 of the "ALS" puzzles in the "theme week" collection succumbed fairly easily to the "DIC" technique.

Here's an example: this is the "Nightmare" for Wednesday, August 30.
Code:
 *-----------*
 |8..|..4|3..|
 |...|..3|...|
 |7.6|59.|...|
 |---+---+---|
 |...|...|86.|
 |4..|...|.5.|
 |.1.|...|..2|
 |---+---+---|
 |.2.|.7.|.89|
 |...|45.|.2.|
 |...|.6.|7..|
 *-----------*

The more or less "obvious" moves (including a fork on "2"s in column 1 and in row 1) bring you to this point.

Code:
  8     59    12    67    12    4     3     79    56
 129   459  12459   67   128    3    256    79   568
  7     3     6     5     9     28   124    14   148
 239   579  23579  129    34    57    8     6    1347
  4    6789 23789  129    23    67    19    5    137
  56    1     57    89   348   567    49    34    2
  56    2     45    3     7     1    456    8     9
 139   6789 13789   4     5     89    16    2    136
 139   4589 134589  28    6    289    7    134   1345

Now Ruud says we need to look for "ALS"s to crack this puzzle. I'm still trying to understand how to locate those. In the meanwhile, I was able to get through it fairly easily by starting a DIC from r5c6.

If one of you guys can explain where to find the "ALS"s to make progress from here, I'll explain how my "DIC" solution works. Smile dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Thu Sep 07, 2006 4:37 pm    Post subject: Another "ALS" example Reply with quote

Here's a good one for practice with the "ALS XZ rule". This is the "tough" puzzle for today (September 8 in Australia already!) from http://www.sudoku.com.au.
Code:
 *-----------*
 |...|2.8|...|
 |...|7..|182|
 |.9.|...|..3|
 |---+---+---|
 |..3|...|.4.|
 |...|679|...|
 |.5.|...|6..|
 |---+---+---|
 |5..|...|.6.|
 |984|..2|...|
 |...|1.7|...|
 *-----------*

After completing 18 cells using strictly elementary techniques (and with 40 left to go) I found a way forward using the ALS XZ rule. Need a hint? The two Almost Locked Sets are in box 6 and in box 9 -- one of them consists of three cells (with 4 possibilities) and the other consists of a single bi-valued cell. dcb

PS I think I'm starting to understand the connection between the "ALS" technique and the "double-implication chains". Every instance of the "ALS XZ rule" can also be visualized as a forcing chain that ends in a contradiction. Sometimes that forcing chain can also be described as a "DIC". But there are many possible "DIC"s that won't fit into the "ALS" straitjacket.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Thu Sep 07, 2006 10:19 pm    Post subject: Reply with quote

Some techniques are better left to computer solvers and IMO this is one of them. It is usually hard to spot a hidden triple in a puzzle: This is like spotting a hidden quad (quint, sextuple, etc...) that bends around a corner, then points to a cell somewhere else. If you told me that I would either have to find an ALS XZ or some kind of chain, give me the chain any day. (And I don't like to do chains.) I have no doubt that many puzzles could be solved with this techique, but I don't find it worth the time and mental energy that must be extended for a manual solver to use it, even with the aid of SS (or any program). And the fact that you find that the ALS seems to almost be a subset of the DIC, makes it all the more unattractive and unnecessary.
Back to top
View user's profile Send private message
AZ Matt



Joined: 03 Nov 2005
Posts: 63
Location: Hiding under my desk in Phoenix AZ USA

PostPosted: Thu Sep 07, 2006 10:38 pm    Post subject: Hmm... Reply with quote

I have this for boxes 6 and 9:

Code:
79 4   179
38 123 5
6  12  78

2  6   48
37 13  17
89 5   489


As I see it, the only four-digit ALS's in box 6 ar the <1789>, the <1238>, and the <3879>. I see x possibilities on the <8> from r9c7 and the <1> from r8c8 and c9, but I can't find any z candidates that can "see all the z candidates from both sets."

That said, I disagree with Tracy, despite my apparent weakness here. After looking at the ALS's in Ruud's puzzle, some made inherent sense to me, and some did not. I am hoping its just a matter of wrapping my mind around the theory...
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Fri Sep 08, 2006 12:47 am    Post subject: Learning about the "ALS XZ rule" Reply with quote

Matt:

The tricky thing about spotting an Almost Locked Set is that it doesn't have to lie entirely within one box, or column, or row. I had some trouble spotting this one, too. Here's that diagram of boxes 6 & 9.
Code:
79A 4   179
38* 123 5
6   12  78A

2   6   48
37  13  17
89B 5   489

Since I've got a lot of practice with DICs, I spotted a contradiction here by following a chain:

A. r5c7 = 8 ==> r6c9 = 7 ==> r4c7 = 9
B. r5c7 = 8 ==> r9c7 = 9

We can't have two "9"s in column 7, so we must have r5c7 = 3.

To put this in terms of Almost Locked Sets, think of it like this.

Blue Set = r4c7 & r6c9 & r8c7, values {3, 7, 8, 9}
Green Set = r9c7, values {8, 9}
Locked Common Value = "9", in r4c7 & r9c7
Value excluded at r5c7 = "8" (r5c7 can "see" both r6c9 & r9c7)
Code:
79b  4   179
38* 123 5
6   12  78b

2   6   48
37b 13  17
89g 5   489

This example improved my understanding of the explanation that "BennyS" gave when he introduced this rule: if there's an "8" in r5c7, then both the Blue Set and the Green Set become "locked sets", because we've removed one candidate from each of them. But now we're stuck with a contradiction on the "Locked Common Value", which in this case is "9".

=============================================

Tracy:

I agree with you, up to a point. The point is, why bother working Sudoku puzzles at all?

If all you care about is finding the solution as quickly and painlessly as you possibly can, then by all means stick with the techniques that make sense to you.

Personally, I want to use the puzzles to sharpen my mind by concentrating on many details simultaneously. So I'd like to understand this "ALS" technique better than I do already -- not because it will help me solve more puzzles, but because I may be able to improve my ability to visualize the whole puzzle if I think of certain forcing chains from the opposite perspective. It seems to me that the logic involved in spotting an "ALS XZ rule" exclusion is seeing the whole forest all at once, while tracing out the chain is focusing on the trees one by one. I'd like to be able to do it both ways (if I can still learn a new trick). dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
AZ Matt



Joined: 03 Nov 2005
Posts: 63
Location: Hiding under my desk in Phoenix AZ USA

PostPosted: Fri Sep 08, 2006 4:14 pm    Post subject: Thanks David Reply with quote

Well there was my problem, and it explains why some of Ruud's ALS's made perfect sense, while I couldn't grasp others. And now it all makes sense; I was stuck on ALS's in columns, rows, or boxes.

And I now see how this interlaces with DICs and my (for luck of a better term) "hunch" solving technique. I used to take credit for "big" solves involving 20 or so cells, and you'd point out it was really a two line DIC. But the cells were still interrelated, and I needed all of them to explain the "glitch" I saw in the patterns of the numbers (how they didn't "fit" into the puzzle). Invariably the "glitch" was either a DIC or an advance x-wing/swordfish thingy, but hey, we all solve differently. In my mind it is still simply a "glitch" that exists because of the requirement of uniqueness (an inevitable imbalance).

And here we have 5 cells for 4/6/8 numbers to "fit" into = a "glitch," aka a DIC, aka an ALS.

Now, how to convince Keith that you don't just randomly test for DICs, you discover them (or hunt for them?)? I think it has to do with strong links, but I am still working on that theory.
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Fri Sep 08, 2006 5:46 pm    Post subject: Another nice "ALS" example Reply with quote

Hi, Matt!

I'm glad the "ALS XZ rule" is starting to make sense. I'm starting to catch onto it, too.

Here's another great example, where the "ALS" almost jumps right off the page at me. This is from Ruud's Nightmare web site -- it's the puzzle for today, Friday, 8 September, 2006.
Code:
 *--------------------------------------------------------------------*
 | 67     2      3      | 589    589    89     | 467    167    147    |
 | 9      567    57     | 4      2      1      | 67     3      8      |
 | 14     14     8      | 7      3      6      | 2      9      5      |
 |----------------------+----------------------+----------------------|
 | 13457  14578  12457  | 12389  1489   24789  | 4567   12567  1247   |
 | 13457  9      6      | 123    14     247    | 8      1257   1247   |
 | 147    1478   1247   | 128    6      5      | 9      127    3      |
 |----------------------+----------------------+----------------------|
 | 56     3      59     | 25689  7      289    | 1      4      29     |
 | 8      1457   14579  | 1259   1459   3      | 57     257    6      |
 | 2      14567  14579  | 1569   1459   49     | 3      8      79     |
 *--------------------------------------------------------------------*

This is what the grid looked like when the pair of Almost Locked Sets first caught my eye. Can you spot them? Before you read on, here's a hint -- one set lies in column 1, and the other lies in column 3. The "Locked Common" value is tied together in box 1, and the "XZ rule" lets you eliminate candidates in row 7 and in column 3 ...

===========================================================

OK, here's the description in "ALS" terms.

Blue Set = r1c1 & r7c1, values {5, 6, 7}
Green Set = r2c3 & r7c3, values {5, 7, 9}
"Locked Common" = 7, in box 1.

So we can eliminate the value "9" from r8c3, r9c3, r7c4, r7c6, and r7c9.
Looking at it from the forcing chain point of view it should be obvious:

r7c9 = 9 ==> r7c3 = 5 ==> r7c1 = 6
r7c1 = 6 ==> r1c1 = 7; r7c3 = 5 ==> r2c3 = 7

So we have to place a "9" at r7c3, which simplifies the puzzle quite a bit. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Ruud



Joined: 18 Jan 2006
Posts: 31

PostPosted: Fri Sep 08, 2006 8:34 pm    Post subject: Reply with quote

Hi David,

I'm afraid I have to correct you on this one. It is a mistake that I also made when I was first introduced into ALS.

Your Z-digit 9 does not appear in both sets. It is essential for the technique that it does. Here's why:

X-digit 7 must appear either in set A (5,6,7) or set B (5,7,9)
When it appears in set A, set B is locked to (5,9).
When it appears in set B, set A is locked to (5,6).

So, when set A is locked to (5,6), set B is still not locked, and the possibility exists that digit 9 will not be part of its solution. When digit 9 would appear in both sets, there will always be a digit 9 locked in one of the sets.

As compensation, I can offer you an alternative Z-digit 5, which can also be seen as an XY-Wing using 3 of the same cells:
Code:
.------------------.------------------.------------------.
|*67    2     3    | 589   589   89   | 467   167   147  |
| 9     567  #57   | 4     2     1    | 67    3     8    |
| 14    14    8    | 7     3     6    | 2     9     5    |
:------------------+------------------+------------------:
| 1357  1578  1257 | 12389 1489  24789| 4567  12567 1247 |
| 1357  9     6    | 123   14    247  | 8     1257  1247 |
| 147   1478  1247 | 128   6     5    | 9     127   3    |
:------------------+------------------+------------------:
|#56    3    -59   | 25689 7     289  | 1     4     29   |
| 8     147   1479 | 129   149   3    | 57    257   6    |
| 2     14567-14579| 1569  1459  49   | 3     8     79   |
'------------------'------------------'------------------'


cheers,
Ruud
Back to top
View user's profile Send private message Visit poster's website
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Fri Sep 08, 2006 8:46 pm    Post subject: Oops! I made a mistake. Reply with quote

You're right, Ruud. I was too quick to think I understand the ALS thing. Sad But the "9"s are still out, because of the chain. :)

Maybe Tracy is right ... the chains are definitely easier for me to see. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
AZ Matt



Joined: 03 Nov 2005
Posts: 63
Location: Hiding under my desk in Phoenix AZ USA

PostPosted: Fri Sep 08, 2006 9:17 pm    Post subject: Good example... Reply with quote

David

Don't give yet. I think I am seeing ALS as a way to identfy a linked group of cells without being distracted by the plethora of other cells for which the numbers in the group could be a candidate. The z candidate is going to fit into the group one way or another. What might at first appear to be like seeing hidden quads around a corner (to quote Tracy) may be as simple as spotting a few x candidate linking possibilities and seeing if there are any ALS's attached.

PS: In your example, what jumped out at me was the interplay of r1c1, r2c3, and r7c1.

Either r2c3 = 5, or r7c1 = 5, or both
but in no event neither
so in any event, r7c3 cannot =5

I don't know what that is called, but I see it quite a bit.
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Fri Sep 08, 2006 11:10 pm    Post subject: Reply with quote

AZ Matt wrote:
I don't know what that is called, but I see it quite a bit.


It's an XY-wing.

Here is DCB's diagram of box 6 & 9 from his post above:
Code:
 
79A 4   179
38* 123 5
6   12  78A

2   6   48
37  13  17
89B 5   489


The cells marked A, A & B form a DIC that David spotted, which he then expressed in terms of an 'ALS'. They also form an XY-wing that would exclude the 8 in r7c9, r9c9 and r5c7.

David & Matt,

My lack of enthusiasm for the technique does not derive from a lack of understanding of the theory (which I don't, though I do believe it is valid), it derives from the degree of difficulty in applying it. AZ Matt hit the nail on the head when he said:
Quote:
you discover them (...hunt for them?)


For the average human solver (which I consider myself) they would be extremely difficult to spot and that opinion is only reinforced when the both of you, whom I consider way above average (excellent even) human solvers, have trouble spotting them in a puzzle in which you know they exist. What chance, then, do the rest of us have?
Back to top
View user's profile Send private message
AZ Matt



Joined: 03 Nov 2005
Posts: 63
Location: Hiding under my desk in Phoenix AZ USA

PostPosted: Fri Sep 08, 2006 11:44 pm    Post subject: Hi Tracy Reply with quote

Of course it's the xy-wing (doh!). Embarassed

Which is an excellent example of why I get confused by all the names and rules. I can't just apply a rule, I have to understand it on an intuitive level and see how they all interrelate.

Tracy, in my experience, once you understand a technique (take the xy-wing for example) they become second nature (so much so that you take their names for granted, apparently). URs, remote pairs. I'll keep working on ALS and DICs and Type 8 URs, etc., and see if I can come up with a unified theory of Sudoky solving.
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Sat Sep 09, 2006 11:22 am    Post subject: Reply with quote

AZ Matt wrote:
I can't just apply a rule, I have to understand it on an intuitive level and see how they all interrelate.


This is a big difference between your average solver and your excellent solver. I see the pattern (which I must search for) and you see the relationship between the candidates in the cells without knowing there is a pattern. You can expand a three cell chain into a five cell chain because you see that additional relationship, but I struggle with that because there is no pattern. I have the feeling that ALS's are right up your alley.
Back to top
View user's profile Send private message
Mogulmeister



Joined: 03 May 2007
Posts: 695

PostPosted: Thu May 03, 2007 12:07 pm    Post subject: Reply with quote

I find the more I practice ALS the more they start to "jump out" of puzzles and I actuallly prefer them to chains.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group