Need help with almost-locked-sets

Advanced methods and approaches for solving Sudoku puzzles

Need help with almost-locked-sets

Postby smoof » Sat Mar 04, 2006 7:02 am

I'm trying to understand the ALS method posted here: http://www.stolaf.edu/people/hansonr/sudoku/explain.htm
I don't have any problem spotting the ALS, the difficulty I'm having is trying to figure out which candidates can be eliminated from which cells. I'm not confident that I understand the definition of "weakly associated" cells.

Take this puzzle for example (I realize simpler techniques could be applied to solve the puzzle)

Code: Select all
   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 |   238 |   689 |   269 ||   368 |     4 |     5 ||     7 |    23 |     1
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |   357 |    67 |   567 ||     1 |    36 |     2 ||     9 |     8 |     4
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 |   238 |     1 |     4 ||     9 |     7 |    38 ||     5 |    23 |     6
===========================||=======================||=======================
r4 |     1 |     3 |   579 ||   567 |    69 |    67 ||     2 |     4 |     8
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 |    25 |     4 |     8 ||   235 |    13 |    13 ||     6 |     9 |     7
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 |     6 |    79 |   279 ||   278 |    89 |     4 ||     1 |     5 |     3
===========================||=======================||=======================
r7 |    78 |   678 |    67 ||     4 |     2 |     9 ||     3 |     1 |     5
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 |     9 |     5 |     3 ||    78 |    18 |   178 ||     4 |     6 |     2
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 |     4 |     2 |     1 ||    36 |     5 |    36 ||     8 |     7 |     9
.............................................................................


ALS A = r4c5, r6c5 {69, 89}
ALS B = r4c6 {67}

My flawed understanding is this:
1. A and B are linked by 6.

2. The unique values of each ALS can be eliminated as candidates from all other cells in the same unit as A and B except for the nodes of A and B.

3. The unit containing A and B is block 5.

4. 8 and 9 are unique to A and therefore can be eliminated as candidates for all cells in block 5 except for the nodes of A and B.

5. 7 is unique to B and therefore can be eliminated as a candidate for all cells in block 5 except for the nodes of A and B.

I know my understanding is flawed because having already seen the puzzles solution, I know that r6c4 is a 7 (which would have been eliminated in step 5 above).

I've been trying to use Bob Hanson's solver to reverse engineer the rule for which candidates can be eliminated but I just can't seem to grasp it. Could someone please explain the logic of which candicates can be eliminated from which cells. I'm not that savy with all the set and math theory so the simpler the terminology the better.

Thanks for your help
smoof
 
Posts: 5
Joined: 03 March 2006

Postby tarek » Sat Mar 04, 2006 10:00 am

User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby smoof » Sat Mar 04, 2006 7:46 pm

Thanks, I had actually already read that thread and any others I could find on the subject. The problem is that thread seems to contradict what Bob Hanson is saying.

My understanding of the thread is that you have a candidate that links the two ALS (call it x). Then you take any other candidate common to the two ALS (call it z). Where the units of all cells containing z in the two ALS intersect, you can remove candidate z from the cell(s). I find it difficult to be totally confident in my understanding because the thread is missing one important part, there is very little information explicitly listing the cells where the candidates can be removed. That would be very helpful to people trying to learn the technique.

My understanding of Bob Hanson's method is that you can take a non-common candidate of the two ALS and remove that candidate from all other cell's that are "weakly associated" with the ALS containing the non-common candidate. But I can't determine what "weakly associated" means so I can't decide which cells I can remove the candidate from. I thought "weakly associated" meant any cell in the same unit as the non-common candidate, but that is wrong.

Needless to say, I'm confused...
smoof
 
Posts: 5
Joined: 03 March 2006

Postby tarek » Sat Mar 04, 2006 8:34 pm

As I see it smoof, you need to go back to basics & then build everything up again:

1. Start by mastering what an ALS is, identify them....

2. The rules in benny's thread, decribe the relationship between different ALSs present in the grid at the same time

3. take the xz rule...... u have a relationship between 2 ALSs

4. In xy rule there are 3 ALSs..............

I thought that it was quite clear......

Although I differ slightly in assigning group names, The method is universal even for Bob Hanson.

Tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby absolute beginner » Sat Mar 04, 2006 8:38 pm

