5/20/07 Nightmare...reduced-pool ALS's

Discuss the <a href="http://www.sudocue.net/daily.php">Daily Sudoku Nightmare</a> here
Post Reply
Sudtyro
Hooked
Hooked
Posts: 49
Joined: Tue Jan 16, 2007 8:17 pm

5/20/07 Nightmare...reduced-pool ALS's

Post by Sudtyro »

This post is the result of a first effort to simplify the process of finding ALS-based eliminations. It grew out of the personal frustration of being unable to manually advance a difficult puzzle beyond the “basics” stage (except perhaps for a few additional simple chains or patterns). The approach (maybe new) stems from an empirical observation that a very restricted class of ALS’s can provide some (but not all) of the eliminations available from a puzzle’s entire ALS pool.

Let me begin with a brief (and hopefully accurate) review of ALS basics: A conventional ALS (Almost Locked Set) comprises N+1 candidates located in N cells within the same house (row, column or box). Any one of the N+1 candidates in the set is strongly linked to the remaining N candidates. The link is strong because all occurrences of any one candidate, if removed (i.e., false), would then leave N cells sharing N candidates, which is a locked set (i.e., all N candidates true).

The Eureka notation for the candidates in an ALS normally begins with a single digit, followed first by a strong-inference symbol, and then finally by the remaining digits in the set. The digits are arranged (e.g., 8=593) so that the first and last digits are the ones intended to weakly link with candidates in the adjacent nodes on either side of the ALS. The first digit is often called the “target” digit, and the last digit is often called the “restricted common.” One can freely switch these two digits in the notation and still have the same ALS, and this happens frequently when linking ALS’s to form an AIC (Alternating Inference Chain). It is important to note that the first and last digits have either a strong or a strong-only link. One key requirement (and complication) for both the first and last digit is that if the digit has multiple occurrences in the ALS, then any weak link to that digit in the ALS must see all examples of that digit in the ALS.

ALS’s are easy to form. By definition, the N possible candidate digits in the N unresolved cells of a single house form one (or more) locked sets. Hence, from a house containing a single locked set of N candidates, one can quickly form an ALS (with N-1 cells and N candidates) simply by eliminating any one cell in the locked set. One can also build ALS’s from the other direction. I.e., a bivalue cell is the smallest possible ALS (one cell and two candidates). Next, say, comes two bivalue cells that share one common digit (two cells and three candidates), and so on. A single house can therefore host many ALS’s, so how does one go about selecting from this staggering multitude of choices among all 27 houses in a puzzle?

Well, it’s always nice to keep things simple. And one very effective way to attack this problem is first to significantly reduce the number of ALS’s to be considered and then to similarly limit the allowed elimination strategies. So, here goes something a little simpler for the manual solver...

The ALS pool becomes very reduced and manageable provided that:
1. Each ALS is subject to the condition that the first and last digits (i.e., the 8 and the 3 in the sample above) occur only once in the set.
Rationale: This allows each of those two digits to now weakly link, without restriction, to any other eligible peer candidate, since the peer can see all occurrences (only one) of that digit. These conditional ALS’s are relatively few in number, and some houses may have none at all.
2. Each ALS has at least three candidates (this necessarily excludes bivalue cells from the reduced pool).
Rationale: A player learns early-on how to visually combine (pattern-match) a bivalue cell with a 2-cell ALS to form either an XY- or an XYZ-Wing, and this technique has been extended to combine that bivalue cell with a 3-cell ALS (WXYZ-Wing) or with any N-cell ALS (...VWXYZ-Wing). Each of these “N-Wings” comprises one bivalue cell weakly linked to an N-cell ALS to form a 2-node grouped AIC equivalent to an ALS-XZ rule. Bivalue cells will therefore be treated differently than other ALS’s and used only to form the “N-Wings.”

The allowed elimination strategies are limited to a single item:
1. Develop grouped AIC’s using only the reduced-pool ALS’s (and the bivalue cells) as nodes.
Rationale: This greatly reduces (and simplifies) the node pool used to form the AIC’s.

