Distributed Disjoint Subsets

Advanced methods and approaches for solving Sudoku puzzles

Distributed Disjoint Subsets

Postby Obi-Wahn » Fri May 11, 2007 9:14 am

Hello,
this thread is about the idea of generalizing the Two-Sector Disjoint Subsets (Sue De Coq) technique to more than 2 sectors.

The rule can be put very simple:
A subset of N cells sharing only N different digits is disjoint, if all occurrences of the same digit share one common sector.
This means that none of the N digits can be true more than once in the subset, because all instances of this digit within the subset can "see" each other.
Every candidate outside the subset that shares a sector with all occurrences of the same digit within the subset can be eliminated.
This follows because if such a candidate was true, it would eliminate this digit completely from the subset, leaving us with only N-1 digits for N cells.

This idea was given by Pep in the above mentioned thread, unfortunately he could give only theoretical examples.
Pep wrote:Now all I have to do is find an efficient algorithm to spot these cases....

AFAIK he never accomplished this task, but ronk found a practical example with 3 sectors.
ronk wrote:I found one of these ... a Three-Sector Disjoint Subset pattern ... in puzzle #461 of the top1465. If the pattern wasn't very rare, I would've started a new thread on the topic. As it is rare, I'm only posting this here for those who might have an academic interest.

With basic techniques, the puzzle can be advanced to ...
Code: Select all
 19     3      256    | 24579  24789  4579   | 4568   45678  1678
 8      7      25     | 6      24     1      | 9     C45     3
 19     4      56     | 3579   3789   3579   | 568    2      1678
----------------------+----------------------+---------------------
 2      15     1347   | 8      3479   6      | 345   A4579  B79
 357   D68     9      | 2347   2347   347    | 1     A45678 A678
 37     68     347    | 1      5      3479   | 23468  46789  26789
----------------------+----------------------+---------------------
 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

Sets: A = {r5c8,r6c8,r6c9} = {456789}
      B = {r4c9} = {79}
      C = {r2c8} = {45}
      D = {r5c2} = {68}

Excepting the cells of sets A, B, C, and D:
      7,9 may be eliminated from box 6  (4 elims)
      4,5 may be eliminated from col 8  (3 elims)
      6,8 may be eliminated from row 5  (0 elims)

Set A is an almost-almost-almost-disjoint set with three cells and six candidates. It shares two candidates with set B, two different candidates with set C, and an additional two different candidates with set D.

I guess I have an academic interest, but fortunately these Distributed Disjoint Subsets aren't as rare as I feared due to Ron's comment.

Now I finally managed to code a searching routine for Distributed Disjoint Subsets into my solver and I was able to find over 300 puzzles within 100000 randomly generated sudokus, that can't be solved with more basic techniques only but can be solved with this new technique.

Here's a Four-Sector Disjoint Subset for a start:
Code: Select all
.3...9..5..........8.6...3.4..2...........1..219....6.6.3...72....3....1...45.8..

After SSTS, an XYZ-Wing and a Sue De Coq we get:
.------------------.---------------------.------------------.
| 17    3     6    | 178  *24      9     | 24    18    5    |
| 59    4     127  | 1578  378-12  37-25 | 29    18    6    |
| 59    8     12   | 6    *124    *45    | 249   3     7    |
:------------------+---------------------+------------------:
| 4     6     58   | 2    *18      13-58 | 35    7     9    |
| 3     7     58   | 9     6      *58    | 1     4     2    |
| 2     1     9    | 57    347     347-5 | 35    6     8    |
:------------------+---------------------+------------------:
| 6     5     3    | 18    9       18    | 7     2     4    |
| 8     9     4    | 3     7-2     27    | 6     5     1    |
| 17    2     17   | 4     5       6     | 8     9     3    |
'------------------'---------------------'------------------'

5 cells (*) sharing 5 different digits {12458}.

Digit 1 only appears in column 5, so it can be eliminated from the remaining cells in this column.
Digit 2 only appears in the intersection of box 2 and column 5, so it can be eliminated from the remaining cells of both this box and this column.
Digit 4 only appears in box 2, but there are no eliminations.
Digit 5 appears only in column 6, so it can be eliminated from the remaining cells in this column.
Digit 8 only appears in box 5, so it can be eliminated from the remaining cells in this box.

4 sectors are involved (c56b25).


And another Four-Sector Disjoint Subset:
Code: Select all
8..9..3....5.....69...78....1....94..7...........2..57..4..6..2.5.2.7.........41.

