Sue De Coq Revisited Again (ASI#1)

Advanced methods and approaches for solving Sudoku puzzles

Postby hobiwan » Sun Nov 02, 2008 11:31 pm

PIsaacson wrote:Shouldn't the wiki be corrected to state that the A/B sets are N cells with N+1 candidates?

I think you are right (after all, if it was N cells with N candidates we would have two locked sets, no need for an SDC). But even with that change, it won't cover all cases. Look at the following example (posted by ronk a while back). It has 6 candidates in 4 cells in r8:
Code: Select all
.---------------.--------------------.------------------------------.
| 19   3   256  | 24579  24789  4579 | 4568     -4-5678   1678      |
| 8    7   25   | 6      24     1    | 9        C45       3         |
| 19   4   56   | 3579   3789   3579 | 568       2        1678      |
:---------------+--------------------+------------------------------:
| 2    15  1347 | 8      379    6    | 345      A4579    B79        |
| 357  68  9    | 2347   2347   347  | 1        A45678   B678       |
| 37   68  347  | 1      5      3479 | 234-6-8  A46789    2-6-7-8-9 |
:---------------+--------------------+------------------------------:
| 4    19  137  | 37     367    2    | 68        689      5         |
| 357  59  37   | 347    3467   8    | 26        1        269       |
| 6    2   8    | 59     1      59   | 7         3        4         |
'---------------'--------------------'------------------------------'
Sue de Coq: r456c8 - {456789} (r2c8 - {45}, r45c9 - {6789}) => r1c8<>45, r6c7<>68, r6c9<>6789


Although I just got corrected by DonM in another thread I still refer to the original definition (plus the additions made in the "Sue de Co revisited" thread):
Sue de Coq wrote:Consider the set of unfilled cells C that lies at the intersection of Box B and Row (or Column) R. Suppose |C|>=2. Let V be the set of candidate values to occur in C. Suppose |V|>= |C|+2. The pattern requires that we find |V|-|C| cells in B and R, with at least one cell in each, with candidates drawn entirely from V. Label the sets of cells CB and CR and their candidates VB and VR. Crucially, no candidate is allowed to appear in VB and VR. Then C must contain V\(VB U VR) [possibly empty], |VB|-|CB| elements of VB and |VR|-|CR| elements of VR. The construction allows us to eliminate the candidates V\VR from B\(C U CB) and the candidates V\VB from R\(C U CR).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Mon Nov 03, 2008 6:41 am

Reply to hobiwan moved here.
Last edited by ronk on Mon Nov 03, 2008 6:35 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby hobiwan » Mon Nov 03, 2008 7:22 am

ronk wrote:Uncommonly, I think the author was viewing the shared cells in the box-line intersection as a quantum cell(s) -- much like the quantum cell of a Type 3 UR.

The thought never occured to me. I took the text literally and simply did not get it until I read the original thread.

ronk wrote:To what additions on the "Sue de Co revisited" thread do you refer:?:

I referred to Obi-Wahn's comment about using additional characters. I didn't check and so overlooked, that he made that comments in the original thread as well.

ronk wrote:I too like an accurate mathematical description. In the past you pointed out the inaccuracy of the red-higlighted portion above. What if we replaced "candidates drawn entirely from V" with "at least two candidates drawn from V":?:

I can't remember pointing that out. If I did, I was citing Obi-Wahn's comment (see above). If we change according to your proposal, we have to add something like "for every candidate in Cx but not in V Cx must contain an additional cell". And I liked your comment about UR3 (made things clearer to me when I read it).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Mon Nov 03, 2008 8:24 am

Reply to hobiwan moved here.
Last edited by ronk on Mon Nov 03, 2008 6:40 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby DonM » Mon Nov 03, 2008 9:50 am

ronk wrote:
hobiwan wrote:
PIsaacson wrote:Shouldn't the wiki be corrected to state that the A/B sets are N cells with N+1 candidates?

I think you are right (after all, if it was N cells with N candidates we would have two locked sets, no need for an SDC).

Uncommonly, I think the author was viewing the shared cells in the box-line intersection as a quantum cell(s) -- much like the quantum cell of a Type 3 UR.

hobiwan wrote:Although I just got corrected by DonM in another thread I still refer to the original definition (plus the additions made in the "Sue de Co revisited" thread):
Sue de Coq wrote:Consider the set of unfilled cells C that lies at the intersection of Box B and Row (or Column) R. Suppose |C|>=2. Let V be the set of candidate values to occur in C. Suppose |V|>= |C|+2. The pattern requires that we find |V|-|C| cells in B and R, with at least one cell in each, with candidates drawn entirely from V. Label the sets of cells CB and CR and their candidates VB and VR. Crucially, no candidate is allowed to appear in VB and VR. Then C must contain V\(VB U VR) [possibly empty], |VB|-|CB| elements of VB and |VR|-|CR| elements of VR. The construction allows us to eliminate the candidates V\VR from B\(C U CB) and the candidates V\VB from R\(C U CR).

I too like an accurate mathematical description.


Mathematical descriptions are fine to document a pattern and if one's mathematical experience or aptitude lends them to prefer those descriptions then fine also. But, IMO, they don't help the average solver trying to learn complex patterns and a reference to that SDC description for a beginning solver as a clear explanation is not likely to be helpful. In other words, taking into account everybody who may be interested in learning SDC, which is likely more accessible, the description above or the following for a generic SDC?:

In a row or column within the same box, look for a core of 4 digit values in 2 cells or 5 digit values in 3 cells. Now, on that same row or column, look for a bivalue cell where the digits are the same as 2 of those in the core. Then, in the same box as the core, look for a bivalue cell with 2 digits from the core, but not the same digits as in the other bivalue cell. If the above are present, on the row or column, you can eliminate all the digits on that row or column equal to the digits in the bivalue cell and in that box eliminate all the digits equal to the bivalue cell there. You can also eliminate all digits in the row or column or in the box equal to any digit still remaining in the core but not present in the two bivalue cells.

My premise is that if SDC and some of the other complex patterns had been described more like this (in addition to the mathematical form), they would be used more often. After all, SDC is the most powerful single non-chain pattern in terms of potential eliminations and yet most solvers don't even seem to look for it. Even the title, accurate as it may be, 'two-sector disjoint subsets', when compared to 'naked pairs' was probably enough to make the regular solver move on.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby ronk » Mon Nov 03, 2008 10:15 am

I've moved the potential mathematical discussion of the Sue de Coq move to the original Two-Sector Disjoint Subsets thread.

DonM, why is it that no one can give an opinion contrary to yours without you becoming defensive:?:
Last edited by ronk on Mon Nov 03, 2008 6:55 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby DonM » Mon Nov 03, 2008 10:54 am

ronk wrote:DonM, why is it that no one can give an opinion contrary to yours without you becoming defensive:?:


Well, let's see. I gave an objective, non-personal opinion that deferred with yours & hobiwan's particularly because it relates to one of the very reasons I started the thread in the first place. So, which one of us is being defensive? For that matter, why make it personal in the first place:?:
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby hobiwan » Mon Nov 03, 2008 12:36 pm

DonM, sorry for hijacking your thread.

I mixed two things in my posts. If you want a tutorial like description for people to learn the technique easily (which of course is the purpose of this thread) then you are right (and you did really well in the first post). But if you want to implement the technique in your solver (which is my main interest) and look for a concise definition, that covers all possibilities, then a more mathematical approach is better IMO (but doesn't belong here).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby DonM » Mon Nov 03, 2008 1:23 pm

hobiwan wrote:DonM, sorry for hijacking your thread.

I mixed two things in my posts. If you want a tutorial like description for people to learn the technique easily (which of course is the purpose of this thread) then you are right (and you did really well in the first post). But if you want to implement the technique in your solver (which is my main interest) and look for a concise definition, that covers all possibilities, then a more mathematical approach is better IMO (but doesn't belong here).


hobiwan, very much appreciated and thanks for making that important distinction. IMO, there are presently two main topics of discussion in the main forums, the mathematical & subjects related to pure manual solving (the two often overlap of course). The former is well-represented and of great past & present value, particularly given the origins of so many of the techniques, but obviously, I'm more an advocate of the latter & hope that occasionally any contribution I make may mean that some newer solver doesn't have to work so hard to understand something like SDC.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby David P Bird » Mon Nov 03, 2008 2:52 pm

I agree that using mathematical notation is a big turn-off to most novices as it requires needless extra effort from them.

I'm not really worried where a SdC starts and finishes as all the cases under discussion are Disjoint Locked Sets. I therefore think it's better to come up with a basic definition for those. Here's my effort:

A simple Disjoint Locked Set (DLS) is a collection of N cells located in two or more houses (or sectors) containing N digits each of which is restricted to a single house. As we have N digits restricted to one occurrence each and N cells to fill, each one will occur once somewhere in the pattern, so any external candidate in sight of all its sisters in the set must be false.


Additionally if just one of the candidates is wild and not restricted to a single house, because the others can only occur once at most, we know that the wild one must occur at least once (and possibly more), so that any sister in sight of all its possible locations must be false - however no deductions are available regarding the other digits.

(Don, this is a worthwhile case of using the DLS notation in my view as the alternative AIC + ALS representation needs to be branched.)

The underlying DLS logic also allows for more complex forms containing repeated digits in separate, isolated houses.

(Don, a simple xy chain can be expressed like this, but there may be prospects for presenting some 'krakenised' xy chains here.)
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Postby DonM » Mon Nov 03, 2008 3:09 pm

David P Bird wrote: A simple Disjoint Locked Set (DLS) is a collection of N cells located in two or more houses (or sectors) containing N digits each of which is restricted to a single house. As we have N digits restricted to one occurrence each and N cells to fill, each one will occur once somewhere in the pattern, so any external candidate in sight of all its sisters in the set must be false.


Additionally if just one of the candidates is wild and not restricted to a single house, because the others can only occur once at most, we know that the wild one must occur at least once (and possibly more), so that any sister in sight of all its possible locations must be false - however no deductions are available regarding the other digits.

(Don, this is a worthwhile case of using the DLS notation in my view as the alternative AIC + ALS representation needs to be branched.)

The underlying DLS logic also allows for more complex forms containing repeated digits in separate, isolated houses.
([b])


David, that's a nice compact definition. Re: notation: I'm sure that, just as we've found with other patterns, there are many opinions and even one's opinion can change with time. I tried to make a case for the one-line format for AAICs (and still use it for archiving purposes), but have to now admit that overall, I like the multi-line format for them, not to mention, for AALSs and AURs, as ronk pointed out back when on Eureka.:)

It occurs to me though that the upside is that if correct SDC notation becomes an subject of discussion, it will mean that more people are using SDC.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby PIsaacson » Mon Nov 03, 2008 8:17 pm

This is probably a dumb question, but is a DLS in fact the same thing as a Distributed Disjoint Subset? David P Bird's definition sure reads like what I know of as a DDS. The original SDC topic header was "Two-Sector Disjoint Subset" and the TSDS acronym appeared repeatedly until "Sue de Coq" won by popular acclaim. It's not that hard to manually find DDS quadruples/quintuples, and I'm starting to spot the occasional sextuple/septuple thanks to this posting and DonM's hunting guide.

So I'm off chasing SDCs again...
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby DonM » Mon Nov 03, 2008 9:17 pm

PIsaacson wrote:This is probably a dumb question, but is a DLS in fact the same thing as a Distributed Disjoint Subset? David P Bird's definition sure reads like what I know of as a DDS. The original SDC topic header was "Two-Sector Disjoint Subset" and the TSDS acronym appeared repeatedly until "Sue de Coq" won by popular acclaim. It's not that hard to manually find DDS quadruples/quintuples, and I'm starting to spot the occasional sextuple/septuple thanks to this posting and DonM's hunting guide. So I'm off chasing SDCs again...


Glad you're finding the 'hunting guide' helpful. I believe that Distributed Disjoint Subsets (as it was discussed in the thread of that name), refers to SDCs that cross beyond 2 sectors.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby PIsaacson » Tue Nov 04, 2008 12:15 am

Code: Select all
After SSTS - using first example from "Two Sector Disjoint Subsets":
4     A*389   A*35      |2        3-9      6       |1        7      B*58
15-39   18-239  6       |7        39       4       |289      238      258
7     A*239   C*23      |8        5        1       |49-2     34-2     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    124     |5        7        9       |28       128      3
35      237     2357    |1        4        8       |6        25       9
159     1-9     8       |3        6        2       |7        15       4

Okay, now here's where I get confused:

POV 1) This could be a 2 sector 5 cell DDS r1c2 r1c3 r1c9 r3c2 r3c3 {23589} which gives the following:
r2c1 <> 3,9 r2c2 <> 239, r3c7 <> 2, r3c8 <> 2, r9c2 <> 9 - based on http://forum.enjoysudoku.com/viewtopic.php?t=5423

POV 2) This could be a double linked ALS chain ALS (1) r1c239 {3589} ALS (2) r3c23 {239} dual link {39} which gives the following:
r2c1 <> 3,9 r2c2 <> 239, r3c7 <> 2, r3c8 <> 2, r9c2 <> 9 - based on http://www.sudoku.org.uk/SudokuThread.asp?fid=4&sid=10326