Manual Solution Procedure: [This is almost fun to do!:)]
1. Select an initial target digit. Do this by examining the puzzle’s single-digit grids for a case with a large number of conjugate pairs that form multiple clusters. Consider it a plus if the candidate also appears in any bivalue cells.
2. Find one or more ALS’s from the reduced pool that contain the target digit and any other restricted-common digit. There’s no need to get them all at once (one at a time is fine), since this step will be repeated.
3. Add these to an ALS “plot,” similar to a bilocation plot, showing a line (strong-inference link) between the target and restricted-common digits.
4. Using only the current ALS plot, look for new weak links between the ALS’s.
5. Use the weak links to develop grouped AIC’s. Check each grouped AIC for possible eliminations and (optionally) update the puzzle grid.
6. Visually inspect the puzzle grid for a bivalue cell whose two candidates are the same as those of any ALS in the current ALS plot (bivalue cell and ALS should not reside in the same house). If the bivalue cell can weakly link to the ALS, then return to step 5.
7. Repeat steps 2-6, as needed, until the ALS pool for the current target digit is depleted.
8. Select a new target digit and return to step 2. A good choice for the new target digit is any previous restricted-common digit, which then allows for possible weak links between those previous and any new ALS’s.
9. Repeat step 8, as needed, until the entire (reduced) ALS pool is depleted.

The following examples will illustrate the above manual solution procedure as applied to the SudoCue Daily Nightmare for Sunday, May 20, 2007. The grid position shown below results after running through the “basics,” and after an additional pair of short Turbot chains.

Code: Select all

--------------------------------------------------
28    2378  2348 | 1    9    2457 | 235   2345 6     
126   236   2346 | 25   234  8    | 9     7    145   
129   2379  5    | 247  234  6    | 123   8    14    
-----------------+----------------+---------------
5     26    126  | 47   16   3    | 8     9    47    
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 | 59   7    1    | 236   236  59     
--------------------------------------------------
We now begin the search for ALS-based eliminations.

Step 1. Select an initial target digit.
A review of the unresolved single-digit 7’s grid (shown below) suggests trying 7 as the initial target digit. Note the numerous conjugate pairs that form three separate clusters. The 7 digit also appears in three of the puzzle’s bivalue cells: r4c49 (a naked pair) and r7c1.

Code: Select all

. 7 . | . . 7 | . . .
. . . | . . . | . . .
. 7 . | 7 . . | . . .
------+-------+------
. . . | 7 . . | . . 7
. . . | 7 . 7 | 7 . .
. . . | . . . | . . .
------+-------+------
7 . . | . . . | . . 7
7 . . | . . . | 7 . 7
. . . | . . . | . . . 
Step 2. Find ALS’s from the reduced pool containing 7 as the target digit and any other restricted-common digit.
One can start with any house in the puzzle, and c9 seems like a good place to begin. Look initially for a few easy ALS’s. Bivalue cells r34c9 quickly provide the first ALS as (7=41)r34c9. Call this ALS “a.” Then, simply add cell r2c9 to get ALS “b” (7=145)r234c9. From there, add cell r9c9 to get ALS “c” (7=1459)r2349c9. Moving now from right to left across the puzzle, inspection reveals no ALS’s from b5 or c7. In b6, the two conjugate pairs, for 4 and 7, suggest eliminating cell r4c9, which immediately yields ALS “d” (7=1564)r56c78. In c6, the two conjugate pairs, for 5 and 7, suggest eliminating cell r1c6, which produces ALS “e” (7=2495)r5678c6. Continuing on, c4 appears to be empty, but b2, which also hosts two conjugate pairs, for 5 and 7, immediately yields ALS “f” (7=2345)r23c45 by eliminating cell r1c6. Let’s pause at this point and move on to step 3.

Step 3. Add these to an ALS “plot.”
A text-based version of the current ALS plot might appear as shown below, where two occurrences of the same letter denote a strong-inference link between the indicated digits. Each ALS uses a different letter.

Code: Select all

. . . | .  . .  | .  .  .
. . . | 5f . .  | .  .  5b
. . . | 7f . .  | .  .  1a
------+---------+-----------
. . . | .  . .  | .  .  7abc
. . . | .  . 7e | 7d 4d .
. . . | .  . .  | .  .  .
------+---------+-----------
. . . | .  . 5e | .  .  .
. . . | .  . .  | .  .  .
. . . | .  . .  | .  .  9c  
Step 4. Look for new weak links.
There is an obvious weak link between 7abc and 7d and between 7d and 7e. However, only the (also obvious) weak link between 5b and 5f in r2 leads to our first useful AIC.

Step 5. Develop grouped AIC’s and check for eliminations.
In an abbreviated AIC notation, we have
7b = 5b – 5f = 7f => r4c4 <> 7.
The grouped-AIC notation is
(7=145)r234c9 – (5=2347)r23c45 => r4c4 <> 7,
which is equivalent to an ALS-XZ rule with X=5 and Z=7.