After SSTS we get:
.------------------.---------------------.------------------.
| 8     246   126  | 9     56     245    | 3     7     14   |
| 7     234   5    | 134   13     124-3  | 8     9     6    |
| 9     346   16   | 346   7      8      | 5     2     14   |
:------------------+---------------------+------------------:
|*256   1     236  | 7     368-5 *35     | 9     4     38   |
| 45    7     39   | 13458 13589  145-39 | 2     6     38   |
|*46    8     369  | 36-4  2     *349    | 1     5     7    |
:------------------+---------------------+------------------:
| 3     9     4    | 15    15     6      | 7     8     2    |
| 1     5     8    | 2     4      7      | 6     3     9    |
|*26    26    7    | 38    389   *39     | 4     1     5    |
'------------------'---------------------'------------------'

6 cells (*) sharing 6 different digits {234569}.

Digits 2 and 6 only appear in column 1, but there are no eliminations.
Digit 3 and 9 appear only in column 6, so they can be eliminated from the remaining cells in this column.
Digit 4 appears only in row 6, so it can be eliminated from the remaining cells in this row.
Digit 5 appears only in row 4, so it can be eliminated from the remaining cells in this row.

4 sectors are involved (r46c16).


And a Five-Sector Disjoint Subset
Code: Select all
.7.......9.....1.41.3.7.92...9...3..2..1....5.1..28........5.9.7...4..5..8......6

After SSTS we get:
.------------------.-------------------.------------------.
| 4     7    *28   | 29-8  *189   129  | 5     6     3    |
| 9    *256   68-2 | 23568  3568  236  | 1     7     4    |
| 1    *56    3    | 456    7     46   | 9     2     8    |
:------------------+-------------------+------------------:
| 8    *46    9    | 4567   56    467  | 3     1     2    |
| 2    *34    7    | 1     *39    49-3 | 6     8     5    |
| 36    1     5    | 36     2     8    | 7     4     9    |
:------------------+-------------------+------------------:
| 36    23-6  14   | 268    68-1  5    | 248   9     7    |
| 7     9     26   | 2368   4     236  | 28    5     1    |
| 5     8     14   | 279   *19    1279 | 24    3     6    |
'------------------'-------------------'------------------'

8 cells (*) sharing 8 different digits {12345689}.

Digit 1 only appears in column 5, so it can be eliminated from the remaining cells in this column.
Digit 2 only appears in box 1, so it can be eliminated from the remaining cells in this box.
Digit 3 only appears in row 5, so it can be eliminated from the remaining cells in this row.
Digit 4 only appears in the intersection of box 4 and column 2, but there are no eliminations.
Digit 5 only appears in the intersection of box 1 and column 2, but there are no eliminations.
Digit 6 only appears in column 2, so it can be eliminated from the remaining cells in this column.
Digit 8 only appears in row 1, so it can be eliminated from the remaining cells in this row.
Digit 9 only appears in column 5, but there are no eliminations.

5 sectors are involved (r15c25b1).


I know that Ron doesn't appreciate this idea, because it's almost impossible for a human solver to spot. But at least for me that applies to ALS chains, too. Once spotted, I think the Distributed Disjoint Subset is easy to understand, so I deem it worth to investigate it further, because maybe it can explain eliminations easier than long chains, even if it's hard to spot. After all it only requires counting.

Greetings, Stefan
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby daj95376 » Fri May 11, 2007 12:13 pm

Your 'Five-Sector Disjoint Subset' has a templates Achilles Heel in <6>.

Code: Select all
# finned Franken Jellyfish r368b4/c1246 (?)
# Naked Singles complete puzzle
^-----------------------------------------------------------------------------^
|  4       7       28     |  289     189     129    |  5       6       3      |
|  9       256     268    |  23568   3568    236    |  1       7       4      |
|  1      *56      3      | *456     7      *46     |  9       2       8      |
|-------------------------+-------------------------+-------------------------|
|  8      *46      9      |  4567    56      467    |  3       1       2      |
|  2       34      7      |  1       39      349    |  6       8       5      |
| @36      1       5      | *36      2       8      |  7       4       9      |
|-------------------------+-------------------------+-------------------------|
|  3-6     236     14     |  268     168     5      |  248     9       7      |
|  7       9      #26     | *2368    4      *236    |  28      5       1      |
|  5       8       14     |  279     19      1279   |  24      3       6      |
^-----------------------------------------------------------------------------^
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby re'born » Fri May 11, 2007 2:04 pm

In your first Four-Sector Disjoint Subset example,
Code: Select all
.3...9..5..........8.6...3.4..2...........1..219....6.6.3...72....3....1...45.8..


I can spot the XYZ-Wing, but not the Sue De Coq that eliminates the 3 from r5c4 and the 1 from r3c6. I suppose it should also eliminate the 1 and 8 from r2c6, but this isn't needed in your example. Can you lend a brother a hand?
re'born
 
Posts: 551
Joined: 31 May 2007

Postby underquark » Fri May 11, 2007 2:57 pm

