
SudoCue Users A forum for users of the SudoCue programs and the services of SudoCue.Net

View previous topic :: View next topic 
Author 
Message 
Ron Moore Addict
Joined: 13 Aug 2006 Posts: 72 Location: New Mexico

Posted: Tue Sep 05, 2006 7:55 pm Post subject: Sept 4 Nightmare 


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

Back to top 


David Bryant Gold Member
Joined: 20 Jan 2006 Posts: 86 Location: Denver, Colorado

Posted: Wed Sep 06, 2006 2:24 am Post subject: A "DIC" solution 


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 "doubleimplication 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:  ....
 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:  ....
 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 

Back to top 


Ron Moore Addict
Joined: 13 Aug 2006 Posts: 72 Location: New Mexico

Posted: Sun Sep 10, 2006 12:49 am Post subject: 


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 bivalued 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 Aand 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 bivalued 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 3valued or 4valued 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 "nstar 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 

Back to top 


David Bryant Gold Member
Joined: 20 Jan 2006 Posts: 86 Location: Denver, Colorado

Posted: Mon Sep 11, 2006 12:47 am Post subject: "DoubleImplication Chains" 


Hi, Ron!
I'm probably not careful enough with my terminology. I think of a doubleimplication 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 4valued 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.
5star constellation
4star 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 

Back to top 


Ruud Site Owner
Joined: 30 Dec 2005 Posts: 601

Posted: Mon Sep 11, 2006 3:12 am Post subject: 


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
 XYChains, 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 XYWing 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, XYchain), 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 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
