The New Sudoku Players' Forum

[rubylips]

I'm yet to generalize the Conditional Disjoint Subsets pattern to its fullest extent but, as the pattern stands, its characteristics are a cell with two candidates, which, according to the candidate chosen, cretaes a disjoint subset in a line (i.e. a row or column) or a box. When the two disjoint subsets share common values, those values should be excluded from the line/box intersection.

An example:

Code: Select all

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


Thirty-three straightforward moves take us to the following position:

Code: Select all

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

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


whereupon:

Code: Select all

Consider the cell r6c3.
When it contains the value 1, the values 5 and 8 in Row 6 must occupy the cells r6c4 and r6c6 in some order.
When it contains the value 3, the values 2 and 8 in Box 4 must occupy the cells r4c1 and r4c3 in some order.
Whichever value it contains, the cells r6c1 and r6c2 cannot contain the value 8.
- The move r6c1:=8 has been eliminated.
The cell r4c1 is the only candidate for the value 8 in Column 1.


after which the puzzle is once more straightforward.

As the above example makes clear, the disjoint subsets are sometimes trivial. Here are further examples of the pattern that have been left as exercises:

Code: Select all

I.

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

II.

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

III.

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


The last example is particularly interesting as it involves three examples of the pattern.

[Jeff]

Code: Select all

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

Interestingly, the cells involved also satisfy the requirement of an xy-chain for the same elimination, ie.

[r6c1]-[r4c1]-[r4c3]-[r6c3]-[r6c6]-[r6c1] => r6c1<>8

[ronk]

Here are further examples of the pattern that have been left as exercises

In your first two examples, all I could find was one xy-wing each ... at r2c1, r3c2, and r7c2 in ...

Code: Select all

 *--------------------------------------------------------------------*
 | 169    5      16     | 27     279    4      | 3      17     8      |
 | 18     4      2      | 3      78     6      | 9      17     5      |
 | 7      89     3      | 1      5      89     | 2      6      4      |
 |----------------------+----------------------+----------------------|
 | 12358  6      4      | 257    2789   1389   | 78     23     19     |
 | 1238   178    9      | 4      2678   138    | 5      23     16     |
 | 12358  178    15     | 257    26789  1389   | 78     4      169    |
 |----------------------+----------------------+----------------------|
 | 19     19     8      | 6      3      7      | 4      5      2      |
 | 56     3      56     | 9      4      2      | 1      8      7      |
 | 4      2      7      | 8      1      5      | 6      9      3      |
 *--------------------------------------------------------------------*

... and at r3c4, r2c6, and r3c7 in ...

Code: Select all

 *--------------------------------------------------*
 | 57   2    3    | 6    57   1    | 9    4    8    |
 | 59   8    6    | 259  4    39   | 123  7    13   |
 | 79   1    4    | 29   37   8    | 23   5    6    |
 |----------------+----------------+----------------|
 | 8    9    7    | 1    2    4    | 6    3    5    |
 | 6    4    1    | 59   35   39   | 7    8    2    |
 | 3    5    2    | 8    6    7    | 14   9    14   |
 |----------------+----------------+----------------|
 | 4    7    5    | 3    1    2    | 8    6    9    |
 | 1    6    8    | 7    9    5    | 34   2    34   |
 | 2    3    9    | 4    8    6    | 5    1    7    |
 *--------------------------------------------------*

The last example is particularly interesting as it involves three examples of the pattern.

There I found a couple of xyz-wings.

Does your conditional disjoint subset technique subsume both of those?

[stuartn]

stuartn

Consider the cell r6c3.
When it contains the value 1, the values 5 and 8 in Row 6 must occupy the cells r6c4 and r6c6 in some order.
When it contains the value 3, the values 2 and 8 in Box 4 must occupy the cells r4c1 and r4c3 in some order.
Whichever value it contains, the cells r6c1 and r6c2 cannot contain the value 8.
- The move r6c1:=8 has been eliminated.
The cell r4c1 is the only candidate for the value 8 in Column 1.

Looks to me like a bog standard forcing chain

If 13 = 1, then 18 must become 8 and 178 = 17
If 13 = 3, then 23 must become 2, 28 = 8 and 178 = 17

why give it a confusing name?

[rubylips]

Looks to me like a bog standard forcing chain
why give it a confusing name?

Just to confirm the point, without the new technique the solver would return the equally transparent:

Code: Select all

Consider the chain r1c4-4-r1c1-2-r4c1-8-r4c4.
When the cell r4c4 contains the value 4, some other value must occupy the cell r1c4, which means that the value 8 must occupy the cell r4c4 - a contradiction.
Therefore, the cell r4c4 cannot contain the value 4.
- The move r4c4:=4 has been eliminated.
The cell r5c6 is the only candidate for the value 4 in Box 5.