Note: The other two weak links developed in step 4 also generate AIC’s, but they can produce no eliminations. E.g., the weak link between 7d and 7e forms the AIC, 4d = 7d – 7e = 5e, but no puzzle candidate can “see” (weakly link to) both 4d and 5e, so no eliminations are possible.

Step 6. Visually inspect the puzzle grid for a bivalue cell whose two candidates are the same as those of any ALS in the current ALS plot (bivalue cell and ALS should not reside in the same house).
The two candidates (4 and 7) in bivalue cell r4c4 match those in ALS “d,” but no weak links are available.

Step 7. Returning now to step 2, we continue our search of the puzzle grid for additional ALS’s containing target digit 7. In c2, the two conjugate pairs, for 7 and 9, suggest eliminating cell r3c2 to immediately form ALS “g” (7=23689)r12459c2. In c1, bivalue cells r17c1 quickly yield ALS “h” (7=28)r17c1. Add cell r6c1 to get ALS “i” (7=289)r167c1, and finally, add cell r3c1 to get ALS “j” (7=2891)r1367c1. We pause here and again move to step 3.

Step 3. The updated ALS plot now becomes:

Code: Select all

8h   7g . | .  . .  | .  .  .
.    .  . | 5f . .  | .  .  5b
1j   .  . | 7f . .  | .  .  1a
----------+---------+-----------
.    .  . | .  . .  | .  .  7abc
.    9g . | .  . 7e | 7d 4d . .
9i   .  . | .  . .  | .  .  .
----------+---------+-----------
7hij .  . | .  . 5e | .  .  .
.    .  . | .  . .  | .  .  .
.    .  . | .  . .  | .  .  9c  
Step 4. Look for new weak links.
One can easily spot the new weak links, 1a and 1j in r3, as well as 9g and 9i in b4.

Step 5. Develop grouped AIC’s and check for possible eliminations.
In abbreviated notation, we now have
7a = 1a – 1j = 7j => r7c9 <> 7.
The grouped-AIC notation is
(7=41)r34c9 - (1=2897)r1367c1 => r7c9 <> 7,
which is again equivalent to an ALS-XZ rule with X=1 and Z=7.
Note that this elimination actually follows (see the 7’s grid) from the previous one (r4c4 <> 7). However, this new chain could very well have been discovered first, depending on the ALS search sequence.

The other weak link (9g and 9i) yields the AIC,
7g = 9g – 9i = 7i,
although no eliminations result since the victim cells (r1c1 and r7c2) contain no 7’s.

Step 6. Visually inspect the puzzle grid for a bivalue cell whose two candidates are the same as those of any ALS in the current ALS plot (bivalue cell and ALS should not reside in the same house).
No new cases are found, but note that we also opted not to update the puzzle grid in the first step 5, where the r4c4 <> 7 elimination would have placed a 4 in r4c4. This placement would then leave a new bivalue cell at r5c6. Using (temporarily) this one grid adjustment, we see immediately that the new bivalue cell’s candidates (7 and 9) exactly match those in ALS “g,” and there is an obvious weak link between (9)r5c6 and 9g. The weak link then allows us to form the AIC,
(7=9)r5c6 – 9g = 7g => r1c6 <> 7.
The grouped-AIC notation is
(7=9)r5c6 – (9=23687)r12459c2 => r1c6 <> 7.
Note that this chain is equivalent to a UVWXYZ-Wing (variant) with U = 9 and Z = 7. It is also equivalent to an ALS-XZ rule with X = 9 and Z = 7.

Step 7. There are only a few more ALS’s to find having 7 as the target digit, but we’ll skip those, keep the original grid position, and move on, in order to illustrate step 8.

Step 8. Select a new target digit. A good strategy is to pick a previous restricted-common to be the new target digit.
As shown in the current ALS plot, multiple occurrences of the digits 5 and 9 suggest trying either. After a coin toss, we select digit 9 as the new target and return to step 2.

Step 2. Find ALS’s containing 9 as the target digit and any other restricted-common digit.
Returning now to c1, we note that bivalue cells r16c1 quickly yield ALS “k” (9=82)r16c1. Similarly, c4’s bivalue cells r29c4 immediately produce ALS “m” (9=52)r29c4. We move again to step 3.

