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

View previous topic :: View next topic 
Author 
Message 
Ruud Site Owner
Joined: 30 Dec 2005 Posts: 601

Posted: Sun Dec 31, 2006 4:20 pm Post subject: Curious new move 


Here is a curious move that I found in a SudokuX, but it is not a move that would be restricted to this variant.
Consider the following SudokuX puzzle:
Code:  . . .. . .. . .
3 . .5 . 7. . 2
. . .. . .. . .
++
4 6 .2 . 9. 7 8
. 9 .1 . 8. 4 .
1 2 .7 . 5. 6 3
++
. . .. . .. . .
8 . .9 . 4. . 7
. . .. . .. . . 
The puzzle only requires simple moves upto this point:
SudoCue continues with an XWing and several coloring moves, but I found a shortcut that bypasses all these advanced moves.
r8c7 must be 5 or 6, so either r8c2=5 or r8c3=6 (due to the strong links)
r7c1 must also be 5 or 6. We can eliminate digits 5 (and 6 if there were any) from the remaining cells in nonet 7. This isolates a single 2 in r9c1 which breaks the puzzle.
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 


Para Yokozuna
Joined: 08 Nov 2006 Posts: 384 Location: The Netherlands

Posted: Tue Jan 02, 2007 7:57 pm Post subject: Same move in Dec 20th Nightmare 


Code: 
8 . .. . .. . .
. 7 .. . 2. 9 .
. 1 23 . .. 6 .
++
. . 6. . 72 . 5
. . .. . .. . .
5 . 74 . .6 . .
++
. 6 .. . 59 4 .
. 9 .8 . .. 1 .
. . .. . .. . 3

A few basic steps upto this
Code: 
....
 8 345 349  1679 14679 1469  1347 25 1247 
 6 7 345  15 1458 2  13458 9 148 
 49 1 2  3 45789 489  4578 6 478 
:++:
 1349 348 6  19* 1389 7  2 38 5 
 139 238 1389  12569 1235689 13689  14 7 149 
 5 238 7  4 12389* 1389*  6 38 19* 
:++:
 1237 6 138  127 1237 5  9 4 278 
 2347 9 345  8 2347 34  57 1 6 
 1247 458 148  12679 124679 1469  78 25 3 
