Sept 4 Nightmare

[Ron Moore]

Generally I found the ALS Nightmares very difficult, but solvable. I want to comment on the Sept 4 Nightmare, as I found a somewhat simpler solution than what Sudocue found.

Code: Select all

.-----------------.------------------.------------------.
|  1256  8   A15   | 26   59   7     | #129    4    3   |
| #126   7    4    | 268  3    689   |  1289  B18   5   |
| A25    3    9    | 248  458  1     | B278   B78   6   |
:------------------+-----------------+------------------:
|  39    69   17   | 36   18    5    |  178    2    4   |
|  15    56   2    | 4678 1478  468  |  3      1568 9   |
|  8     4    1357 | 9    12    236  |  157    1567 17  |
:------------------+-----------------+------------------:
|  7     25   35   | 1    248   2348 |  6      9    28  |
|  4     29   8    | 37   6     29   |  157    1357 17  |
|  39    1    6    | 5    789   289  |  4      37   28  |
'------------------'-----------------'------------------'

At this point in the solution Sudocue found two fairly large ALS's in R12348C4 and {R7C5,R8C6,R9C5,R9C6}. I would never have seen this. I found a different ALS reduction with smaller sets, which Sudocue actually found later in its solution (after another ALS reduction with large sets!). The sets are marked above, with cells prefixed with A {r1c3, r3c1} and B {r2c8, r3c7, r3c8}. 2 is the "restricted common" candidate, causing elimination of the candidate 1 at the two cells prefixed with #.

This immediately makes available another "relatively" simple ALS reduction:

Code: Select all

.------------------.-------------------.-----------------.
|  1256  8    15   | B26    59    7    | 29     4    3   |
| A26    7    4    | B268   3    #689  | 1289   18   5   |
| A25    3    9    | B248  B458   1    | 278    78   6   |
:------------------+-------------------+-----------------:
|  39    69   17   |  36    18    5    | 178    2    4   |
|  15    56   2    |  4678  1478  468  | 3      1568 9   |
|  8     4    1357 |  9     12    236  | 157    1567 17  |
:------------------+-------------------+-----------------:
|  7     25   35   |  1     248   2348 | 6      9    28  |
|  4     29   8    |  37    6     29   | 157    1357 17  |
|  39    1    6    |  5     789   289  | 4      37   28  |
'------------------'-------------------'-----------------'

Set A is r23c1, set B is {r123c4, r3c5}, and 5 is the "restricted common" candidate, causing elimination of candidate 6 at the cell prefixed with #. After this, only simple eliminations are needed to complete the solution. Sudocue eventually found this same elimination using slightly different sets.

All told, Sudocue used 4 ALS reductions, two of them with quite large sets, and an empty rectangle starting from the initial configuration above. This leads me to ask about the order in which Sudocue searches for ALS reductions. Let me say that an algorithm to search for all possible ALS sets which produce eliminations seems quite difficult to me, so in any case I'm impressed with this recently added feature.

Ron Moore

[David Bryant]

Hi, Ron!

I had a lot of fun with the "ALS" week. I'm still trying to understand how to spot the useful "ALS"s in a puzzle. I was able to solve all seven of the puzzles by using "double-implication chains", which I think are in many cases the same thing as "almost locked sets". Let me explain.

I started from the position you illustrated.

Code: Select all

.-----------------.------------------.------------------.
|  1256  8    15B  | 26   59    7    |  129    4    3   |
|  126   7    4    | 268  3     689  |  1289   18A  5   |
|  25*   3    9    | 248  458   1    |  278A   78A  6   |
:------------------+-----------------+------------------:
|  39    69   17   | 36   18    5    |  178    2    4   |
|  15    56   2    | 4678 1478  468  |  3      1568 9   |
|  8     4    1357 | 9    12    236  |  157    1567 17  |
:------------------+-----------------+------------------:
|  7     25   35   | 1    248   2348 |  6      9    28  |
|  4     29   8    | 37   6     29   |  157    1357 17  |
|  39    1    6    | 5    789   289  |  4      37   28  |
'------------------'-----------------'------------------'