Code: Select all
 
 *--------------------------------------------------------------------*
 | 8     *246   *126    | 9      5-6    245    | 3      7      14     |
 | 7     *234    5      |*134    13    *124    | 8      9      6      |
 | 9      346    16     | 346    7      8      | 5      2      14     |
 |----------------------+----------------------+----------------------|
 | 256    1      236    | 7      368    35     | 9      4      38     |
 | 45     7      39     | 13458  13589  145    | 2      6      38     |
 | 46     8      369    | 36     2      349    | 1      5      7      |
 |----------------------+----------------------+----------------------|
 | 3      9      4      | 15     15     6      | 7      8      2      |
 | 1      5      8      | 2      4      7      | 6      3      9      |
 | 26     26     7      | 38     389    39     | 4      1      5      |
 *--------------------------------------------------------------------*

I'm a human (I think); have I applied this technique correctly in eliminating 6 from r1c5? Are there puzzles where multiple succesive applications of this technique are required?
Last edited by underquark on Fri May 11, 2007 2:09 pm, edited 1 time in total.
underquark
 
Posts: 299
Joined: 06 September 2005

Postby ronk » Fri May 11, 2007 3:07 pm

rep'nA wrote:In your first Four-Sector Disjoint Subset example, [...] I can spot the XYZ-Wing, but not the Sue De Coq that eliminates the 3 from [edit: r4c5] and the 1 from r3c6. I suppose it should also eliminate the 1 and 8 from r2c6, but this isn't needed in your example.

Because of the added cell r6c5, this Sue de Coq is a bit unusual.
Code: Select all
 17     3      6      | 178    24     9      | 24     18     5
 59     4      127    | 1578   12378  2357-18| 29     18     6
 59     8      12     | 6      124    245-1  | 249    3      7
----------------------+----------------------+---------------------
 4      6      58     | 2      18-3  A1358   | 35     7      9
 3      7      58     | 9      6     A58     | 1      4      2
 2      1      9      |B57    A347   A3457   | 35     6      8
----------------------+----------------------+---------------------
 6      5      3      | 18     9     C18     | 7      2      4
 8      9      4      | 3      27     27     | 6      5      1
 17     2      17     | 4      5      6      | 8      9      3

Sets:  A = {r456c6,r6c5} = {134578}
       B = {r6c4} = {57}
       C = {r7c6} = {18}

Elims: r23c6<>18, r4c5<>3457

[edit: add the following] Since set A is not entirely within the c6b5 intersection, my answer above is INCORRECT.
Code: Select all
 3      6      | 178    24     9      | 24     18     5
 4      127    | 1578   12378  2357-18| 29     18     6
 8      12     | 6      124    245-1  | 249    3      7
---------------+----------------------+---------------------
 6      58     | 2      18-3  A1358   | 35     7      9
 7      58     | 9      6     A58     | 1      4      2
 1      9      |B57    B347   B3457   | 35     6      8
---------------+----------------------+---------------------
 5      3      | 18     9     C18     | 7      2      4
 9      4      | 3      27     27     | 6      5      1
 2      17     | 4      5      6      | 8      9      3

Sets: A = {r45c6} = {1358}; B = {r6c456} = {3457}; C = {r7c6} = {18}
Elims: r2c6<>8, r3c6<>1, r4c5<>3

Using ...
Sets: A = {r456c6} = {134578}; B = {r6c45} = {3457}; C = {r7c6} = {18} ... is also correct.
Last edited by ronk on Tue Nov 18, 2008 1:13 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby re'born » Fri May 11, 2007 3:13 pm

underquark wrote:
Code: Select all
 
 *--------------------------------------------------------------------*
 | 8     *246   *126    | 9      5-6    245    | 3      7      14     |
 | 7     *234    5      |*134    13    *124    | 8      9      6      |
 | 9      346    16     | 346    7      8      | 5      2      14     |
 |----------------------+----------------------+----------------------|
 | 256    1      236    | 7      368    35     | 9      4      38     |
 | 45     7      39     | 13458  13589  145    | 2      6      38     |
 | 46     8      369    | 36     2      349    | 1      5      7      |
 |----------------------+----------------------+----------------------|
 | 3      9      4      | 15     15     6      | 7      8      2      |
 | 1      5      8      | 2      4      7      | 6      3      9      |
 | 26     26     7      | 38     389    39     | 4      1      5      |
 *--------------------------------------------------------------------*

I'm a human (I think); have I applied this technique correctly in eliminating 6 from r1c4? Are there puzzles where multiple succesive applications of this technique are required?


I don't think so. For instance, 1,2 and 4 do not all lie in common sectors, i.e.., there is no sector that contains all of your 1's.

Incidentally, there is an xy-chain that solves your puzzle:

5-[r4c6]-3-[r6c4]-6-[r6c1]-4-[r5c1]-5 implying r4c1, r5c456 <> 5.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby re'born » Fri May 11, 2007 3:18 pm

