SudoCue Users

[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.

[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.

[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
_________________
“If the human brain were so simple that we could understand it, we would be so simple that we couldn't.” - Emerson M Pugh