SudoCue Users Forum Index SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net
 
 FAQFAQ   SearchSearch   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Curious new move

 
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips
View previous topic :: View next topic  
Author Message
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Sun Dec 31, 2006 4:20 pm    Post subject: Curious new move Reply with quote

Here is a curious move that I found in a Sudoku-X, but it is not a move that would be restricted to this variant.

Consider the following Sudoku-X 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 X-Wing 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
View user's profile Send private message Send e-mail
Para
Yokozuna
Yokozuna


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

PostPosted: Tue Jan 02, 2007 7:57 pm    Post subject: Same move in Dec 20th Nightmare Reply with quote

Code:

8 . .|. . .|. . .
. 7 .|. . 2|. 9 .
. 1 2|3 . .|. 6 .
-----+-----+-----
. . 6|. . 7|2 . 5
. . .|. . .|. . .
5 . 7|4 . .|6 . .
-----+-----+-----
. 6 .|. . 5|9 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 ALS-xz patterns.

Para
Back to top
View user's profile Send private message
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Tue Jan 02, 2007 9:46 pm    Post subject: Reply with quote

Thanks for the additional example. Smile

Both this puzzle and my original example have a complementary Sue-De-Coq 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
View user's profile Send private message Send e-mail
Para
Yokozuna
Yokozuna


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

PostPosted: Wed Jan 03, 2007 4:50 pm    Post subject: Sue-de-Coq vs ALC Reply with quote

Just checked what Sue-de-Coq is. As i figure Sue-de-Coq 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
View user's profile Send private message
Ron Moore
Addict
Addict


Joined: 13 Aug 2006
Posts: 72
Location: New Mexico

PostPosted: Wed Mar 14, 2007 12:38 am    Post subject: Two ALS's With Two Restricted Common Candidates Reply with quote

[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, r7c9|r89c8 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 1-3).

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    | *269-7   3    #2469-7 | 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    #57-6  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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips All times are GMT
Page 1 of 1

 
Jump to:  
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