View previous topic :: View next topic 
Author 
Message 
keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA

Posted: Sun May 22, 2011 4:37 am Post subject: Sue de Coq 


Most of you will have noticed that, most of the time, I am only dimly aware of what I am doing. In the past couple of weeks, I have been accused (at least twice) of using a Sue de Coq. So, I thought I should find out what that is.
The existing explanations (that I could find) seemed to be, in the end, incomplete. Also, there are not enough examples. So, while this thread will probably turn out to be nothing new, I hope it will be helpful.
Here are some links to SdC threads:
Sudopedia: http://www.sudopedia.org/wiki/Sue_de_Coq
The original thread: http://forum.enjoysudoku.com/twosectordisjointsubsetst2033.html
Please read the Sudopedia discussion: http://www.sudopedia.org/wiki/Talk:Sue_de_Coq
See also: http://homepages.cwi.nl/~aeb/games/sudoku/solving12.html
The basic idea is this: Code:  ++++
 @ ab @  @ @ @  ( abcde ) 
 . . .  . . .  # # # 
 . . .  . . .  # # cd 
++++
 . . .  . . .  . . . 
 . . .  . . .  . . . 
 . . .  . . .  . . . 
++++
 . . .  . . .  . . . 
 . . .  . . .  . . . 
 . . .  . . .  . . . 
++++
., @, #: Any candidates
a, b, c, d, e: Specific candidates  An SdC exists in one box and one line, in this case B3 and R1.
The three cells common to the line and the box (R1C789) together contain exactly five distinct candidates a,b,c,d, and e.
A cell in the line but not in the box (here, R1C2) contains only candidates a, b.
A cell in the box but not in the line (here, R3C9) contains only candidates c, d.
We can eliminate a, b, and e from all the cells marked @, and we can eliminate c, d, and e from all the cells marked #.
Explanation: Look at the three cells R1C789. Their solution cannot contain both a and b, nor can it contain both c and d. The solution of those three cells must be 1. (a or b), and 2. (c or d), and 3. (e).
1. is a pseudocell that makes a pair ab in R1.
2. is a pseudocell that makes a pair cd in B3.
3. eliminates e in the cells that are in R1 and not B3, and in the cells that are in B3 and not in R1.
Examples, and questions, to follow.
Keith
Last edited by keith on Wed May 25, 2011 9:55 am; edited 1 time in total 

Back to top 


daj95376
Joined: 23 Aug 2008 Posts: 3855

Posted: Sun May 22, 2011 7:55 am Post subject: 