''''

Either R6C5 and R6C6 has to contain 1 or 9. Combined with R4C4 you can eliminate 1 and 9 from the other squares in box 5.
Sudocue makes the same eliminations with 5 ALSxz patterns.
Para 

Back to top 


Ruud Site Owner
Joined: 30 Dec 2005 Posts: 601

Posted: Tue Jan 02, 2007 9:46 pm Post subject: 


Thanks for the additional example.
Both this puzzle and my original example have a complementary SueDeCoq move. In this puzzle, r6c28 are used in combination with r4c4. I'm trying to figure out whether these moves are always complementary or whether they can also exist separately.
The technique has been discovered before  and forgotten  the name is Almost Locked Candidates or ALC.
Ruud 

Back to top 


Para Yokozuna
Joined: 08 Nov 2006 Posts: 384 Location: The Netherlands

Posted: Wed Jan 03, 2007 4:50 pm Post subject: SuedeCoq vs ALC 


Just checked what SuedeCoq is. As i figure SuedeCoq is what i did in my post of Jan 2nd, right? > http://www.sudocue.net/forum/viewtopic.php?t=474
There are no ALC's in that one, right?
Para 

Back to top 


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

Posted: Wed Mar 14, 2007 12:38 am Post subject: Two ALS's With Two Restricted Common Candidates 


[Summary of edits, 14 Mar 2007: The acknowledgment (immediately following) was added; the logic for the basic results of this approach was reworded, hopefully more clearly; another example position added at end of post.]
Acknowledgment. After my first submission of this post I found an interesting thread on the Sudoku players forum (here), in which Bob Hanson discusses the positions I describe here, with the same conclusions, all expressed more tersely  see item IV in his post in that thread. His item IV (generalized) is also interesting. I believe this addresses the structure I've called an "ALS ring" in one of my posts, but there may be more there than I had realized.
*********************************************************
I would like to point out yet another way of looking at the type of eliminations illustrated in this thread. I also have some commments on Sue de Coq in the Sudocue solver and the respective Sudopedia page.
First a few basics, which most if not all readers will already know:
An Almost Locked Set (ALS) is a set of N cells all lying in some common house, which contains exactly N+1 distinct digits as candidates. (As an aside, there may be more than one house which contains all cells of an ALS. Indeed, a single bivalued cell is an ALS which is contained in three different houses.)
A fact which is used in some way or another in ALS arguments is this:
If an ALS does not contain one of its candidate digits, then it must contain every other of its candidate digits (in some unspecified order).
If A and B are two ALS's which have one or more common candidate digits, then such a shared digit, say x, is termed "restricted common" if x cannot be simultaneously placed in sets A and B; or equivalently, if every cell in A containing x as a candidate sees every cell in B containing x as a candidate.
Getting down to specifics, I'll start with Para's example from a related thread (here) because it has a nice symmetry to it: Code: 
....
 128 28 5  147 347 1237  78 6 9 
 7 3 4  8 6 9  12 A25 125 
 6 9 128  157 57 127  78 4 3 
:++:
 238 4 2378  6 137 5  12 9 1278 
 5 78 3789  2 1379 4  6 378 178 
 239 1 6  79 8 37  5 237 4 
:++:
 389 5 3789  479 2 6  49 1 B78 
 4 6 12789 1579 579 178  3 A2578 2578 
 1289 278 12789 3 457 178  49 A2578 6 
'''' 
Here the sets marked with A and B in the diagram are ALS's.
ALS A contains cells r289c8, three cells with four candidates  2578
ALS B is the single cell r7c9, with two candidates  78
Now, set A must reduce to either a "257" or "258" naked triple, according as the value of r7c9 is 8 or 7, respectively. Of course, either triple eliminates digits 2 and 5 (if there were any) from other cells in column 8.
For readers familiar with using grouped chains (chains with ALS's as nodes), this Alternating Inference Chain (AIC) reflects this intuition:
(257=8)r289c8  (8=7)r7c9  (7=825)r289c8
What makes this work is that both digits 7 and 8 are "restricted common" digits for the two sets A and B. A restricted common digit for two ALS's can be used to weakly link between those sets in a grouped chain, as above. The chain uses one of the restricted common digits to weakly link from set A to B, then the other to weakly link back to set A.
I should only need to mention briefly that in the diagrammed position above, r7c9r89c8 is also an ALS in box 9 which will reduce to either a "278" or "578" naked triple, depending on the value of r2c8, and either triple will eliminate the 7 and 8 candidates in other cells in box 9. Or we can arrive at the same result by observing that since set A is an ALS, if it does not contain 7, it must contain 8 (and perforce, whichever one it is has to lie in r89c8, as these are the only cells in A containing 7 and/or 8 as a candidate). Thus this digit pairs up with r7c9, which must be 7 or 8, to eliminate the other 7 and 8 candidates in cells outside of A and B in box 9.
When I was learning how to use Almost Locked Sets in ALS XZ rule eliminations, I came across a few positions in which there were two "restricted common" digits for two ALS's, and I noted that several eliminations were sometimes possible in these positions. It was quite a while afterwards before I could characterize what was really going on, but eventually I came up with the following principle. If you wanted to give it a name, I suppose it could be called the "two ALS's with two restricted common digits" pattern. I'm not sure it really merits a name of its own, since it's really just an example of how ALS's can be used, once you're comfortable working with them. Everything here can be expressed in terms of grouped AIC's (with ALS's as nodes), as was done above, so if you can work with such chains then you've got this covered (along with several other techniques).
******************************************************************************************
Suppose A and B are two ALS's which share two "restricted common" candidate digits, say w and x. Let VA and VB denote the set of candidate digits in sets A and B, respectively. Then the following three conclusions can be drawn (not all are generally useful in any particular position):For any digit d in the set VA  {w,x}, d can be eliminated as a candidate from any cell not in A which sees all cells in set A containing d as a candidate.
Similarly, for any digit d in the set VB  {w,x}, d can be eliminated as a candidate from any cell not in B which sees all cells in set B containing d as a candidate.
The restricted common digit w can be eliminated from a cell not in A or B but which sees all cells in A and B containing w as a candidate, and similarly for x. At this point I'm probably just restating the obvious, but here's how the reasoning goes:
Since set A is an ALS, if it does not contain digit w then it contains every other digit in VA, in particular x. So A contains at least one of w, x, and similarly, so does B. Both cannot contain w, say, since w is restricted common, and similarly for x. So A contains exactly one of w, x, and B contains the other. From this the third conclusion stated above directly follows.
This also means that A must be lacking exactly one of w, x, so in either case it must contain all other of its digits, i.e., all digits in VA  {w,x}, and likewise B must contain all digits in VB  {w,x}. From this the first and second conclusions follow.
******************************************************************************************
Applying the principle to the above example, we can take
w = 7
x = 8
A = r289c8, VA = 2578, VA  {w,x} = 25
B = r7c9, VB = 78, VB  {w,x} = {empty}
So the first conclusion shows that each digit in VA  {w,x}, namely 2 and 5, can be removed from other cells in column 8; the second conclusion gives nothing in this case since VB  {w,x} is empty.
The third translates to the result that 7 and 8 can be eliminated from all cells outside of both A and B in box 9 (since all cells with candidates 7 and 8 in A and B lie in box 9).
Now, at this juncture I should point out that this principle is not the same as the Sue de Coq technique. However, in all examples I've seen of Sue de Coq usage, the same eliminations also can be derived using this simpler "two ALS's with two restricted common digits" idea. Let's take Para's example from earlier in this thread: Code: 
....
 8 345 349  1679 14679 1469  1347 25 1247 
 6 7 345  15 1458 2  13458 9 148 
 49 1 2  3 45789 489  4578 6 478 
:++:
 1349 348 6  A19 1389 7  2 38 5 
 139 238 1389  12569 1235689 13689  14 7 149 
 5 B238 7  4 B12389 B1389  6 B38 19 
:++:
 1237 6 138  127 1237 5  9 4 278 
 2347 9 345  8 2347 34  57 1 6 
 1247 458 148  12679 124679 1469  78 25 3 
'''' 
Here we can take A = r4c4 with VA = 19, B = r6c2568 with VB = 12389, w = 1, x = 9. In this case, only our third conclusion (elimination of restricted common digits) yields anything. Since all cells of A and B with digits 1 and/or 9 as candidates lie in box 5, that conclusion tells us that 1 and 9 can be eliminated from other cells in box 5. (By the way, Para, that was a nice observation. I found a less elegant way to proceed.)
Now let's consider the example given on the Sudopedia page for the Sue de Coq technique (here). I've shown only the relevant portion of the grid (rows 13).
Code:  ....
 1 29 7  259 6 28  A58 4 3 
 5 8 4  129 3 12  7 169 126 
 3 B29 6  12459 2489 7  B158 B159 B125 
.... 
As marked in the diagram, we can take set A = r1c7 with VA = 58, set B = r3c2789 with VB = 12589; and for the restricted common digits we use w = 5, x = 8. In this case there are no eliminations to be made from the digits in VA  {w,x} since that set is empty. There are several eliminations to be made from the digits in VB  {w,x} = {1,2,9}  in fact, all of the eliminations available from Sue de Coq in this particular case. Digit 1 can be eliminated from any cell, not in B, which sees all cells in B with 1 as a candidate (namely, r3c789). This yields the eliminations of 1 in r2c89 and r3c4. Digit 2 can be eliminated from any cell, not in B, which sees all cells in B with 2 as a candidate, so this yields the eliminations of 2 in r3c45, and similarly for digit 9. There are no eliminations to be made of the restricted common digits 5 or 8 in box 3, since no candidates for 5 or 8 exist outside of A and B in box 3. If there were, they could be eliminated using either approach.
Now let's tweak the position a bit, leaving set B as is, but making set A an ALS with 2 cells: Code: 
....
 1 2349 347  259 6 2348  A589 A589 347 
 5 8 347  129 349 12  347 169 1267 
 349 B29 6  12459 2489 7  B158 B159 B125 
.... 
I've changed several of the cells in an attempt to make the position somewhat realistic, and consistent with the new set A: A = r1c78, VA = 589. It probably is not consistent with the rest of the diagram (not shown), or there may be a simpler technique which can be used here. If so, for the sake of discussion please ignore those shortcomings. I'm just trying to illustrate a point, and to find a real life example would be impractical for me.
Since the new set A is an ALS, and 5 and 8 are still restricted common digits for sets A and B, all of the aforementioned eliminations of the digits in VB  {w,x} = {1,2,9} still hold. But now we have VA  {w,x} = {9}, so we can eliminate all 9's in cells not in A which see both of r1c78, in this case r1c24 and r23c8. Note that this position does not qualify as a "Sue de Coq" since the sectors r1c78 and r3c2 contain digit 9 as a common candidate.
Now I have to confess that it wasn't until recently that I understood what "Sue de Coq" was. When I started trying to learn intermediate and advanced techniques, I did see the term somewhere, but it was over my head at the time so I didn't pursue it. Now I've noticed in the past few months that the Sudocue solver has occasionally used Sue de Coq, and the term has appeared in this thread, of course, so I figured I ought to learn exactly what it was.
So I started with the brief help information that the Sudocue solver v2.2.0.0 gives (under Tools>Options>Solver) for the various supported techniques. This didn't help because *** comment to Ruud *** the information for Sue de Coq is incorrect, just an identical copy of the "2 string kite" information.
My next thought was to consult the Sudopedia page for Sue de Coq (here), but here also I found a problem. The following is a direct quote of the opening paragraph on that page. Quote: 
The Sue de Coq technique uses two intersecting sets A and B, where A is a set of N cells with N candidates in a line, B is a set of N cells with N candidates in a box, and the sets A  B and B  A have no common candidates. Candidates can be eliminated from the cells in the line that are not in A, and the cells in the box that are not in B. 
If you've read this quote, I'm sure I don't need to point out that "N cells with N candidates" can't be right, since that would make A and B locked (or naked) subsets in their respective houses and we wouldn't need to consider how they interact. Also, the use of "N cells" for both of sets A and B might be construed as saying that sets A and B have the same number of cells, but that is not a requirement. So I went to the referenced link to the Sudoku players forum (here), and guess what? I still don't understand Sue de Coq in its full generality. I think I do understand it in the "two sector" form, and the scope of the Sudopedia page is limited to this, so, if my understanding is correct, the description should read something like this:The Sue de Coq technique uses two intersecting sets A and B, where A is a set of cells in a line, and B is a set of cells in a box, such that: all candidate digits in A  B and B  A are also candidates in the intersection of sets A and B; A  B and B  A have no common candidates; and the number of cells in A union B equals the number of distinct candidate digits in A union B. Candidates can be eliminated from the cells in the line that are not in A, and the cells in the box that are not in B. (It's unfortunate that I used A and B as names for the 2 ALS's involved, since that usage conflicts with the usage here. Moreover, in the Sudoku players forum three sets  A, B, C  are used to define the positional constraints.)
I have looked at all the two sector Sue de Coq examples in this thread, and the Sudoku player's forum thread, and each of these positions can also be considered as a "two ALS's with two restricted common digits" pattern, with the same eliminations. Offhand, it seems like a fairly complex Sue de Coq pattern would be required to avoid classification under this pattern as well. (Maybe those could be understood with Almost Almost Locked Set arguments?)
Ruud suggests there may be a complementary relationship between Sue de Coq and Almost Locked Candidates (ALC) positions. I shouldn't speculate because I haven't read up on ALC either, but from the tone of the discussion it seems like there would more likely be a complementary relationship between the positions I've described here, and ALC. I think ALC may be using the complement of an ALS, which Myth Jellies defined as a "Weak ALS" in this thread. (I would have called it an Almost Hidden Set, but the last thing the Sudoku world needs are more aliases for the same concept.)
[following added, 14 Mar 2007)]
Here's another example, taken from the Sudopedia page on Subset Exclusion (here), which I happened to read after posting this. As indicated there, the idea of Subset Exclusion is not widely adopted, because it is very tedious. (I would say the same thing about Aligned Pair or Triple Exclusion. I think a beginning or intermediate player who wants to advance to the next level would be better served by learning to work with Alternating Inference Chains and Almost Locked Sets. Of course, I'm behind the Sudoku frontiers by well over a year so I have the benefit of hindsight. I'm sure these ideas were useful when they were first discovered. I think AIC's and ALS's generalize these ideas).
Code:  ....
 1 9 3  A57 B457 8  6 457 2 
 67 25 8  *2697 3 #24697  57 457 1 
 67 25 4  1 B567 26  3 8 9 
:++:
 3 7 1  4 9 5  2 6 8 
 5 8 69  267 1 267  4 79 3 
 2 4 69  367 8 367  79 1 5 
:++:
 4 3 7  59 2 1  8 59 6 
 89 16 2  5678 #576 679  159 3 4 
 89 16 5  368 B46 3469  19 2 7 
'''' 
By a tedious process of considering the various possible combinations of values for a certain set of cells, it was shown that (7)r2c4 ("*" in the diagram) could be eliminated. Since the relevant cells happened to be highlighted in the figure on that page, and since I had recently been working on my first submission of this post, it only took me a few seconds to see that this position contains 2 ALS's with 2 restricted common digits (or can be viewed as a Sue de Coq).
We can take ALS A = r1c4 with VA = 57, ALS B = r139c5 with VB = 4567, w = 5, x = 7.
This gives not only the elimination of (7)r2c4 obtained by Subset Exclusion, but also eliminates (7)r2c6 and (6)r8c5 (cells marked with "#" in the diagram). 

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
