View previous topic :: View next topic |
Author |
Message |
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Mon Sep 04, 2006 5:21 pm Post subject: More on Almost Locked Sets |
|
|
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. dcb |
|
Back to top |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Thu Sep 07, 2006 4:37 pm Post subject: Another "ALS" example |
|
|
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 |
|
|
TKiel
Joined: 22 Feb 2006 Posts: 292 Location: Kalamazoo, MI
|
Posted: Thu Sep 07, 2006 10:19 pm Post subject: |
|
|
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 |
|
|
AZ Matt
Joined: 03 Nov 2005 Posts: 63 Location: Hiding under my desk in Phoenix AZ USA
|
Posted: Thu Sep 07, 2006 10:38 pm Post subject: Hmm... |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Fri Sep 08, 2006 12:47 am Post subject: Learning about the "ALS XZ rule" |
|
|
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 |
|
|
AZ Matt
Joined: 03 Nov 2005 Posts: 63 Location: Hiding under my desk in Phoenix AZ USA
|
Posted: Fri Sep 08, 2006 4:14 pm Post subject: Thanks David |
|
|
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 "xx" I saw in the patterns of the numbers (how they didn't "fit" into the puzzle). Invariably the "xx" 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 "xx" 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 "xx," 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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Fri Sep 08, 2006 5:46 pm Post subject: Another nice "ALS" example |
|
|
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 |
|
|
Ruud
Joined: 18 Jan 2006 Posts: 31
|
Posted: Fri Sep 08, 2006 8:34 pm Post subject: |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Fri Sep 08, 2006 8:46 pm Post subject: Oops! I made a mistake. |
|
|
You're right, Ruud. I was too quick to think I understand the ALS thing. 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 |
|
|
AZ Matt
Joined: 03 Nov 2005 Posts: 63 Location: Hiding under my desk in Phoenix AZ USA
|
Posted: Fri Sep 08, 2006 9:17 pm Post subject: Good example... |
|
|
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 |
|
|
TKiel
Joined: 22 Feb 2006 Posts: 292 Location: Kalamazoo, MI
|
Posted: Fri Sep 08, 2006 11:10 pm Post subject: |
|
|
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 |
|
|
AZ Matt
Joined: 03 Nov 2005 Posts: 63 Location: Hiding under my desk in Phoenix AZ USA
|
Posted: Fri Sep 08, 2006 11:44 pm Post subject: Hi Tracy |
|
|
Of course it's the xy-wing (doh!).
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 |
|
|
TKiel
Joined: 22 Feb 2006 Posts: 292 Location: Kalamazoo, MI
|
Posted: Sat Sep 09, 2006 11:22 am Post subject: |
|
|
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 |
|
|
Mogulmeister
Joined: 03 May 2007 Posts: 1151
|
Posted: Thu May 03, 2007 12:07 pm Post subject: |
|
|
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 |
|
|
|
|
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
|