I get the idea behind the ALS xz-rule, but how do I actually find the pattern in a given puzzle?
This post is intended as the beginning to an answer of that question. It is unlikely that the advanced reader will find anything new in this post. Most of the work is traceable to the important original work of bennys and aeb, only the organization is mine. I make no claims that finding these patterns will become easy after reading this. It is only after a considerable amount of time that I have learned to recognize the patterns that might lead to ALS style deductions.
I've chosen to describe situations using subset counting instead of the ALS xz-rule because I think that it is the more natural and general language and, frankly, it is the technique I personally use. However, when appropriate, I will try to rephrase deductions into the form of the ALS xz-rule to give old-schoolers a frame of reference.
Subset Counting
Let me begin by briefly describing subset counting. First, choose any set of cells of the sudoku. We write down each of the possible candidates that could occur in any cell of our set. We then calculate the maximum number of times each of those candidates might occur in a solution. This process is best described by an example. Here is the one aeb used in his original thread:
- Code: Select all
. . . | . . . | . . .
. . . | . . * | . 79 789
. . . | . . . | . . 789
------------+-------------+------------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------------+-------------+------------
. . . | . . 37 | . . 79
. . . | . . . | . . .
. . . | . . 39 | . . .
In the above grid we pick 6 cells. The possible candidates are 3,7,8,9. Using the Sudopedia definition, a house is any row, column or block. We see that all of the 3's in our set lie in the same house (column 6), and hence the maximum numbers of times 3 can occur in our set (from now on to be called the max multiplicity of 3) is 1. The max multiplicity of 7 is 2 (say, r7c6=7, r2c8=7). The max multiplicity of 8 is 1 since all 8's are in the same house (box 3 or column 9). Finally, the max multiplicity of 9 is 3 since we could have r2c8=9, r7c9=9 and r9c6=9. If we add up the max multiplicites, we get 7. That is there are at most 7 candidates (counting multiplicites) available for the 6 cells. Assume now that we could somehow decrease the number of candidates for these 6 cells to 5. Then we would have a problem. You can't fill 6 cells with 5 numbers. But this is exactly what would happen if r2c6=9. For then the only cells in our set that could be 9 are r3c9 and r7c9, which are both in the same house. Therefore we would reduce the max multiplicity of 9 to 1. The sum of our max multiplicities would then be 5 and we would have a contradiction. Therefore, r2c6<>9.
Easier examples
I would like to work with some very restricted max multiplicities to keep things relatively painless. A set of n cells with n distinct candidates where the max multiplicity of each candidate is 1 will be called a 1-set. A set of n cells with n distinct candidates where the max multiplicity of all but one candidate is 1 and the remaining candidate has max multiplicity 2 will be called a (1,2)-set. If we would like to specify which candidate has max multiplicity 2, we will write that a set is a (1,2)<a>-set where a is the exceptional candidate. From here on, all of the example will be of 1-sets and (1,2)-sets. All of our deductions will follow from the next theorem of aeb.
1 Theorem (aeb)
(a) Let S be a 1-set and let x be a candidate in S. Any cell outside of S that sees every instance of x in S cannot be x.
(b) Let S be a (1,2)<x>-set. Any cell outside of S that sees every instance of x in S cannot be x.
Example
- Code: Select all
. . . | . . . | . . .
* * * | 79 * * | * * 79
. . . | . . . | . . .
The above set of two cells is a 1-set since the two candidates 7 and 9 can each only occur once. By Theorem 1(a), 7 and 9 can be removed from every cell in row 2 outside of our set. Of course, this is just a naked pair. In fact, any naked set (e.g., naked triple, naked quad, etc.) is just a 1-set. However, not every 1-set is a naked set. The most startling example of this is the Sue De Coq (see also Obi-Wahn's thread Distributed Disjoint Subsets for a treatment related to mine). Another example is what I would call a simple continuous xy-chain. This is a continuous xy-chain that uses each label at most once.
Example
- Code: Select all
. . . | . . . | . . *
. . . | . . . | . 79 *
. . . | . . . | . . 89
------------+-------------+------------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------------+-------------+------------
. . . | . . . | . * 78
. . . | . . . | . * .
. . . | . . . | . * .
The above set is a (1,2)<7>-set (the reader should verify this claim). By theorem 1(b), we can eliminate 7 from the cells outside of S that see every 7 in the set. These cells are denoted by * above. Of course this is just a standard xy-wing.
[ALS xz-rule: A={7,8,9} on r2c8, r3c9, B={7,8} on r7c9, x=8, z=7]
More generally, any simple discontinuous xy-chain is also a (1,2)-set with the exceptional candidate being the discontinuous link. The next question is, can we add candidates to any of the above 3 cells and preserve the type. For instance, if we add an 8 to r2c8, then the max multiplicity of 8 becomes 2, so we would no longer have a (1,2)-set. Similarly, we cannot add a 9 to r7c9. On the other hand, if we add a 7 to r3c9, the max multiplicity of 7 remains 2. So we again get a (1,2)-set:
- Code: Select all
. . . | . . . | . . *
. . . | . . . | . 79 *
. . . | . . . | . . 789
------------+-------------+------------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------------+-------------+------------
. . . | . . . | . . 78
. . . | . . . | . . .
. . . | . . . | . . .
Applying Theorem 1(b) again, we see that r1c9,r2c9<>7. But this is just an xyz-wing.
[ALS xz-rule: A={7,8,9} on r2c8, r3c9, B={7,8} on r7c9, x=8, z=7 (Notice that this is exactly the same as for the above xy-wing!)]
This shows that there is an easy way to build new patterns from existing ones, namely by searching for ways of adding candidates without changing the multiplicities. It also suggests that if there are no such ways, then a new pattern will require adding more cells. As we have exhausted the 3 cell pattern, our next example will examine 4 cells.
Example
In this example, we explore the WXYZ-wing with an example coming from Jeff's thread Extension of xyz-wing.
- Code: Select all
----------+----------+----------
. . . | . . . | . . .
. 12 . | . . 23 | 34 * *
* * * | . . . | . 14 .
----------+----------+----------
The above set is a (1,2)<1>-set (it is also a simple discontinuous xy-chain) and so we can eliminate 1 from the *'d cells.
[ALS xz-rule: A={1,2,3,4} on r2c267, B={1,4} on r3c8, x=4,z=1]
Let us try to add candidates into our cells. As our set only contains two rows, the max multiplicity of 1 could never be more than 2, so we are free to add a 1 to every cell. Now, 2,3,4 all have max multiplicity 1 and we want to keep it that way. So we should not add a 2 or 3 to r3c8, nor a 4 to r2c2 or r2c6. The best we can do therefore is to obtain the following (1,2)<1>-set.
- Code: Select all
----------+----------+----------
. . . | . . . | . . .
. 123 . | . . 123 |1234 * *
. . . | . . . | . 14 .
----------+----------+----------
[ALS xz-rule: A={1,2,3,4} on r2c267, B={1,4} on r3c8, x=4,z=1 (Note again that this is the same deduction as above!)]
The cost is that we do not have as many deductions, but we do have a less restrictive pattern, a wxyz-wing. Of course, one does not have to restrict one's self to looking at (1,2)-sets of size 4, and this is why they have vwxyz-wings, uvwxyz-wings, etc.
How can I use this?
It is probably best to show you with examples. In a recent thread, Mike Barker suggested that there was a wxyz-wing that solved puzzle #4 from the top95 The point at which we were examining the puzzle was:
- Code: Select all
*--------------------------------------------------------------------*
| 4 8 7 | 3 12 12 | 56 9 56 |
| 59 359 39 | 6 48 48 | 2 7 1 |
| 1 2 6 | 57 9 57 | 3 8 4 |
|----------------------+----------------------+----------------------|
| 7 34 5 | 89 348 489 | 1 6 2 |
| 69 13469 349 | 2 1346 57 | 8 34 57 |
| 28 1346 28* | 57 1346 14 | 57 34 9 |
|----------------------+----------------------+----------------------|
| 58 45 1 | 48 7 6 | 9 2 3 |
| 3 67 89* | 1 28 289 | 4 5 67 |
| 269- 4679- 24(9)* | 49* 5 3 | 67 1 8 |
*--------------------------------------------------------------------*
As there are generally tons of patterns available for bivalue candidates, I focused on these. What stood out to me was the almost simple discontinuous xy-chain in {r6c3,r8c3,r9c3,r9c4}. If only that lousy 9 wasn't in r9c3, I would have my xy-chain and would be able to eliminate 9 from r9c1, r9c2 and r8c6. Nevertheless, we still can make some deductions because of subset counting. You see, our set is a (1,2)<9>-set with or without the 9 in r9c3. Therefore, we may remove 9 from all cells that see every cell in our set that contains a 9. So we still can eliminate 9 from r9c1, r9c2. Note that we just found a wxyz-wing.
[ALS xz-rule: A={2,4,8,9} on r689c3, B={4,9} on r9c4, x=4, z=9]
Here is an example from the zoo (thanks again to Mike Barker)
- Code: Select all
9.7..4......6..8.......9.2.......9....3....42.6...25...9.1..3.5.5...81..6......7.
- Code: Select all
*-----------------------------------------------------------------------------*
| 9 1238 7 | 2358 12358 4 | 6 135 13 |
| 1345 1234 145 | 6 12357 1357 | 8 1359 1379 |
| 1358 138 6 | 3578 13578 9 | 4 2 137 |
|-------------------------+-------------------------+-------------------------|
| 12458 7 12458 | 3458 13458 135 | 9 1368 1368 |
| 158 18 3 | 589 15689 156 | 7 4 2 |
| 148 6 9 | 3478 13478 2 | 5 138 138 |
|-------------------------+-------------------------+-------------------------|
| 2478* 9 248* | 1 2467 67* | 3 68* 5 |
| 2347 5 24 | 23479 234679 8 | 1 69 469 |
| 6 1348 148 | 3459 3459 35 | 2 7 489 |
*-----------------------------------------------------------------------------*
Again, I start with bivalued cells, and notice that if it wasn't for a few pesky candidates (namely, the 2 and 8 in r7c1 and the 2 in r7c3), I would have a simple continuous xy-chain in row7 and hence a 1-set! Oh wait, that would just be a naked quad. To help you visualize, this is what the grid would look like if it wasn't for those extra candidates:
- Code: Select all
|-------------------------+-------------------------+-------------------------|
| 47* 9 48* | 1 2467- 67* | 3 68* 5 |
| 2347 5 24 | 23479 234679 8 | 1 69 469 |
| 6 1348 148 | 3459 3459 35 | 2 7 489 |
*-----------------------------------------------------------------------------*
Now let's work our magic. In a 1-set, we are allowed to add candidates as long as they don't change the max multiplicity. So we can add an 8 to r7c1, which would give us back our original grid minus the missing 2's. If we add back the two's though, we will have 5 distinct candidates in 4 cells. So we need to add another cell. The one which looks to do the least amount of damage is r8c3 since it only contains 2 and 4 and the 4 sees every other instance of 4 in our set. By doing this we now again have a 1-set, and so we can add the original 2's back since they both see r8c3. But let's not stop there! We could also add an 8 to r7c6 as well as a 6 to r7c1 and r7c3 and a 7 to r7c3 and r7c8. In total if our grid looked like
- Code: Select all
|-------------------------+-------------------------+-------------------------|
| 24678* 9 24678* | 1 2467- 678* | 3 678* 5 |
| 2347- 5 24* | 23479 234679 8 | 1 69 469 |
| 6 1348- 148- | 3459 3459 35 | 2 7 489 |
*-----------------------------------------------------------------------------*
we would still have a 1-set. We could then eliminate 2 from r8c1, 4 from r8c1,r9c2 and r9c3, 6 from r7c5 and 7 from r7c5. In this case adding all of the candidates in has not actually changed the ultimate eliminations.
[ALS xz-rule: A={2,4,6,7,8} on r7c1368, B={2,4} on r8c3, x=2,z=4
ALS xz-rule: A={2,4,6,7,8} on r7c1368, B={2,4} on r8c3, x=4,z=2]
The Moral
There are a lot of ALS style reductions that do not fit into the form I've presented. In a sense, you might call that for which I'm looking almost xy-chains. The way I go about finding things is by looking for chains of bivalued cells and observing the obstructions to them being xy-chains. If all of the obstructions are 'nice', then I've found the right set. Usually 'nice' means that the extra candidate sees every other instance of itself in my set. Otherwise, I tweak things by adding or removing cells until either I find the right combination or I give up. More often than not I will take the latter route. Experience helps me know sooner when to give up.
In any case, hopefully this presentation helps somebody understand a little better how to manually spot ALS style reductions and perhaps it will inspire others to share their tricks, especially for the more complicated set-ups.