Step 3. The updated ALS plot now becomes:

Code: Select all

8h2k 7g . | .    . .  | .  .  .
.    .  . | 5f2m . .  | .  .  5b
1j   .  . | 7f   . .  | .  .  1a
----------+-----------+-----------
.    .  . | .    . .  | .  .  7abc
.    9g . | .    . 7e | 7d 4d .   
9ik  .  . | .    . .  | .  .  .
----------+-----------+-----------
7hij .  . | .    . 5e | .  .  .
.    .  . | .    . .  | .  .  .
.    .  . | 9m   . .  | .  .  9c  
Step 4. Look for new weak links.
One can easily spot 9c and 9m in r9, as well as 5f and 2m in cell r2c4, and finally 8h and 2k in cell r1c1.

Step 5. Develop grouped AIC’s and check for possible eliminations.
In abbreviated notation, weak link 9c and 9m, along with 5f and 2m, provide
7c = 9c – 9m = 2m – 5f = 7f => r4c4 <> 7.
Recall that this elimination was done previously (as the very first example) using a 2-node grouped AIC. That AIC, however, depended on ALS “b” (7=145)r234c9, which might very well have been missed or otherwise excluded for some reason in the original ALS search sequence. The above AIC therefore provides an alternate (albeit longer) path for the same elimination.
The grouped-AIC notation for the longer chain is
(7=1459)r2349c9 – (9=52)r29c4 – (5=2347)r23c45 => r4c4 <> 7.
Close inspection here reveals that the last two ALS’s in the chain share the common cell, r2c4.
[Edit: The elimination is valid, but the grouped AIC may be improperly formed. See this link for a discussion of the issues. This paragraph's original ALS-XY-Wing-rule example has been withdrawn because it violated the common-cell rule.]

The other new ALS, (9=82)r16c1 (letter “k”), can be used with the old weak link, 9g and 9k, to yield
7g = 9g – 9k = 2k => r1c2 <> 2.
The grouped-AIC notation is
(7=23589)r12459c2 - (9=82)r16c1 => r1c2 <> 2.
This chain illustrates something not seen so far...namely, a strong-inference link between two different digits (7g and 2k) that both belong to the same house, and thereby leads to the indicated elimination.

Step 6. Visually inspect the puzzle grid for a bivalue cell whose two candidates are the same as those of any ALS in the current ALS plot (bivalue cell and ALS should not reside in the same house).
We now notice that the two candidates (2 and 9) in bivalue cell r6c6 exactly match those in new ALS “k,” and there is an obvious weak link between (9)r6c6 and 9k. The weak link then allows us to immediately form the AIC,
(2=9)r6c6 – 9k = 2k => r1c6 <> 2.
The grouped-AIC notation is
(2=9)r6c6 – (9=82)r16c1 => r1c6 <> 2.
Note that this chain is equivalent to a simple XY-Wing (Type 2) with Z = 2. It is also equivalent to an ALS-XZ rule with X = 9 and Z = 2.

I’ll stop (mercifully) at this point in the solution procedure because the two or three eliminations produced thus far are probably sufficient to significantly advance the puzzle. Note also that I deliberately neglected the option in step 5 to update the puzzle grid after each elimination, and this would have obviously changed the ALS pool and the ALS plot. Except for the one UVWXYZ-Wing example, I opted to keep the original puzzle grid intact in order to illustrate the versatility of these ALS-based eliminations, which can be applied at any stage in solving a difficult puzzle.

Summary:
For one sample puzzle, at least, this simplified approach to (manually) finding ALS-based eliminations seems to work quite well. Its obvious advantages include a much reduced ALS pool and a straightforward, methodical way to find and exploit (via an ALS “plot”) the weak links between those ALS’s. The reduced-pool ALS’s are relatively few in number and easy to find, so there is a minimum expenditure of time and effort. Note as a bonus that the ALS plot itself may be helpful as an adjunct to any other solution technique that can utilize those strong-inference links.

Reference Material:
Myth Jellies' Alternating Inference Chains
http://www.sudoku.com/boards/viewtopic.php?t=3865

Ron Moore’s Grouped AICs and Rings
http://www.sudocue.net/forum/viewtopic.php?t=672

bennys’ ALS Rules
http://www.sudoku.com/boards/viewtopic. ... &highlight

Sudopedia
http://www.sudopedia.org/wiki/Main_Page

Questions, comments and suggestions are always welcome!
Post Reply