Extended Disjoint Subset Links

Advanced methods and approaches for solving Sudoku puzzles

Extended Disjoint Subset Links

Postby rubylips » Fri Dec 09, 2005 11:05 am

I've talked about the rather inelegantly-named Extended Disjoint Subset Links over the past week - here's a concrete example.

Code: Select all
 . . . | 9 . 8 | . 6 .
 3 . . | . . . | 2 . .
 . . 1 | . 2 . | . . .
-------+-------+------
 . 8 . | 1 . . | . 9 .
 . . 2 | . . . | 3 . .
 . 7 . | . . 5 | . 4 .
-------+-------+------
 . . . | . 4 . | 6 . .
 . . 5 | . . . | . . 1
 . 9 . | 6 . 7 | . . .

Standard techniques take us so far:

Code: Select all
  2|4|5|7  2|4|5  4|7 |        9    1|3|5        8 |      1|5        6      3|4|5
        3  4|5|6    9 |    4|5|7    5|6|7    1|4|6 |        2  1|5|7|8    4|5|7|8
        8  4|5|6    1 |  3|4|5|7        2    3|4|6 |  4|5|7|9    3|5|7  3|4|5|7|9
----------------------+----------------------------+-----------------------------
      4|5      8  3|6 |        1    3|6|7  2|3|4|6 |      5|7        9    2|5|6|7
    4|5|9  1|4|5    2 |    4|7|8  6|7|8|9    4|6|9 |        3  1|5|7|8    5|6|7|8
      1|9      7  3|6 |    2|3|8  3|6|8|9        5 |      1|8        4      2|6|8
----------------------+----------------------------+-----------------------------
      2|7  1|2|3  7|8 |  2|3|5|8        4  1|2|3|9 |        6  2|3|5|8    3|5|8|9
        6  2|3|4    5 |    2|3|8    3|8|9    2|3|9 |  4|7|8|9  2|3|7|8          1
    1|2|4      9  4|8 |        6  1|3|5|8        7 |    4|5|8  2|3|5|8    3|4|5|8

whereupon we note:

Code: Select all
Consider the chain r7c6-1-r7c2-3-r8c2=<4|9>=r7c6.
When the cell r7c6 contains the value 9, it likewise contains the value 1 - a contradiction.
Therefore, the cell r7c6 cannot contain the value 9.
- The move r7c6:=9 has been eliminated.
The cell r7c9 is the only candidate for the value 9 in Row 7.

The point is that the cells {r8c2,r8c4,r8c5,r8c6} form an Almost Locked Set, so when r7c6 takes the value 9, the set is locked, which forces r8c2 to take the value 4. Of course, we could have solved the puzzle without the link but the resulting chain is very short and the logic necessary to follow the link falls well within 'human' capabilities.

After a couple more observations:

Code: Select all
2. The cell r3c7 is the only candidate for the value 9 in Row 3.
3. The value 4 in Box 9 must lie in Column 7.
- The move r9c9:=4 has been eliminated.

  2|4|5|7  2|4|5  4|7 |        9    1|3|5        8 |    1|5        6    3|4|5
        3  4|5|6    9 |    4|5|7    5|6|7    1|4|6 |      2  1|5|7|8  4|5|7|8
        8  4|5|6    1 |  3|4|5|7        2    3|4|6 |      9    3|5|7  3|4|5|7
----------------------+----------------------------+-------------------------
      4|5      8  3|6 |        1    3|6|7  2|3|4|6 |    5|7        9  2|5|6|7
    4|5|9  1|4|5    2 |    4|7|8  6|7|8|9    4|6|9 |      3  1|5|7|8  5|6|7|8
      1|9      7  3|6 |    2|3|8  3|6|8|9        5 |    1|8        4    2|6|8
----------------------+----------------------------+-------------------------
      2|7  1|2|3  7|8 |  2|3|5|8        4    1|2|3 |      6  2|3|5|8        9
        6  2|3|4    5 |    2|3|8    3|8|9    2|3|9 |  4|7|8  2|3|7|8        1
    1|2|4      9  4|8 |        6  1|3|5|8        7 |  4|5|8  2|3|5|8    3|5|8

we find another link:

Code: Select all
Consider the chain r7c8=<5|3>=r9c9~3~r1c9-3-r1c5-1-r9c5=5=r7c8.
When the cell r7c8 contains the value 5, the chain is self-contradicting.
Therefore, the cell r7c8 cannot contain the value 5.
- The move r7c8:=5 has been eliminated.
The cell r7c4 is the only candidate for the value 5 in Row 7.

Here an Almost Locked Set is formed by the cells {r9c3,r9c7,r9c9}, so when r7c8 takes a 5, r9c9 must take a 3. The final extended link works because when r9c5 doesn't take a 5, one of {r9c7,r9c8,r9c9} must, which means that r7c8 doesn't.

