## Two-Sector Disjoint Subsets

Advanced methods and approaches for solving Sudoku puzzles
ronk wrote:Here is an example where both sets B (CB) and C (CR) contain digit 1...

Nice example! (And another one my solver doesn't pick up ).

ronk wrote:There's no doubt that is true. Modifying rubylip's definition, while keeping the definition simple, is the problem.

First stab:
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|+n cells in B and R, with at least one cell in each, with at least |V|-|C| candidates drawn from V and with n the number of candidates not drawn from V. Label the sets of cells CB and CR and their candidates VB and VR. Crucially, no candidate from V 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), the candidates VR\V from R\(C U CR) and the candidates VB\V from B\(C U CB).

Your case with the same candidate in CR and CB ist not mentioned explicitly (counts both times for n). Simple is relative though...
hobiwan
2012 Supporter

Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

hobiwan wrote:The pattern requires that we find |V|-|C|+n cells in B and R ...

By noting that ... |VB| + |VR| + |V\(VB U VR)| = |CB| + |CR| + |C| ... can't we avoid specific mention of an 'n'

BTW I added two more examples (2nd and 3rd here) of SDCs that have the same digit in both VB and VR.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

I cannot find smaller Sue De Coq patterns for these puzzles.
Code: Select all
`Ruud50k #6640..........7.2.691.....75...4........16.3...8....5.1.3...68..7....9.....3534...12.After SSTS 69-38 249-5 12-58 | 149   1348  348   | 38    4567  24567B38    7    B58    | 2     348   6     | 9     1     45A3689 A249  A128   |C149   7     5     | 38   C46   C246-------------------+-------------------+------------------ 4     259   3     | 67    2689  2789  | 256   5679  1 1     6     257   | 3     249   2479  | 245   8     4579 89    29    278   | 5     2469  1     | 246   3     4679-------------------+-------------------+------------------ 2     1     6     | 8     345   34    | 7     459   459 7     8     9     | 14    1245  24    | 456   456   3 5     3     4     | 67    69    79    | 1     2     8Sets: A = {r3c23} = {1234689}; B = {r2c13} = {358}; C = {r3c489} = {12469}Elims: r1c1<>38, r1c2<>5, r1c3<>58`

The box-line intersection of 3 cells (A) contains 7 candidates (meaning candidate values), with 2 candidates linked to a 2-cell ALS (B) and 5 candidates linked to a 3-cell AALS (C). After the SDC, cascading singles solves the puzzle.

[edit: Actually, there is a smaller SDC in the above. Can you find it?]

Code: Select all
`Ruud50k #11016.8..6.3.....8.7..46.4..1....47....8.9.......1.1....49....2....92..5.3.....3.8..6.After SSTS 157   8     1259  | 49    6     2459  | 3     1257  25 135   2359  1259  | 8    C259   7     | 6     125   4 6     257   4     | 3    C25    1     | 9     257   8-------------------+-------------------+------------------ 35    4     7     | 19-6 A12359 259   | 25    8     36 9     2356  2568  |B46   A2345  258-4 | 7     25    1 358   1     2568  |B67   A2357  258   | 4     9     36-------------------+-------------------+------------------ 14578 57    158   | 2     47-1  6     | 158   3     9 2     69    1689  | 5    C19    3     | 18    4     7 1457  579   3     | 1479  8     49    | 125   6     25Sets: A = {r456c5} = {1234579}; B = {r56c4} = {467}; C = {r238c5}={1259}Elims: r4c4<>6, r5c6<>4, r7c5<>1`

The box-line intersection of 3 cells (A) contains 7 candidates, with 2 candidates linked to a 2-cell ALS (B) and 4 candidates linked to a 3-cell ALS (C). Then, interlaced with singles, a nice loop ... r4c5 -1- r8c5 =1= r9c4 =7= r7c5 =4= r5c5 =3= r4c5 ==> r4c5<>1
... two naked pairs and a w-wing solve the puzzle.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:By noting that ... |VB| + |VR| + |V\(VB U VR)| = |CB| + |CR| + |C| ... can't we avoid specific mention of an 'n'

Look's fine to me!

BTW: If we aim for completeness, we should add, that if any candidate of the complete SDC get's locked into one house that's not part of the SDC, that canddiate can be eliminated from the additional house.

Ruud50k #6640: the smallest SDC my solver finds is
Code: Select all
`.---------------------.--------------------.-------------------.| -36-89  2459  125-8 | A149  A1348  A348  | C38   4567  24567 ||  38     7     58    |  2     3-48   6    |  9    1     45    ||  3689   249   128   | B149   7      5    |  38   46    246   |:---------------------+--------------------+-------------------:|  4      259   3     |  67    2689   2789 |  256  5679  1     ||  1      6     257   |  3     249    2479 |  245  8     4579  ||  89     29    278   |  5     2469   1    |  246  3     4679  |:---------------------+--------------------+-------------------:|  2      1     6     |  8     345    34   |  7    459   459   ||  7      8     9     |  14    1245   24   |  456  456   3     ||  5      3     4     |  67    69     79   |  1    2     8     |'---------------------'--------------------'-------------------'Sue de Coq: r1c456 - {13489} (r1c7 - {38}, r3c4 - {149}) => r1c1<>3, r2c5<>4, r1c13<>8orSue de Coq: r1c56 - {1348} (r1c7 - {38}, r13c4 - {149}) => r2c5<>4, r1c1<>3, r1c13<>8`