Nice diagram!
Code:  r1c2 = a => r1c789+r3c9 = bcde => (#) <> bcde
r1c2 = b => r1c789+r3c9 = acde => (#) <> acde
since one must be true => (#) <> cde

Code:  r3c9 = c => r1c789+r1c2 = abde => (@) <> abde
r3c9 = d => r1c789+r1c2 = abce => (@) <> abce
since one must be true => (@) <> abe

Regards, Danny 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA

Posted: Sun May 22, 2011 2:14 pm Post subject: 


Example A
Here's an example:
Puzzle: FP042211
Code:  ++++
 8 7 .  1 . .  . . . 
 . . 2  . . .  1 . 4 
 . . .  . 5 9  7 8 . 
++++
 3 . .  4 . 6  . . . 
 . . 7  . . .  9 . . 
 . . .  8 . 3  . . 6 
++++
 . 4 5  9 . .  . . . 
 2 . 3  . . .  4 . . 
 . . .  . . 7  . 5 9 
++++  After basics: Code:  ++++
 8 7 69  1 236 4  2356 2369 235 
 59 356 2  7 36 8  1 369 4 
 146 136 146  236 5 9  7 8 23 
++++
 3 1258 189  4 79 6  258 127 12578 
 46 68 7  25 12 125  9 34 38 
 59 125 149  8 79 3  25 1247 6 
++++
 7 4 5  9 12368 12  2368 1236 1238 
 2 9 3  56 168 15  4 167 178 
 16 168 168  23 4 7  23 5 9 
++++
ab = 69
cd = 23
e = 5 
The Sue de Coq is in R1B3, making the eliminations shown.
Keith 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA

Posted: Sun May 22, 2011 2:29 pm Post subject: 


Example B
Here's another example: Code:  Puzzle: M6306219sh(37)
++++
 1 8 .  . . .  . 4 9 
 . 9 4  . . 1  6 7 . 
 . . .  . . 5  . . . 
++++
 . 2 9  . . 3  . . . 
 . . .  1 . 8  . . . 
 . . .  5 . .  3 8 . 
++++
 . . .  7 . .  . . . 
 . 4 1  2 . .  8 9 . 
 9 5 .  . . .  . 2 6 
++++  After basics: Code:  ++++
 1 8 235  6 237 27  25 4 9 
 235 9 4  38 238 1  6 7 35 
 2367 367 2367  9 4 5  12 13 8 
++++
 8 2 9  4 6 3  157 15 157 
 3457 37 357  1 27 8  9 6 24 
 467 1 67  5 9 27  3 8 24 
++++
 236 36 2368  7 1358 9  4 135 135 
 37 4 1  2 35 6  8 9 357 
 9 5 378  38 138 4  17 2 6 
++++
ab = 35
cd = 17
e = 6  The Sue de Coq is in C9B9, making the eliminations shown. (Edited to add "e = 6" above.)
By the way, the elimination in R4C9 is also made by an XYwing 135. After that: Code:  ++++
 1 8 235  6 237 27  25 4 9 
 235 9 4  38 238 1  6 7 35 
 2367 367 2367  9 4 5  12 13 8 
++++
 8 2 9  4 6 3  157 15 17 
 3457 37 357  1 27 8  9 6 24 
 467 1 67  5 9 27  3 8 24 
++++
 236 36 2368  7 1358 9  4 *135 135 
 37 4 1  2 35 6  8 9 357 
 9 5 378  38 138 4  17 2 6 
++++  I am not sure I would ever recognize this as an SdC. Are there other ways to see that R7C8 <>1?
Keith
Last edited by keith on Sun May 22, 2011 5:45 pm; edited 2 times in total 

Back to top 


JC Van Hay
Joined: 13 Jun 2010 Posts: 468 Location: Charleroi, Belgium

Posted: Sun May 22, 2011 3:43 pm Post subject: 


"MLoop" : 1r7c9(1=7)r4c97r4c7=(71)r9c7@ => 1r7c8 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA

Posted: Sun May 22, 2011 5:49 pm Post subject: 


JC Van Hay wrote:  "MLoop" : 1r7c9(1=7)r4c97r4c7=(71)r9c7@ => 1r7c8  JC's logic is fine, though it is a different pattern from a Sue de Coq. (And, it answers the question I asked.)
Keith 

Back to top 


ronk
Joined: 07 May 2006 Posts: 398

Posted: Sun May 22, 2011 7:14 pm Post subject: 


JC Van Hay wrote:  "MLoop" : 1r7c9(1=7)r4c97r4c7=(71)r9c7@ => 1r7c8 
Instead of that, I see ... (1)r7c9 = (17)r4c9 = (7)r4c7  (7=1)r9c7  loop 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA


Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA

Posted: Sun May 22, 2011 10:13 pm Post subject: 


Example C
The original Sue de Coq:
http://forum.enjoysudoku.com/twosectordisjointsubsetst2033.html
Code:  4 . .  2 . .  1 . .
. . 6  . . 4  . . .
7 . .  8 5 .  . . .
++
2 5 .  4 . .  . . 1
. . .  . . .  . . .
8 . .  . . 3  . 9 7
++
. . .  . 7 9  . . 3
. . .  1 . .  6 . .
. . 8  . . 2  . . 4  After basics: Code:  ++++
 4 389 35  2 39 6  1 7 58 
1359 12389 6  7 39 4  289 238 258 
 7 239 23  8 5 1  249 234 6 
++++
 2 5 9  4 8 7  3 6 1 
 36 367 37  9 1 5  248 248 28 
 8 14 14  6 2 3  5 9 7 
++++
 16 1246 14  5 7 9  28 128 3 
 35 237 2357  1 4 8  6 25 9 
 159 19 8  3 6 2  7 15 4 
++++
ab = 19
cd = 23
e = 8  The line is C2, the box is B1. Making the eliminations shown.
In this same grid, there is a second SdC: Code:  ++++
 4 389 35  2 39 6  1 7 58 
1359 12389 6  7 39 4  289 238 258 
 7 239 23  8 5 1 249 234 6 
++++
 2 5 9  4 8 7  3 6 1 
 36 367 37  9 1 5  248 248 28 
 8 14 14  6 2 3  5 9 7 
++++
 16 1246 14  5 7 9  28 128 3 
 35 237 2357  1 4 8  6 25 9 
 159 19 8  3 6 2  7 15 4 
++++
ab = 39
cd = 58
e = 2  The line is R2, the box is b3. Making the eliminations shown.
Our drag queen (the boy named Sue), then says: Quote:  and that {r7c1,r7c2,r7c3} contains three of {1,3,5,6,9} with the other three values in r5c1 and r9c2, so we eliminate r2c1=9, r2c2=3, r2c2=9 and r7c3=1.  This appears to be a typo: {r7c1,r7c2,r7c3} should be r789c1.
There is a third SdC in C1 and B7: Code:  ++++
 4 389 35  2 39 6  1 7 58 
1359 12389 6  7 39 4  289 238 258 
 7 239 23  8 5 1  249 234 6 
++++
 2 5 9  4 8 7  3 6 1 
 36 367 37  9 1 5  248 248 28 
 8 14 14  6 2 3  5 9 7 
++++
 16 1246 14  5 7 9  28 128 3 
 35 237 2357  1 4 8  6 25 9 
 159 19 8  3 6 2  7 15 4 
++++
ab = 36
cd = 19
e = 5  Making the eliminations shown.
(Edit: Corrected, thanks to Danny.)
Does anyone agree or disagree with this analysis?
Keith
Last edited by keith on Mon May 23, 2011 2:37 am; edited 2 times in total 

Back to top 


daj95376
Joined: 23 Aug 2008 Posts: 3855

Posted: Sun May 22, 2011 11:58 pm Post subject: 


HoDoKu v2.0.1 does not agree ...
(Keith: Yes. Correction made.)
Note: on an earlier puzzle where you use a given, e=6, HoDoKu only uses two cells.
Code:  r78c9  {1357} (r2c9  {35}, r9c7  {17}) => r7c8<>1, r4c9<>5

(Edited by Keith to remove comment details now that corrections have been made.) 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA

Posted: Mon May 23, 2011 1:16 am Post subject: 


Danny,
Thank you. I have made some corrections.
daj95376 wrote:  Note: on an earlier puzzle where you use a given, e=6, HoDoKu only uses two cells.
Code:  r78c9  {1357} (r2c9  {35}, r9c7  {17}) => r7c8<>1, r4c9<>5

 Originally, in Example B, I did not include the solved cell R9C9 = 6 as e. Then, I realized that the basic original template still applies when you do include it. Sure, you can make a special case when only two of the three common cells are unknown, but why?
I guess I was very surprised to find an error in the original Sue de Coq post. It's been around for years!
Keith 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA

Posted: Mon May 23, 2011 3:36 am Post subject: 


Example D
http://forum.enjoysudoku.com/post16664.html#p16664
ronk has a Sue de Coq example which makes a lot of eliminations, and solves an intractable puzzle: Code:  Puzzle: ronkSdC
++++
 . 6 .  . . .  8 3 . 
 . 2 5  . . .  . 1 . 
 . . .  . 1 6  . . . 
++++
 . . 7  . 6 .  . . . 
 8 . .  4 . 5  7 . 3 
 . . .  . . .  . 8 . 
++++
 . . 2  . . .  1 9 . 
 . 5 .  . . 8  . . . 
 4 . .  . . 7  . . . 
++++  After basics: Code:  ++++
 179 6 149  2579 24579 249  8 3 24579 
 379 2 5  379 8 349  469 1 4679 
 379 34789 3489  23579 1 6  2459 2457 24579 
++++
 25 349 7  8 6 1239  2459 245 12459 
 8 19 169  4 29 5  7 26 3 
 25 349 3469  2379 2379 1239  24569 8 124569 
++++
 367 378 2 356 345 34  1 9 45678 
 13679 5 139 12369 2349 8  2346 2467 2467 
 4 1389 1389 123569 2359 7  2356 256 2568 
++++
ab = 29
cd = 34
e = 5 
The SdC is in C5B8, making the eliminations shown. [Edited to fix a typo in R9C4.]
Keith
Last edited by keith on Mon May 23, 2011 8:11 pm; edited 1 time in total 

Back to top 


ronk
Joined: 07 May 2006 Posts: 398

Posted: Mon May 23, 2011 4:12 am Post subject: 


keith, the SDC is subsumed by the doublylinked ALSxz. 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA

Posted: Tue May 24, 2011 1:00 am Post subject: 


ronk wrote:  keith, the SDC is subsumed by the doublylinked ALSxz.  ronk, you are correct, but (except for more examples), I'm going to stop here with the theory. The linked ALS patterns get very complicated very quickly.
My goal is to lay out patterns that might be useful for pencil and paper solvers. Let's see how useful this basic pattern turns out to be. If what has been laid out so far is not useful, there is no point in going farther.
Keith 

Back to top 


DonM
Joined: 15 Sep 2009 Posts: 51

Posted: Tue May 24, 2011 2:30 am Post subject: 


keith wrote:  ronk wrote:  keith, the SDC is subsumed by the doublylinked ALSxz.  ronk, you are correct, but (except for more examples), I'm going to stop here with the theory. The linked ALS patterns get very complicated very quickly.
My goal is to lay out patterns that might be useful for pencil and paper solvers. Let's see how useful this basic pattern turns out to be. If what has been laid out so far is not useful, there is no point in going farther.
Keith 
Keith, I didn't see the following link above. It is in the way of a miniprimer for manual solvers with some graphic examples (hide the kids ):
http://forum.enjoysudoku.com/suedecoqrevisitedagainasi1t6410.html
My interest in SuedeCoq developed mainly as a pattern that should be of great interest to manual/pencil&paper solvers, but which seemed to be very underused. In the 2+ years since the thread above, I have found the SDC to be relatively easytolearn (and find) and frequent enough to be wellworth adding to one's toolbag, especially considering how powerful it is.
Following up on your point above: In spite of having also put up 2 ALSprimer threads including duallinked ALSxz examples (those threads specifically aimed at manual solvers), I have found that a SuedeCoq pattern is much easier to find than the associated duallinked ALS patterns. I don't think this just applies to me, because I practically never see duallink ALS patterns in the solutions of others. 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA

Posted: Tue May 24, 2011 3:16 am Post subject: 


DonM wrote:  Keith, I didn't see the following link above. It is in the way of a miniprimer for manual solvers with some graphic examples (hide the kids ):
http://forum.enjoysudoku.com/suedecoqrevisitedagainasi1t6410.html
My interest in SuedeCoq developed mainly as a pattern that should be of great interest to manual/pencil&paper solvers, but which seemed to be very underused. In the 2+ years since the thread above, I have found the SDC to be relatively easytolearn (and find) and frequent enough to be wellworth adding to one's toolbag, especially considering how powerful it is.
Following up on your point above: In spite of having also put up 2 ALSprimer threads including duallinked ALSxz examples (those threads specifically aimed at manual solvers), I have found that a SuedeCoq pattern is much easier to find than the associated duallinked ALS patterns. I don't think this just applies to me, because I practically never see duallink ALS patterns in the solutions of others. 
DonM,
I think we are in violent agreement! I had not seen the specific thread you mention, but there are a couple of similar ones. I did not quote them, because they stray to more general patterns than are defined and described in this thread.
I also have the feeling that the utility of the Sue de Coq may have been diminished in the last couple of years by Mwings, Wwings, and the like. Not that they are variants of the same pattern as the SdC, but they can often be used to make the same eliminations.
Nonetheless, I think the basic Sue de Coq pattern is incredibly elegant, and easy to recognize. It belongs in our toolboxes.
Keith 

Back to top 


DonM
Joined: 15 Sep 2009 Posts: 51

Posted: Sun May 29, 2011 6:46 pm Post subject: 


keith wrote:  DonM wrote:  Keith, I didn't see the following link above. It is in the way of a miniprimer for manual solvers with some graphic examples (hide the kids ):
http://forum.enjoysudoku.com/suedecoqrevisitedagainasi1t6410.html
My interest in SuedeCoq developed mainly as a pattern that should be of great interest to manual/pencil&paper solvers, but which seemed to be very underused. In the 2+ years since the thread above, I have found the SDC to be relatively easytolearn (and find) and frequent enough to be wellworth adding to one's toolbag, especially considering how powerful it is.
Following up on your point above: In spite of having also put up 2 ALSprimer threads including duallinked ALSxz examples (those threads specifically aimed at manual solvers), I have found that a SuedeCoq pattern is much easier to find than the associated duallinked ALS patterns. I don't think this just applies to me, because I practically never see duallink ALS patterns in the solutions of others. 
DonM,
I think we are in violent agreement! I had not seen the specific thread you mention, but there are a couple of similar ones. I did not quote them, because they stray to more general patterns than are defined and described in this thread.
I also have the feeling that the utility of the Sue de Coq may have been diminished in the last couple of years by Mwings, Wwings, and the like. Not that they are variants of the same pattern as the SdC, but they can often be used to make the same eliminations.
Nonetheless, I think the basic Sue de Coq pattern is incredibly elegant, and easy to recognize. It belongs in our toolboxes.
Keith 
In my Sudoku discussions I think that some of my opinions have pushed one or two people to a point of violence, but never from a position of agreement!
Interestingly enough, I went back into my solving archives and found it ironic (given my comment in bold above) that the only puzzle solution I've ever posted in Other Puzzles here (I think) was a duallinked ALS (towards the bottom of the following threadI still don't know how to link to a specific post):
http://www.dailysudoku.com/sudoku/forums/viewtopic.php?p=20026#20026
Last edited by DonM on Sun May 29, 2011 8:13 pm; edited 2 times in total 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3287 Location: near Detroit, Michigan, USA


Back to top 


DonM
Joined: 15 Sep 2009 Posts: 51

Posted: Sun May 29, 2011 8:13 pm Post subject: 


Well, that was easy! (Have edited the link.) Thanks Keith. 

Back to top 


Asellus
Joined: 05 Jun 2007 Posts: 865 Location: Sonoma County, CA, USA

Posted: Wed Jun 15, 2011 4:39 pm Post subject: 


I was traveling this past month so didn't see this thread. As someone who occasionally spots and utilizes Sue de Coq, I would quibble only slightly with the definition above as being overdetermined, as I'll try to explain. Also, the definitions in the various links seem overly complicated given the basic pattern involved. How easy this pattern is to spot probably varies from person to person but describing it shouldn't make the job more difficult than necessary.
Here's my attempt to define the pattern most generally in the simplest "visual pattern" terms I can think of. I use abbreviations that match the pattern's structure. I'll label an example with the abbreviations to help make it clear.
A Sue de Coq involves n candidates in n cells arranged in a particular way within two houses, a Box (B) and a Row or Column (RC) that overlaps with the Box. I'll use "S" to refer to each of the n Sue de Coq cells. These n cells fall into 3 groups: (1) at least 2 of the 3 overlap cells ("OLS"); (2) at least one of the RC cells not in the overlap ("RCS"); and (3) at least one of the B cells not in the overlap ("BS"). The final requirement is that the RCS and BS cells can have no digit in common.
The victim cells fall into 2 groups: (1) nonSue de Coq cells within the Box ("BV"); and (2) nonSue de Coq cells within the Row or Column ("RCV").
Eliminations: (1) All digits in the RCS cells can be eliminated from the RCV cells, and (2) all digits in the BS cells can be eliminated from the BV cells, and (3) if the OLS cells contain a digit not found in either the BS or RCS cells that digit can be eliminated from all of the victim cells.
Using the second example in the "Example C" post:
Code:  ++++
 4 OLS:389 OLS:35  2 39 6  1 7 RCS:58 
1359 12389 6  7 39 4  289 238 258 
 7 BS:239 BS:23  8 5 1  249 234 6 
++++
 2 5 9  4 8 7  3 6 1 
 36 367 37  9 1 5  248 248 28 
 8 14 14  6 2 3  5 9 7 
++++
 16 1246 14  5 7 9  28 128 3 
 35 237 2357  1 4 8  6 25 9 
 159 19 8  3 6 2  7 15 4 
++++ 
This is a 5digit, 5cell Sue de Coq. The BS digits are 239; the RCS digits are 58 (these two groups have no digits in common, as required). In this case, there are no eliminations in the potential RC victim cells and there is no digit unique to the OLS cells for the third sort of elimination. (I removed the eliminations shown in r3c78 in the previous post because they are consequential eliminations due to locked candidates and not eliminations immediately due to the Sue de Coq.)
To avoid clutter I didn't label the potential victim cells. To make sure they are clear, here is a diagram:
Code:  ++++
 RCV/BV S S  RCV RCV RCV  RCV RCV S 
 BV BV BV         
 BV S S         
++++ 
Additional comments...
The smallest possible SdC requires 4 cells and the largest could involve, conceivably, 9 cells (though whether such a creature occurs in the real world I don't know).
There can be multiple RCS cells and multiple BS cells and they aren't limited to bivalue cells. (The example above has two BS cells, one a trivalue cell.)
In the example, I show 2 OLS cells rather than three. Since the third OL cell is a solved cell, it could be included (forming a 6cell/digit SdC) without contradicting the definition. However, we don't usually consider solved cells to be parts of solving patterns. In addition, I believe that such a nonSdC third OL cell does not necessarily need to be a solved cell and is thus a potential victim (though I don't have an example to prove this).
At most there can be only one digit in the OLS cells not contained in either the RCS or BS cells and causing the third sort of elimination from all possible victim cells.
As already mentioned, all Sue de Coqs can be seen as overlapping ALS closed AIC loops. For those familiar with such things, that is probably the easiest way to understand the underlying logic. Otherwise, one must do a bunch of "ifthen" reasoning exhausting the solution possibilities to convince oneself that the pattern works as described. While this ALS connection is interesting and worth pursuing, definitions of the pattern that rely on ALS (or AALS or AAAAAALS) descriptions strike me as too many trees and not enough forest. 

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