Hello Smoof,
there is actually an ALS-xz in your sample.
Code: Select all
+----------------+-------------+---------+
| *238 #689 ^269 | *368 4  5   | 7 *23 1 |
|  357 #67   567 |  1   36 2   | 9  8  4 |
|  238  1    4   |  9   7  38  | 5  23 6 |
+----------------+-------------+---------+
|  1    3    579 |  567 69 67  | 2  4  8 |
|  25   4    8   |  25  13 13  | 6  9  7 |
|  6   #79   279 |  278 89 4   | 1  5  3 |
+----------------+-------------+---------+
|  78   678  67  |  4   2  9   | 3  1  5 |
|  9    5    3   |  78  18 178 | 4  6  2 |
|  4    2    1   |  36  5  36  | 8  7  9 |
+----------------+-------------+---------+

A={2368} at r1c1, r1c4, r1c8 in Row 1
B={6789} at r1c2, r2c2, r6c2 in Column 2
x=8
z=6
Eliminate 6 at r1c3

The two ALSs have to be linked, here with x=7,
but there has to be another common Digit.
absolute beginner
 
Posts: 22
Joined: 26 February 2006

Postby absolute beginner » Sat Mar 04, 2006 9:50 pm

For clearance:
8 is restricted common to A and B,
because 8 in A forces, that 8 is not in B
( and so be would be {679} ) and
vice versa ( A would be {236} ).
z=6 has only to be in A and B,
there is no need, that its restricted common.

r1c3 sees all the 6es in A and all the
6es in B. If r1c1=6, then both A and B
had no 6. So A would be {238} and
B would be {789} but the both 8s
fource a contradiction
absolute beginner
 
Posts: 22
Joined: 26 February 2006

Postby smoof » Sun Mar 05, 2006 2:37 am

Thanks everyone for the responses. Just to clarify, I'm trying to get some help determining what constitutues a cell's "weak association" as specified in Bob Hanson's ALS algorithm.

Bob's ALS algorithm appears to be different from Benny's xz rule since it has additional properties that allow a further reduction in candidates. This is an excerpt taken from Bob's web page:

But it's better than that. If B has the 7, Set A cannot have it -- Set A must be 1, 3, 8, and 9. Likewise, if Set A has the 7, then Set B does not. It must have 2 and 3. And then A has 1, 3, 8, and 9. Ah, but these are the only two possibilities! Either the 7 is in Set A or Set B. In either case, A has a 1, 8, and 9; and B has a 2. then any other 8 or 9 weakly associated with A, and any other 2 weakly associated with B can be eliminated! This includes any 8s in the third block (in the cells highlighted in red) as well as the 8 in row 2, column 6. Neat, huh?


It's the part highlighted in red that gives it more power than the standard ALS xz rule. The only part I'm having trouble with is the determination of which cells can be classified as "weakly associated". Thanks again for the help.
smoof
 
Posts: 5
Joined: 03 March 2006

Postby ronk » Sun Mar 05, 2006 3:57 am

smoof wrote:Bob's ALS algorithm appears to be different from Benny's xz rule since it has additional properties that allow a further reduction in candidates.

The ALS xz-rule is the general term for two almost-locked-sets with either 1) one restricted common (singly-weakly-linked) candidate or 2) two restricted common (doubly-weakly-linked) candidates. The 'restricted common' term originated with bennys and the doubly-weakly-linked term originated with Bob Hanson AFAIK.

In the case where the ALS sets are only singly-weakly-linked, eliminations based on Bob Hanson's description would be no different than bennys'. However, quite a few additional eliminations are possible for the doubly-weakly-linked case, which I don't think bennys ever addressed.

Just be sure which one of the two cases you're dealing with.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Neunmalneun » Sun Mar 05, 2006 12:14 pm

absolute beginner wrote:
r1c3 sees all the 6es in A and all the
6es in B. If r1c1=6, then both A and B
had no 6. So A would be {238} and
B would be {789} but the both 8s
fource a contradiction


Thanks to absolute beginner. That was the first explication that helped me to understand the ALS rule. I read benny's post several times and saw that the rule worked, but now I have an idea why it can eliminate the z-candidates outside the groups. I assume it only works if both the groups (A and B) have n cells and n+1 candidates (?). Kind regards.
Neunmalneun
 
Posts: 52
Joined: 22 December 2005


Return to Advanced solving techniques