Ruud50k #11016: No luck here.
hobiwan
2012 Supporter

Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

hobiwan wrote:
ronk wrote:By noting that ... |VB| + |VR| + |V\(VB U VR)| = |CB| + |CR| + |C| ... can't we avoid specific mention of an 'n'

Look's fine to me!

It looks pretty, but I now think ... |V| + |VB\V| + |VR\V| = |C| + |CB| + |CR| ... is much easier to understand. The 2nd and 3rd terms contain only the "extra candidates" in B and R, respectively. Besides, I actually tested this one.

hobiwan wrote:BTW: If we aim for completeness, we should add, that if any candidate of the complete SDC get's locked into one house that's not part of the SDC, that canddiate can be eliminated from the additional house.

Changing the last sentence of rubylips' definition to ...

The construction allows us to eliminate candidates VB U (V\VR) from B\(C U CB), and candidates VR U (V\VB) from R\(C U CR).

... should take care of that.

hobiwan wrote:Ruud50k #6640: the smallest SDC my solver finds is
[...]
Sue de Coq: r1c456 - {13489} (r1c7 - {38}, r3c4 - {149}) => r1c1<>3, r2c5<>4, r1c13<>8
or
Sue de Coq: r1c56 - {1348} (r1c7 - {38}, r13c4 - {149}) => r2c5<>4, r1c1<>3, r1c13<>8

I found the second, but was unaware of the first interpretation. Thanks.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:It looks pretty, but I now think ... |V| + |VB\V| + |VR\V| = |C| + |CB| + |CR| ... is much easier to understand.

Nice!

ronk wrote:
hobiwan wrote:BTW: If we aim for completeness, we should add, that if any candidate of the complete SDC get's locked into one house that's not part of the SDC, that canddiate can be eliminated from the additional house.

Changing the last sentence of rubylips' definition to ...

The construction allows us to eliminate candidates VB U (V\VR) from B\(C U CB), and candidates VR U (V\VB) from R\(C U CR).

... should take care of that.

It's definitely better than my first stab, but it doesn't cover what I meant. Consider the following SDC posted by PIsaacson here:
Code: Select all
`.------------.-----------------.----------------.| 1  9    37 |  8   35     2   | 56   4    67   || 2  8    4  |  6   57-9  B19  | 3    59   17   || 5  6   C37 | A17  4     A39  | 2    8    1-79 |:------------+-----------------+----------------:| 9  37   2  |  4   36     8   | 67   1    5    || 6  4    5  |  17  379    139 | 8    39   2    || 8  37   1  |  2   369    5   | 679  369  4    |:------------+-----------------+----------------:| 7  1    9  |  5   8      6   | 4    2    3    || 3  5    6  |  9   2      4   | 1    7    8    || 4  2    8  |  3   1      7   | 569  569  69   |'------------'-----------------'----------------'Sue de Coq: r3c46 - {1379} (r3c3 - {37}, r2c6 - {19}) => r3c9<>7, r2c5<>9`

R is r3 and B is b2, but as PIsaacson noted, 9 can be eliminated from r5c6 (because the 9s are locked in c6). The definition as it stands does not cover that elimination since it's neither in R nor in B.
hobiwan
2012 Supporter

Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

hobiwan wrote:Consider the following SDC posted by PIsaacson here:R is r3 and B is b2, but as PIsaacson noted, 9 can be eliminated from r5c6 (because the 9s are locked in c6). The definition as it stands does not cover that elimination since it's neither in R nor in B.

I believe this SDC should not result in r5c6<>9. Strictly speaking, an SDC involves two sectors, not three. Adding the third sector makes it a Distributed Disjoint Subset technique.

BTW I expect to soon complete a revised Sue De Coq definition for your review. So far it's just been "here a piece, there a piece" ... as I try to get it all straight in my head.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:
Code: Select all
`top1465 #785.......9.....3..51.7..418...13...4......5...37.8....2...1.64....9......2...5.....After SSTS 1    3   B26   | 678  278  5    | 27   9    4A489 B68   249-6| 679  3    279  | 27   5    1A29   7    5    | 29   4    1    | 8    3    6----------------+----------------+--------------- 5    1    3    | 789  2789 2789 | 4    6    78C69   26   29   | 4    5    78   | 1    78   3 7    4    8    | 3    1    6    | 9    2    5----------------+----------------+--------------- 28   5    1    | 279  6    4    | 3    78   789C36   9    67   | 1    78   378  | 5    4    2C34   28   47   | 5    279  2379 | 6    1    789Sets: A = {r23c1} = {2489}, B = {r1c3,r2c2} = {268}, C = {r589c1} = {3469}Elim: r2c3<>6`

I finally got time to add the last SDC variant and ran into trouble: shouldnt this be r2c3<>26?
hobiwan
2012 Supporter

Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

hobiwan wrote:I finally got time to add the last SDC variant and ran into trouble: shouldnt this be r2c3<>26?

A more significant "variant" may be hidden SDCs -- see here. Thanks for the correction.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Previous