ronk wrote:
rep'nA wrote:In your first Four-Sector Disjoint Subset example, [...] I can spot the XYZ-Wing, but not the Sue De Coq that eliminates the 3 from [edit: r4c5] and the 1 from r3c6. I suppose it should also eliminate the 1 and 8 from r2c6, but this isn't needed in your example.

Because of the added cell r6c5, this Sue de Coq is a bit unusual.
Code: Select all
 17     3      6      | 178    24     9      | 24     18     5
 59     4      127    | 1578   12378 -12357-8| 29     18     6
 59     8      12     | 6      124   -1245   | 249    3      7
----------------------+----------------------+---------------------
 4      6      58     | 2      1-38  A1358   | 35     7      9
 3      7      58     | 9      6     A58     | 1      4      2
 2      1      9      |B57    A347   A3457   | 35     6      8
----------------------+----------------------+---------------------
 6      5      3      | 18     9     C18     | 7      2      4
 8      9      4      | 3      27     27     | 6      5      1
 17     2      17     | 4      5      6      | 8      9      3

Sets:  A = {r456c6,r6c5} = {134578}
       B = {r6c4} = {57}
       C = {r7c6} = {18}

Elims: r23c6<>18, r4c5<>3457


Oooooh, that one was tricky. Thanks ronk!:D
re'born
 
Posts: 551
Joined: 31 May 2007

Postby underquark » Fri May 11, 2007 6:12 pm

rep'nA wrote:For instance, 1,2 and 4 do not all lie in common sectors, i.e.., there is no sector that contains all of your 1's.

Incidentally, there is an xy-chain that solves your puzzle:

5-[r4c6]-3-[r6c4]-6-[r6c1]-4-[r5c1]-5 implying r4c1, r5c456 <> 5.
Thanks; got it now (I think). It'd be way too easy my way.
underquark
 
Posts: 299
Joined: 06 September 2005

Postby Obi-Wahn » Fri May 11, 2007 10:07 pm

daj95376 wrote:Your 'Five-Sector Disjoint Subset' has a templates Achilles Heel in <6>.

You're right, I didn't filter for template checks.

But how about this Five-Sector Disjoint Subset?
Code: Select all
.....4....9.....5.81...9......4..7.....2.51.9.63.....8.4...3...9.7..6......8...35

After SSTS:
.------------.------------.-------------.
| 3   7   5  | 16  18  4  | 29-8 89  26 |
| 4   9   6  |*37  78  2  |*38   5   1  |
| 8   1   2  | 36  5   9  | 34   7   46 |
:------------+------------+-------------:
| 1   5   9  | 4   6   8  | 7    2   3  |
| 7   8   4  | 2   3   5  | 1    6   9  |
| 2   6   3  |*79  79  1  | 5    4   8  |
:------------+------------+-------------:
| 5   4   8  |*19  2   3  | 6    19  7  |
| 9   3   7  | 5  *14  6  |*248  18 *24 |
| 6   2   1  | 8   49  7  | 49   3   5  |
'------------'------------'-------------'

7 cells (*) sharing 7 different digits {1234789}.

r2 covers {3}
r8 covers {24}
c4 covers {79}
c7 covers {8}, 1 exclusion
b7 covers {1}


And here's a Six-Sector Disjoint Subset using all 9 digits yielding 8 exclusions (I like this one):
Code: Select all
7.6..5..43......9.......52......943.1....7..8...8....182..9..7.6.9...........3...

After SSTS:
.------------------------.------------------------.------------------------.
| 7      *189     6      | 239-1   23-18   5      |*138    *18      4      |
| 3       5       2      | 1467    14678   1468   | 178-6   9      *67     |
|*49      148-9   148    | 13679   13678   168    | 5       2      *367    |
:------------------------+------------------------+------------------------:
|*25      678     578    | 156     156     9      | 4       3      *27     |
| 1       3469    345    | 23456   23456   7      | 29      56      8      |
| 29-45   34679   3457   | 8       3456    246    | 79      56      1      |
:------------------------+------------------------+------------------------:
| 8       2       1345   | 1456    9       146    | 136     7       35-6   |
| 6       1347    9      | 1457    14578   1248   | 138     148     235    |
|*45      147     1457   | 124567  1245678 3      | 1268    148     9      |
'------------------------'------------------------'------------------------'

9 cells (*) sharing 9 different digits {123456789}.

r1 covers {18}, 3 exclusions
r4 covers {2}
c1 covers {45}, 2 exclusions
c9 covers {67}, 1 exclusion
b1 covers {9}, 1 exclusion
b3 covers {36}, 1 exclusion


underquark wrote:Are there puzzles where multiple succesive applications of this technique are required?

