The New Sudoku Players' Forum

by **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

by **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 | ^-----------------------------------------------------------------------------^

by **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?

by **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?

by **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.

by **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.

by **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!

by **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.

by **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).

by **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 :!:

by **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

by **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.

by **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.

by **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.

by **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.