I considered the result of setting r3c1 = 2, and also of setting r3c1 = 5.

A. r3c1 = 2 ==> {7, 8} pair in r3c78 ==> r2c8 = 1
B. r3c1 = 5 ==> r1c3 = 1

So we can eliminate "1" from r2c1 and from r1c7 -- this is the same result you obtained with the "ALS XZ rule". Now the grid looks like this.

Code: Select all

.-----------------.------------------.------------------.
|  1256A 8    15   | 26A  59AB  7    |  29+    4    3   |
|  26A   7    4    | 268+ 3     689A |  1289   18   5   |
|  25*   3    9    | 248  458   1    |  278    78   6   |
:------------------+-----------------+------------------:
|  39A   69   17   | 36A  18    5    |  178    2    4   |
|  15    56   2    | 4678 1478  468  |  3      1568 9   |
|  8     4    1357 | 9    12    236  |  157    1567 17  |
:------------------+-----------------+------------------:
|  7     25+  35A  | 1    248   2348 |  6      9    28  |
|  4     29   8    | 37   6     29+  |  157    1357 17  |
|  39A   1    6    | 5    789B  289  |  4      37   28+ |
'------------------'-----------------'------------------'

Since I'd had good luck with it already, I stayed with r3c1 ...

First, I was able to decide where all the "2"s would appear if r3c1 = 2.

A1. r3c1 = 2 ==> r2c1 = 6 ==> {1, 5} pair in r1c13 ==> r1c5 = 9
A2. (r2c1 = 6 & r1c5 = 9) ==> r2c6 = 8 ==> r2c4 = 2 ==> r1c7 = 2
A3. r2c4 = 2 ==> r1c4 = 6 ==> r4c4 = 3 ==> r4c1 = 9 ==> r9c1 = 3 ==> r7c3 = 5 ==> r7c2 = 2
A4. r7c2 = 2 ==> r9c9 = 2 ==> r8c6 = 2

Next I traced out what would happen if r3c1 = 5:

B. r3c1 = 5 ==> r1c5 = 5 ==> r9c5 = 9 ==> r8c6 = 2

So there has to be a "2" at r8c6, and this is also enough to solve the puzzle.

I think that the "DIC" technique and the "ALS XZ rule" are often equivalent, as in the first chain illustrated above. Since I'm already pretty familiar with the "DIC" technique, I'm probably going to have trouble thinking of it in "ALS" terms. dcb

[Ron Moore]

David,

I'm like you in that it's still difficult for me to identify really useful "ALS XZ rule" configurations. For the simpler configurations (meaning the ones that I have some chance of spotting in practice), in most cases in one or the other of the two sets, there will be only one occurrence of the restricted common candidate X, in a single bi-valued cell.

For example, in the first configuration I mentioned, the restricted common digit X (2 in this case) appears in set A only in cell r3c1. As I'm sure you realize, your examination of the two mutually exclusive cases "r3c1 = 2" and "r3c1 = 5" is equivalent, in the terminology of the "ALS XZ rule," to examining the two mutually exclusive cases "X (digit 2) is in set A--and therefore not in set B" and "X is not in set A."

In more complex "ALS XZ rule" configurations, the restricted common digit might appear in mutliple cells in each of the two sets, so you could not in effect restate the ALS logic in terms of the possible values of a single cell. The rub, of course, is that those configurations are more difficult to spot.

I don't remember specifics at this point, but I do recall having to resort to some fairly lengthy chain type arguments in my solution to some of the other ALS theme puzzles. I ran the latest Sudocue solver on them to see if I had overlooked some straightforward ALS eliminations, and in most cases I did not consider them straightforward. Maybe this will come with practice.

As I mentioned in a post on another thread, over time I've read many of your posts on the forum. I hope you don't mind my asking about some of the terms I've seen you use. Am I correct that "double implication chains" are two separate chains of inference, which arise from separately considering the cases that either of two mutually exclusive possibilities is true, which lead to a common conclusion? That may not have come out clearly. In other words, is it basically the idea that if "A implies B" and "not A implies B" then "B is true"? I realize the term is not yours, but the first few times I saw it I missed the basic idea that the "double" applies to "chains" rather than "implications" (there are two chains with a common implication). Does the term only apply to considering the two possible values of a bi-valued cell, as in this case, or would it apply to the case where only two possible locations for a digit exist in some house, and either placement leads to a common conclusion?

