Sudtyro Hooked
Joined: 16 Jan 2007 Posts: 49

Posted: Fri Jun 29, 2007 1:34 pm Post subject: 5/20/07 Nightmare...reducedpool ALS's 


This post is the result of a first effort to simplify the process of finding ALSbased 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 stronginference 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 strongonly 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 N1 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 earlyon how to visually combine (patternmatch) a bivalue cell with a 2cell ALS to form either an XY or an XYZWing, and this technique has been extended to combine that bivalue cell with a 3cell ALS (WXYZWing) or with any Ncell ALS (...VWXYZWing). Each of these “NWings” comprises one bivalue cell weakly linked to an Ncell ALS to form a 2node grouped AIC equivalent to an ALSXZ rule. Bivalue cells will therefore be treated differently than other ALS’s and used only to form the “NWings.”
The allowed elimination strategies are limited to a single item:
1. Develop grouped AIC’s using only the reducedpool 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 singledigit 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 restrictedcommon 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 (stronginference link) between the target and restrictedcommon 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 26, 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 restrictedcommon 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: 

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 ALSbased eliminations.
Step 1. Select an initial target digit.
A review of the unresolved singledigit 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: 
. 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 restrictedcommon 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 textbased version of the current ALS plot might appear as shown below, where two occurrences of the same letter denote a stronginference link between the indicated digits. Each ALS uses a different letter.
Code: 
. . .  . . .  . . .
. . .  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 groupedAIC notation is
(7=145)r234c9 – (5=2347)r23c45 => r4c4 <> 7,
which is equivalent to an ALSXZ 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: 
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 groupedAIC notation is
(7=41)r34c9  (1=2897)r1367c1 => r7c9 <> 7,
which is again equivalent to an ALSXZ 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 groupedAIC notation is
(7=9)r5c6 – (9=23687)r12459c2 => r1c6 <> 7.
Note that this chain is equivalent to a UVWXYZWing (variant) with U = 9 and Z = 7. It is also equivalent to an ALSXZ 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 restrictedcommon 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 restrictedcommon 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: 
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 2node 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 groupedAIC 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 ALSXYWingrule example has been withdrawn because it violated the commoncell 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 groupedAIC notation is
(7=23589)r12459c2  (9=82)r16c1 => r1c2 <> 2.
This chain illustrates something not seen so far...namely, a stronginference 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 groupedAIC notation is
(2=9)r6c6 – (9=82)r16c1 => r1c6 <> 2.
Note that this chain is equivalent to a simple XYWing (Type 2) with Z = 2. It is also equivalent to an ALSXZ 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 UVWXYZWing example, I opted to keep the original puzzle grid intact in order to illustrate the versatility of these ALSbased 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 ALSbased 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 reducedpool 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 stronginference 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.php?t=2510&highlight
Sudopedia
http://www.sudopedia.org/wiki/Main_Page
Questions, comments and suggestions are always welcome! 