POV 3) This might be a SDC A = r1c23+r3c2 {23589} B = r1c9 {58} C = r3c3 {23} which gives the following:
r2c1 <> 3,9 r2c2 <> 239, r1c5 <> 9 - based on http://forum.enjoysudoku.com/viewtopic.php?t=2033

Both DDS and ALS dual-linked chains agree in eliminations, but miss the r1c5 <> 9
The SDC misses the r9c2 <> 9 and the r3c78 <> 2, but picks up on the r1c5 <> 9

Are these eliminations correct? If so, then my question is "Why doesn't subset counting (at the least) catch the r1c5 <> 9?" or is it just a lucky guess and my SDC is incorrectly stated?
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby hobiwan » Tue Nov 04, 2008 1:43 am

PIsaacson,
I don't think your SDC view is correct. The core group of cells has to be at an intersection of a row/col and a box, therefore the SDC would be:
A = r1c23 {3589}, B = r1c9 {58}, C = r3c23 {239} => r2c1<>39, r2c2<>239
You could only eliminate 5 or 8 from r1 (if there were any). Due to the SDC, 9 is locked into r13c2, so r1c5=9 is perfectly possible.

Most definitions of SDCs don't cover additional candidates (like the 2 in the example above), and they don't mention the fact, that if one of the candidates of the SDC gets locked into one house, it can be eliminated elsewhere in that house.

In your case:
9 is locked in r13c2 => r9c2<>9
2 is locked in r3c23 => r3c78<>2
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

PreviousNext

Return to Advanced solving techniques