I also found examples for this, but the majority of DDS with bigger size I found so far consist of bivalue cells only, so I'm sure somebody would point out that these can be interpreted as bidirectional XY-Cycles (if I got this right).
Last edited by Obi-Wahn on Fri May 11, 2007 6:54 pm, edited 1 time in total.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby re'born » Fri May 11, 2007 10:49 pm

Obi-Wahn wrote:
But how about this Five-Sector Disjoint Subset?
Code: Select all
.....4....9.....5.81...9......4..7.....2.51.9.63.....8.4...3...9.7..6......8...35

After SSTS:
.------------.------------.-------------.
| 3   7   5  | 16  18  4  | 29-8 89  26 |
| 4   9   6  |*37  78  2  |*38   5   1  |
| 8   1   2  | 36  5   9  | 34   7   46 |
:------------+------------+-------------:
| 1   5   9  | 4   6   8  | 7    2   3  |
| 7   8   4  | 2   3   5  | 1    6   9  |
| 2   6   3  |*79  79  1  | 5    4   8  |
:------------+------------+-------------:
| 5   4   8  |*19  2   3  | 6    19  7  |
| 9   3   7  | 5  *14  6  |*248  18 *24 |
| 6   2   1  | 8   49  7  | 49   3   5  |
'------------'------------'-------------'

7 cells (*) sharing 7 different digits {1234789}.

r2 covers {3}
r8 covers {24}
c4 covers {79}
c7 covers {8}, 1 exclusion
b7 covers {1}



Very nice, though it is (perhaps) easier to spot the following BUG+2 deduction:
Code: Select all
 *--------------------------------------------------*
 | 3    7    5    | 16   18   4    | 29+8 89-  26   |
 | 4    9    6    | 37   78   2    | 38   5    1    |
 | 8    1    2    | 36   5    9    | 34   7    46   |
 |----------------+----------------+----------------|
 | 1    5    9    | 4    6    8    | 7    2    3    |
 | 7    8    4    | 2    3    5    | 1    6    9    |
 | 2    6    3    | 79   79   1    | 5    4    8    |
 |----------------+----------------+----------------|
 | 5    4    8    | 19   2    3    | 6    19   7    |
 | 9    3    7    | 5    14   6    | 28+4 18   24   |
 | 6    2    1    | 8    49   7    | 49   3    5    |
 *--------------------------------------------------*


[r1c8]-8-[r1c7]=8|4=[r8c7]=8=[r8c8]-8-[r1c8], and so r1c8<>8, solving the puzzle.



Obi-Wahn wrote:And here's a Six-Sector Disjoint Subset using all 9 digits yielding 8 exclusion (I like this one):
Code: Select all
7.6..5..43......9.......52......943.1....7..8...8....182..9..7.6.9...........3...

After SSTS:
.------------------------.------------------------.------------------------.
| 7      *189     6      | 239-1   23-18   5      |*138    *18      4      |
| 3       5       2      | 1467    14678   1468   | 178-6   9      *67     |
|*49      148-9   148    | 13679   13678   168    | 5       2      *367    |
:------------------------+------------------------+------------------------:
|*25      678     578    | 156     156     9      | 4       3      *27     |
| 1       3469    345    | 23456   23456   7      | 29      56      8      |
| 29-45   34679   3457   | 8       3456    246    | 79      56      1      |
:------------------------+------------------------+------------------------:
| 8       2       1345   | 1456    9       146    | 136     7       35-6   |
| 6       1347    9      | 1457    14578   1248   | 138     148     235    |
|*45      147     1457   | 124567  1245678 3      | 1268    148     9      |
'------------------------'------------------------'------------------------'

9 cells (*) sharing 9 different digits {123456789}.

r1 covers {18}, 3 exclusions
r4 covers {2}
c1 covers {45}, 2 exclusions
c9 covers {67}, 1 exclusion
b1 covers {9}, 1 exclusion
b3 covers {36}, 1 exclusion




Wow! Pardon the implied vulgarity, but that is frickin' awesome:!:
re'born
 
Posts: 551
Joined: 31 May 2007

Postby daj95376 » Sat May 12, 2007 12:49 am

Puzzle #1: But how about this Five-Sector Disjoint Subset?

Code: Select all
.....4....9.....5.81...9......4..7.....2.51.9.63.....8.4...3...9.7..6......8...35

r1c7    <> 8     XY-Chain   on [r1c5]
r1c9    <> 2     XY-Wing    on [r9c7]
r8c7    <> 2     XY-Wing    on [r9c7]

Puzzle #2: A Six-Sector Disjoint Subset using all 9 digits yielding 8 exclusions

Code: Select all
7.6..5..43......9.......52......943.1....7..8...8....182..9..7.6.9...........3...

  c8b6  -  56    Locked Pair
    b1  -  4     Locked Candidate (1)