I've used the technique (like many intermediate or higher level Sudoku players, I'm sure) but without attaching a specific name to it. By extension I occasionally use triple or even quadruple implication chains, in the cases of 3-valued or 4-valued cells. Obviously, in these cases, some of the chains must lead very quickly to the desired conclusion or I'll lose interest in pursuing all the possibilities.

I've also seen you use the term "n-star constellation." Is this simply the set of n cells (including the target cell, where the conclusion is drawn) in the double implication chains arising from consideration of the two possible values of one of the cells in the set?

Ron Moore

[David Bryant]

Hi, Ron!

I'm probably not careful enough with my terminology. I think of a double-implication chain as being one of two things.

A. A set of two chains of inference that can be drawn by considering each of two possibilities in a "base" cell. Usually the "base" cell can only take on two values, but sometimes I've been able to reason with a 3- or 4-valued cell using just two states: "a" or "not a".

B. A set of two chains of inference that can be drawn by considering just one possibility in a "base" cell. In this situation there are two different chains leading out of the one cell, generally in different directions (one might move up a column, then across a row -- the other might move across a row first).

To be useful, the two chains of inference must intersect each other somewhere. The intersection may produce a contradiction, or it may eliminate a single digit somewhere, or it may actually determine a value in a cell that's remote from the "base" cell.

Here are a couple of links to the discussions in which I first learned about this technique.

5-star constellation
4-star constellation

I learned about this stuff from Andrei Stoffel ("someone_somewhere"), who used to contribute a lot to the "Daily Sudoku" forum. Later I learned that people had started using different terminology over on the "Sudoku.Com" forum, at roughly the same time that Andrei and I were hashing this stuff out for ourselves. So that's why my vocabulary is warped ... we were inventing our own terms, and they aren't the ones the Sudoku programming community eventually settled on for this kind of technique. For instance, the "XY" chain looks to me like a special type of "DIC" that leads to elimination of a single digit ("x or y" in base cell -- assuming "y" leads to an "x" somewhere else, and the intersection of a column and row permits the elimination). dcb

[Ruud]

Let me throw in my 2 Eurocents,

The "formal" definition of a DIC (double implication chain) describes it as a single chain that works in 2 directions. This can only occur when:

1. The chain is completely built with strong links, or
2. The chain uses alternating inference.

Examples of type 1 are:
- Simple coloring
- Remote locked pairs
- XY-Chains, which only contain bivalue cells, with bilocation links between them.

Examples of type 2 are:
- Fishy cycles
- Grouped coloring
- Nice loops
- AIC (Alternating Inference Chains)

The double implication plays on the relationship between the first and last nodes in the chain. For a chain A ... Z, there is a relation between A and Z, which is passed on through the chain.

There are 4 possibilities:

1. When A is TRUE, Z is TRUE and when Z is TRUE, A is TRUE (useless)
2. When A is TRUE, Z is FALSE and when Z is TRUE, A is FALSE
3. When A is FALSE, Z is FALSE and when Z is FALSE, A is FALSE (useless)
4. When A is FALSE, Z is TRUE and when Z is FALSE, A is TRUE

The 4th type is what we use, because any candidate that can see both A and Z can be eliminated. An XY-Wing is a short type 4 DIC.

Single implication chains only work in a single direction, so A has effect on Z, but Z has no effect on A.

Examples are:
1. Forcing chains (old school)
2. Nice loops with embedded (AUR's and ALS's)

A chain becomes a loop when A equals Z. Now type 2 is very productive, because it can be used to show an inconsistency, resulting in the elimination of the start/end node.

All these different names essentially represent the same types of chains, sometimes with a few limitations (remote locked pairs, XY-chain), with a specific notation system (Nice Loops, AIC's), or embedded patterns (AUR, ALS)

I will update my Glossary, so that these terms also have a proper definition. I like to know whether there are other aliases that I've missed.

cheers,
Ruud