Yours is a fair point with regard to the example given. I chose the example as it's the simplest I could find, whereas it would have been better to present an example, such as the following, where the new technique saves effort compared to forcing chains. (Personally, I prefer the new pattern as I find it easier to spot).

Code: Select all

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


reduces to:

Code: Select all

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


With Conditional Disjoint Subsets:

Code: Select all

Consider the cell r9c6.
When it contains the value 7, the values 1 and 5 in Row 9 must occupy the cells r9c3 and r9c8 in some order.
When it contains the value 8, the values 4 and 5 in Box 8 must occupy the cells r8c4 and r8c6 in some order.
Whichever value it contains, the cells r9c4 and r9c5 cannot contain the value 5.
- The move r9c5:=5 has been eliminated.
The cell r5c5 is the only candidate for the value 5 in Column 5.


By way of comparison, here's a solution that uses Forcing Chains. (It might be possible to find something more direct):

Code: Select all

Consider the chain r5c2-2-r9c2-6-r9c5-5-r5c5.
When the cell r5c2 contains the value 5, so does the cell r5c5 - a contradiction.
Therefore, the cell r5c2 cannot contain the value 5.
- The move r5c2:=5 has been eliminated.
Consider the chain r8c1-2-r9c2-6-r9c5-5-r8c4.
When the cell r8c1 contains the value 5, so does the cell r8c4 - a contradiction.
Therefore, the cell r8c1 cannot contain the value 5.
- The move r8c1:=5 has been eliminated.
Consider the chain r8c4-5-r9c5-6-r9c2-2-r9c9-8-r8c9.
When the cell r8c4 contains the value 8, so does the cell r8c9 - a contradiction.
Therefore, the cell r8c4 cannot contain the value 8.
- The move r8c4:=8 has been eliminated.
Consider the chain r2c6-1-r6c6-2-r6c1~2~r8c1-2-r8c9-8-r8c6.
When the cell r2c6 contains the value 8, so does the cell r8c6 - a contradiction.
Therefore, the cell r2c6 cannot contain the value 8.
- The move r2c6:=8 has been eliminated.
Consider the chain r3c2-9-r3c5~9~r7c5-6-r9c5-6-r9c2-2-r5c2.
When the cell r5c2 contains the value 9, some other value must occupy the cell r3c2, which means that the value 2 must occupy the cell r5c2 - a contradiction.
Therefore, the cell r5c2 cannot contain the value 9.
- The move r5c2:=9 has been eliminated.
The value 9 in Box 5 must lie in Row 5.
- The moves r4c4:=9, r4c6:=9, r6c4:=9 and r6c6:=9 have been eliminated.
The value 9 in Box 1 must lie in Column 2.
- The move r2c3:=9 has been eliminated.
Consider the chain r5c9~3~r5c2-2-r9c2-2-r8c1-6-r8c7-3-r7c9.
When the cell r5c9 contains the value 3, so does the cell r7c9 - a contradiction.
Therefore, the cell r5c9 cannot contain the value 3.
- The move r5c9:=3 has been eliminated.
Consider the chain r5c5-5-r9c5-6-r9c2-2-r8c1~2~r6c1-2-r6c6-1-r6c4.
When the cell r6c4 contains the value 5, some other value must occupy the cell r5c5, which means that the value 1 must occupy the cell r6c4 - a contradiction.
Therefore, the cell r6c4 cannot contain the value 5.
- The move r6c4:=5 has been eliminated.
Consider the chain r9c5~5~r9c3-1-r9c8-1-r7c8-7-r7c6-9-r7c5-6-r9c5.
When the cell r9c5 contains the value 5, it likewise contains the value 6 - a contradiction.
Therefore, the cell r9c5 cannot contain the value 5.
- The move r9c5:=5 has been eliminated.
The cell r5c5 is the only candidate for the value 5 in Column 5.


The reason that Conditional Disjoint Subsets works so well here is that the subsets used in the construction each have more than one cell, so can't be replicated by chains as easily.

[rubylips]

There I found a couple of xyz-wings.
Does your conditional disjoint subset technique subsume both of those?

The simplest Conditional Disjoint Subset examples, such as those given in my original post, correspond, as you point out, directly to straightforward forcing chains. Please see my reply to stuartn for an example of the pattern that has, as far as I see, no direct forcing chains equivalent.

[Nick70]

By way of comparison, here's a solution that uses Forcing Chains. (It might be possible to find something more direct)

Yes:

Code: Select all

r7c8=7 => r9c8<>7 => r9c8=1 => r9c3<>1 => r9c3=5 => r9c5<>5 => r5c5=5
r7c6=7 => r7c6<>9 => r7c5=9 => r7c5<>6 => r9c5=6 => r9c5<>5 => r5c5=5

[rubylips]

Yes:

Code: Select all