r159    -  2     233 Swordfish
r6c1    <> 9     XY-Chain   on [r6c7]
  c9b3  -  67    Locked Pair
r4  b5  -  16    Locked Pair
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Sat May 12, 2007 1:19 am

Obi-Wahn wrote:And here's a Six-Sector Disjoint Subset using all 9 digits yielding 8 exclusions (I like this one):
Code: Select all
7.6..5..43......9.......52......943.1....7..8...8....182..9..7.6.9...........3...

After SSTS:
.------------------------.------------------------.------------------------.
| 7      *189     6      | 239-1   23-18   5      |*138    *18      4      |
| 3       5       2      | 1467    14678   1468   | 178-6   9      *67     |
|*49      148-9   148    | 13679   13678   168    | 5       2      *367    |
:------------------------+------------------------+------------------------:
|*25      678     578    | 156     156     9      | 4       3      *27     |
| 1       3469    345    | 23456   23456   7      | 29      56      8      |
| 29-45   34679   3457   | 8       3456    246    | 79      56      1      |
:------------------------+------------------------+------------------------:
| 8       2       1345   | 1456    9       146    | 136     7       35-6   |
| 6       1347    9      | 1457    14578   1248   | 138     148     235    |
|*45      147     1457   | 124567  1245678 3      | 1268    148     9      |
'------------------------'------------------------'------------------------'

9 cells (*) sharing 9 different digits {123456789}.

r1 covers {18}, 3 exclusions
r4 covers {2}
c1 covers {45}, 2 exclusions
c9 covers {67}, 1 exclusion
b1 covers {9}, 1 exclusion
b3 covers {36}, 1 exclusion

Very nice. I'm sure you're aware this may also be viewed as a continuous loop of three ALSs.

{ALS: r1c2=9|18|3=r1c78} -3- {ALS:r23c9=3|67|2=r4c9} -2- {ALS:r4c1=2|45|9=[r9c1|r3c1]} -9- {ALS:r1c2 ...}

Due to the continuous loop, all weak links are converted to strong links ... and the non-linking digits of each ALS become locked into the ALS.

But I can't help but think there's also a connection to constraint sets. In this particular case, the almost-locked-sets in r1, c1 and c9 are "derived strong constraint sets" which are "exactly covered" by weak sets in r4, b1 and b3.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Obi-Wahn » Tue May 15, 2007 12:12 am

Once again I realize that I'm at least one year behind you, because I only got interested in Sudoku by an article in the German edition of the Scientific American in March 2006.
I just found the thread about Subset Counting by aeb, of which my Distributed Disjoint Subsets are only a special case. I guess the reason why his thread didn't draw great attention was a lack of practical examples.

Maybe I can raise the stakes by extending DDS to Almost Distributed Disjoint Subsets. This works pretty much the same way as the fins work with Fish patterns. I allow one of the digits in the subset to break the DDS rule and have additional instances within the subset that don't see each other. This digit I called the outlaw. Now the ADDS can still yield an exclusion if there exists a candidate of the outlaw digit outside the chosen subset that sees all instances of this digit within the subset. If this candidate was true, it would remove the outlaw digit completely from the subset leaving us with N-1 digits for N cells, which is unsolvable. So this candidate can be eliminated.

I managed to extend my solver this way and it's still very fast. I can check hundreds of puzzles within just seconds. And it's probably still not optimal because I was glad to make it work at all.

ADDS is a generalization of XY-wing and XYZ-wing to more then 2 sectors (Z being the outlaw in these cases). Here is a simple example to maybe make it clearer what I'm talking about.

Code: Select all
.7..9.8..21...3.....4..2...98.....3.7....61.....3...2........4..2.81...6..5...79.

After SSTS there are 3 ADDS, one being an XYZ-wing.
Code: Select all
.---------------.---------------.---------------.
|*356  7   *36  | 4    9    15  | 8    16   2   |
| 2    1    89  | 567  5678 3   | 459  67   459 |
| 58-6 569  4   | 1567 5678 2   | 59   167  3   |
:---------------+---------------+---------------:
| 9    8    26  | 1257 2457 157 | 456  3    457 |
| 7    345  23  | 9    245  6   | 1    8    45  |
|*56   456  1   | 3    457  8   | 4569 2    4579|
:---------------+---------------+---------------:
| 1368 369  789 | 567  3567 579 | 2    4    18  |
| 4    2    79  | 8    1    79  | 3    5    6   |
| 18   36   5   | 26   236  4   | 7    9    18  |
'---------------'---------------'---------------'

3 cells (*) sharing 3 digits {356}.

r1 covers {3}
c1 covers {5}
digit 6 is the outlaw, but all instances can be seen by r3c1.