Yet another extended disjoint subset link has to be found in order to progress beyond the last elimination. (It's seldom necessary to use these links but this puzzle provides an unusual number of examples).

Code: Select all
  2|4|5|7  2|4|5  4|7 |      9    1|3|5        8 |    1|5        6    3|4|5
        3  4|5|6    9 |    4|7    5|6|7    1|4|6 |      2  1|5|7|8  4|5|7|8
        8  4|5|6    1 |  3|4|7        2    3|4|6 |      9    3|5|7  3|4|5|7
----------------------+--------------------------+-------------------------
      4|5      8  3|6 |      1    3|6|7  2|3|4|6 |    5|7        9  2|5|6|7
    4|5|9  1|4|5    2 |  4|7|8  6|7|8|9    4|6|9 |      3  1|5|7|8  5|6|7|8
      1|9      7  3|6 |  2|3|8  3|6|8|9        5 |    1|8        4    2|6|8
----------------------+--------------------------+-------------------------
      2|7  1|2|3  7|8 |      5        4    1|2|3 |      6    2|3|8        9
        6  2|3|4    5 |  2|3|8    3|8|9    2|3|9 |  4|7|8  2|3|7|8        1
    1|2|4      9  4|8 |      6    1|3|8        7 |  4|5|8  2|3|5|8    3|5|8

Consider the chain r9c5=<8|4>=r8c2~4~r9c3~8~r9c5.
When the cell r9c5 contains the value 8, the chain is self-contradicting.
Therefore, the cell r9c5 cannot contain the value 8.


The following puzzles are left as (fairly difficult) exercises:

Code: Select all
I.

 . . 3 | . . 6 | . . .
 . 8 . | . . . | . 9 .
 . . 7 | . 2 . | . . 4
-------+-------+------
 . 9 . | . . 8 | . . 5
 . . 4 | . . . | 6 . .
 2 . . | 1 . . | . 7 .
-------+-------+------
 7 . . | . 4 . | 2 . .
 . 5 . | . . . | . 3 .
 . . . | 9 . . | 1 . .

II.

 . . 3 | . 6 . | . . 2
 . . 5 | . . 7 | . . .
 6 . . | . . . | . 1 .
-------+-------+------
 . . 1 | . . 5 | . 4 .
 . 6 . | . . . | . 3 .
 . 8 . | 1 . . | 9 . .
-------+-------+------
 . 9 . | . . . | . . 8
 . . . | 4 . . | 3 . .
 7 . . | . 2 . | 6 . .

III.

 . 3 . | 9 . . | . . .
 2 . . | 7 . . | . . 6
 . . 1 | . . 6 | . 5 .
-------+-------+------
 . . 9 | . . . | 2 . .
 8 . . | . . . | . . 4
 . . 5 | . . . | 3 . .
-------+-------+------
 . 4 . | 2 . . | 9 . .
 6 . . | . . 8 | . . 7
 . . . | . . 5 | . 1 .

IV.

 . . . | 4 . . | . . 8
 . 7 5 | . . . | 9 . .
 . . 2 | . . 7 | . 1 .
-------+-------+------
 . . 8 | . . 2 | . . .
 6 . . | . . . | . . 3
 . . . | 9 . . | 5 . .
-------+-------+------
 . 9 . | 7 . . | 1 . .
 . . 1 | . . . | 8 2 .
 3 . . | . . 6 | . . .
rubylips
 
Posts: 149
Joined: 01 November 2005

Re: Extended Disjoint Subset Links

Postby ronk » Fri Dec 09, 2005 1:50 pm

rubylips wrote:
Code: Select all
Consider the chain r7c6-1-r7c2-3-r8c2=<4|9>=r7c6.
When the cell r7c6 contains the value 9, it likewise contains the value 1 - a contradiction.

Doesn't candidate 2 first need to be eliminated from both r8c2 and r7c2?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby rubylips » Fri Dec 09, 2005 10:49 pm

I don't think so. The key points are that there are just two candidates for the value 3 in Column 2 and for the value 1 in Row 7.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby ronk » Sat Dec 10, 2005 12:22 am

rubylips wrote:there are just two candidates for the value 3 in Column 2

Thanks, I missed that.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Bob Hanson » Sat Dec 10, 2005 8:16 pm

aside: I like to suggest not including those | in configuration descriptions. Is there some significance to them? They hardly seem necessary, and (for me at least) they make it harder to see what's where. And, unfortunately, they cause code to wrap, I think.

The point is that the cells {r8c2,r8c4,r8c5,r8c6} form an Almost Locked Set, so when r7c6 takes the value 9, the set is locked, which forces r8c2 to take the value 4. Of course, we could have solved the puzzle without the link but the resulting chain is very short and the logic necessary to follow the link falls well within 'human' capabilities.


In my mind the point is not that {r8c2,r8c4,r8c5,r8c6} forms an almost-locked set, but that {r8c4,r8c5,r8c6} {238 389 239} does. This is then doubly-weakly linked to the "almost-almost locked set" 234 at r8c2. It is this double weak link that forces 234 to be 4 when the 9 is removed.

But it seems easier for me at least just to use conjugate pairs to see that 9 in r7c6 require no 9 in r7c9, so a 9 in r8c7, so no 4 there, forcing the 4 in r8c2.
Bob Hanson
 
Posts: 75
Joined: 04 December 2005


Return to Advanced solving techniques