r7c8=7 => r9c8<>7 => r9c8=1 => r9c3<>1 => r9c3=5 => r9c5<>5 => r5c5=5
r7c6=7 => r7c6<>9 => r7c5=9 => r7c5<>6 => r9c5=6 => r9c5<>5 => r5c5=5

Correct me if I'm wrong, but these chains have been found through the application of reverse logic in the full knowledge of the target cell. There's no way that a human could reasonably be expected to spot these chains, so they don't provide a fair comparison with the Conditional Disjoint Subsets method.

[ronk]

With Conditional Disjoint Subsets:

Code: Select all

Consider the cell r9c6.
When it contains the value 7, the values 1 and 5 in Row 9 must occupy the cells r9c3 and r9c8 in some order.
When it contains the value 8, the values 4 and 5 in Box 8 must occupy the cells r8c4 and r8c6 in some order.
Whichever value it contains, the cells r9c4 and r9c5 cannot contain the value 5.
- The move r9c5:=5 has been eliminated.
The cell r5c5 is the only candidate for the value 5 in Column 5.


So why don't you consider ...
r9c6=7 => r9c8=1 => r9c3=5 => r9c5<>5, and
r9c6=8 => r8c6=4 => r8c4=5 => r9c5<>5
... to be forcing chains?

And what exactly is disjoint in that particular example?

[Nick70]

Correct me if I'm wrong, but these chains have been found through the application of reverse logic in the full knowledge of the target cell.

My program scans the whole grid and selects the "best" chain--where best means shorter, easier to follow, and that causes a big number to placed if possible.

There's no way that a human could reasonably be expected to spot these chains, so they don't provide a fair comparison with the Conditional Disjoint Subsets method.

I wasn't trying to do that. I just showed a simpler solution than the one found by your program since you wondered if it existed.

[bennys]

Code: Select all

+-------------+-------------+-------------+
 | 24  7   8   | 24  6   5   | 1   9   3   |
 | 9   3   24  | 248 1   48  | 56  7   56  |
 | 5   1   6   | 7   3   9   | 8   4   2   |
 +-------------+-------------+-------------+
 | 28  9   23  | 458 7   6   |*35  1  *45  |
 |*17  6   5   | 3   9   14  | 2   8  *47  |
 | 178 4  *13  | 58  2   18  | 357 6   9   |
 +-------------+-------------+-------------+
 | 6   5   7   | 1   4   2   | 9   3   8   |
 | 14  2   14  | 9   8   3   | 67  5   67  |
 | 3   8   9   | 6   5   7   | 4   2   1   |
 +-------------+-------------+-------------+

A={R5C1,R6C3}
B={R4C7,R4C9,R5C9}
Both are almost locked and both can have 7 only in R5
Which mean that any placement that remove candidate from both( other then 7) sets is impossible.
for example R4C3 = 3 remove 3 from A and B.

[rubylips]

And what exactly is disjoint in that particular example?

OK, here's a better example from the I didn't see this argument used before thread that should clarify that it's not necessary for a chain of any form to exist in order for the construction to work. Much credit is due to bennys.

Code: Select all

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

Consider the cell r2c1.
When it contains the value 8, the value 6 in Column 1 must occupy the cell r9c1.
When it contains the value 3, the values 4, 6 and 9 in Box 1 must occupy the cells r1c2, r1c3 and r2c2 in some order.
Whichever value it contains, the cells r1c1 and r3c1 cannot contain the value 6.
- The move r3c1:=6 has been eliminated.
The cell r3c8 is the only candidate for the value 6 in Row 3.


Here, we clearly don't know exactly where the values 4 and 9 will go if the cell r2c1 contains a 3, nor do we have to deduce that the 6 will reside at r1c2 - it's sufficient to know that, since the cells r1c2, r1c3 and r2c2 are certain to contain the values 4, 6 and 9 (and thus set up a disjoint subset of Box 1), the value 6 cannot occur in Column 1.

[rubylips]

I wasn't trying to do that. I just showed a simpler solution than the one found by your program since you wondered if it existed.

Thank-you. My solver simply spits out the shortest chain it finds, regardless of whether the candidate it eliminates is 'critical'.

[ronk]

Consider the cell r2c1.
When it contains the value 8, the value 6 in Column 1 must occupy the cell r9c1.
When it contains the value 3, the values 4, 6 and 9 in Box 1 must occupy the cells r1c2, r1c3 and r2c2 in some order.
Whichever value it contains, the cells r1c1 and r3c1 cannot contain the value 6.

Thanks, I think I got it now. It's like forcing chains with at least one multiplet ... as opposed to all singlets. For this specific example, and taking notational liberty:

r2c1=8 => r9c1=6 => r3c1<>6
r2c1=3 => {r1c2,r1c3,r2c2}={469} => r3c1<>6

Thanks also for the link, Ron