.----------------.---------------.---------------.
|*356   7   *36  | 4    9    15  | 8    16   2   |
| 2     1    89  | 567  5678 3   | 459  67   459 |
| 68-5 *569  4   | 1567 5678 2   |*59   167  3   |
:----------------+---------------+---------------:
| 9     8    26  | 1257 2457 157 | 456  3    457 |
| 7     345  23  | 9    245  6   | 1    8    45  |
| 56    456  1   | 3    457  8   | 4569 2    4579|
:----------------+---------------+---------------:
| 1368  369  789 | 567  3567 579 | 2    4    18  |
| 4     2    79  | 8    1    79  | 3    5    6   |
| 18    36   5   | 26   236  4   | 7    9    18  |
'----------------'---------------'---------------'

4 cells (*) sharing 4 digits {3569}.

b1 covers {36}.
r3 covers {9}.
digit 5 is the outlaw, but all instances can be seen by r3c1.


.----------------.-----------------.---------------.
| 356   7    36  | 4      9    15  | 8    16   2   |
| 2     1    89  | 567    5678 3   | 459  67   459 |
| 568   569  4   | 1567   5678 2   | 59   167  3   |
:----------------+-----------------+---------------:
| 9     8    26  | 157-2  2457 157 | 456  3    457 |
| 7    *345  23  | 9     *245  6   | 1    8   *45  |
| 56    456  1   | 3      457  8   | 4569 2    4579|
:----------------+-----------------+---------------:
| 1368  369  789 | 567    3567 579 | 2    4    18  |
| 4     2    79  | 8      1    79  | 3    5    6   |
| 18   *36   5   |*26     36-2 4   | 7    9    18  |
'----------------'-----------------'---------------'

5 cells (*) sharing 5 digits {23456}.

r5 covers {45}.
c2 covers {3}.
r9 covers {6}.
digit 2 is the outlaw, but both instances can be seen by r4c4 and r9c5.


Compared with the many possible eliminations of DDS, ADDS only yields few exclusion candidates, but it's many times more frequent. More than half of the remaining unsolved of my randomly generated puzzles can be solved with ADDS.

The following is the most complex example I found so far:
Code: Select all
..4..83...2......9168.5..2.5....7....3.1...57..9.....16...891.....7....2...6.....

After SSTS there's a Five-Sector Disjoint Subset:
.----------------.----------------.-----------------.
|*79   *59   4   | 2    67    8   | 3    1     *56  |
| 3-7   2    357 | 4    167   16  | 56   8      9   |
| 1     6    8   | 9    5     3   | 7    2      4   |
:----------------+----------------+-----------------:
| 5    *48   1   |*38   246-3 7   | 2469 469-3 *36  |
|*24    3    6   | 1    9     24  | 8    5      7   |
|*247   78-4 9   | 358  2346  2456| 246  346    1   |
:----------------+----------------+-----------------:
| 6     47   2   | 35   8     9   | 1    47     35  |
| 8     159  35  | 7    134   145 | 4569 3469   2   |
| 349-7 159  357 | 6    1234  1245| 459  3479   8   |
'----------------'----------------'-----------------'

8 cells (*) sharing 8 candidates {23456789}.
5 sectors are involved: r14c19b4


SSTS now lead to a Two-Sector Almost Disjoint Subset:
.---------------.------------------.---------------.
| 79   59   4   | 2    67     8    | 3    1    56  |
| 3    2    57  | 4    167    16   | 56   8    9   |
| 1    6    8   | 9    5      3    | 7    2    4   |
:---------------+------------------+---------------:
| 5    48   1   | 38   246    7    | 2469 469  36  |
| 24   3    6   | 1    9      24   | 8    5    7   |
| 247  78   9   | 58   2346   2456 | 246  346  1   |
:---------------+------------------+---------------:
| 6    47   2   | 35   8      9    | 1    47   35  |
| 8   *159 *35  | 7   *134   *145  | 4569 3469 2   |
|*49   159  357 | 6    123-4  125-4| 459  3479 8   |
'---------------'------------------'---------------'

5 cells (*) sharing 5 digits {13459}, digit 4 is the outlaw.
2 sectors are involved: r8b7


Again SSTS lead to a Seven-Sector Almost Disjoint Subset:
.---------------.----------------.---------------.
|*79   59   4   | 2   *67    8   | 3    1    56  |
| 3    2    57  | 4    167  *16  | 56   8    9   |
| 1    6    8   | 9    5     3   | 7    2    4   |
:---------------+----------------+---------------:
| 5   *48   1   |*38   246   7   | 2469 469  36  |
| 2-4  3    6   | 1    9    *24  | 8    5    7   |
| 247  78   9   | 58   2346  2456| 246  346  1   |
:---------------+----------------+---------------:
| 6    47   2   |*35   8     9   | 1    47   35  |
| 8    159  35  | 7    134   145 | 569  369  2   |
|*49   159  357 | 6    123  *125 | 459  3479 8   |
'---------------'----------------'---------------'

9 cells (*) sharing 9 digits {123456789}, digit 4 is the outlaw.
7 sectors are involved: r14c146b28.

From here SSTS and finned X-Wings solve the puzzle.


The next step would be adding multiplicities like aeb used (allowing each digit to be covered by more than one sector). But I still have to think about how to do it efficiently.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby ronk » Fri May 18, 2007 7:35 pm

Obi-Wahn wrote:Once again I realize that I'm at least one year behind you ...

If you're referring to me, I doubt you're very far behind at all. And your obviously better math and programming skills probably make us close to even.:)

The following is the most complex example I found so far:
Code: Select all
..4..83...2......9168.5..2.5....7....3.1...57..9.....16...891.....7....2...6.....

[edit: some elimination steps not quoted]

Again SSTS lead to a Seven-Sector Almost Disjoint Subset:
.---------------.----------------.---------------.
|*79   59   4   | 2   *67    8   | 3    1    56  |
| 3    2    57  | 4    167  *16  | 56   8    9   |
| 1    6    8   | 9    5     3   | 7    2    4   |
:---------------+----------------+---------------:
| 5   *48   1   |*38   246   7   | 2469 469  36  |
| 2-4  3    6   | 1    9    *24  | 8    5    7   |
| 247  78   9   | 58   2346  2456| 246  346  1   |
:---------------+----------------+---------------:
| 6    47   2   |*35   8     9   | 1    47   35  |
| 8    159  35  | 7    134   145 | 569  369  2   |
|*49   159  357 | 6    123  *125 | 459  3479 8   |
'---------------'----------------'---------------'

9 cells (*) sharing 9 digits {123456789}, digit 4 is the outlaw.
7 sectors are involved: r14c146b28.

This deduction is particularly interesting because the excluded candidate sees three candidates within the "pattern" instead of two. Do you have any other examples like that:?:

FWIW, your deduction in network form (using nice loop notation) is ...
Code: Select all
      ---4---{ALS:r4c2=4|3=r4c4}---3---r7c4---5--
    /                                             \
r5c1-4-{ALS:r9c1=4|7=r1c1}-7-{ALS:r1c5=7|1=r2c6}-1-{AALS:r9c6=15|4=r5c6}-4-r5c1

The next step would be adding multiplicities like aeb used (allowing each digit to be covered by more than one sector). But I still have to think about how to do it efficiently.

Hmm. You might already effectively be doing that. In any case, congratulations for your DDS and ADDS implementations.
Last edited by ronk on Sun May 20, 2007 12:09 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Obi-Wahn » Sun May 20, 2007 3:46 pm

What I meant was, that every time I think I am working on something new, I sooner or later discover that somebody posted the same idea already about a year ago ...

ronk wrote:This deduction is particularly interesting because the excluded candidate sees three candidates within the "pattern" instead of two. Do you have any other examples like that:?:


I think this one is similar:
Code: Select all
..8...75...71.3..8...4..3.....9...7....3..8...2...1..537...9...1.......65.....4..

After SSTS:
.---------------.---------------.---------------.
| 4    3    8   | 26   9    26  | 7    5    1   |
| 269  69   7   | 1    5    3   | 26   4    8   |
| 26   15   15  | 4    78   78  | 3    26   9   |
:---------------+---------------+---------------:
| 68   4    156 | 9   *268  568 |*12   7    3   |
| 679  15   1569| 3    267  567 | 8    12   4   |
| 78   2    3   |*78   4    1   | 69   69   5   |
:---------------+---------------+---------------:
| 3    7    4   | 56  *16   9   | 5-1  8    2   |
| 1    8    2   |*57   37   4   |*59  *39   6   |
| 5    69   69  | 28   13   28  | 4   *13   7   |
'---------------'---------------'---------------'

8 cells (*) sharing 8 digits {12356789}, digit 1 is the outlaw.
6 sectors are involved: r48c458b5.


I have added Multiplicities now to DDS, but it's very slow for puzzles with many empty cells. One thing is that the calculation of multiplicities isn't trivial.
The question is, how many times can the same digit be placed within a given set of cells without violating the Sudoku rules. Or in other terms, what is the least number of sectors that is needed to cover all cells of the set. And this is equivalent to the Minimal Set Cover problem which is NP hard.
The other thing is, that I couldn't find a way for an early search termination. For DDS there can't be more than 9 cells within the set, because every digit is allowed only once. With multiplicities the number of cells is unlimited, so for an exhaustive search all available empty cells must be added. This leads to millions of nodes in the search tree for which multiplicities must be calculated.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Next

Return to Advanced solving techniques

cron