The New Sudoku Players' Forum

[bennys]

Here the fastest way that I can see.

Code: Select all

+----------------+----------------+----------------+
| 579  5789 12   | 3    4    12   | 589  59   6    |
| 459  6    249  | 7    8    29   | 1    3459 3459 |
| 34  *89   1349 |*19   6    5    |*489  7    2    |
+----------------+----------------+----------------+
| 79   4    8    | 5    2    79   | 3    6    1    |
| 6    1    5    | 89   3    489  | 7    2    49   |
| 2    3    79   | 6    1    479  | 459  8    459  |
+----------------+----------------+----------------+
| 1    2    39   | 4    7    38   | 6    359  3589 |
| 3457 57   6    | 128  9    138  | 24   134  3478 |
| 8    79   3479 | 12   5    6    | 249  1349 3479 |
+----------------+----------------+----------------+

A={R3C2,R3C4,R3C7}
we cant have R8C7=4 and R9C4=1 and so R8C4<>2
and we get



+----------------+----------------+----------------+
| 579  5789 12   | 3    4    12   | 589  59   6    |
| 459  6    249  | 7    8    29   | 1    3459 3459 |
| 34   89   1349 | 19   6    5    | 489  7    2    |
+----------------+----------------+----------------+
| 79   4    8    | 5    2    79   | 3    6    1    |
| 6    1    5    | 89   3    489  | 7    2    49   |
| 2    3    79   | 6    1    479  | 459  8    459  |
+----------------+----------------+----------------+
| 1    2    39   | 4    7    38   | 6    359  3589 |
| 3457 57   6    | 18   9    138  | 2   *34   378  |
| 8    79   3479 | 2    5    6    |*49   1    3479 |
+----------------+----------------+----------------+
We have R9C7=9 or R8C8=3
but R9C7=9 => R7C3=9
and R8C8=3 => R7C6=3 => R7C3=9 and that solve the puzzle.

[rubylips]

I'd like to couch the excellent observations from bennys in my own vocabulary, mainly to assist my own understanding.

First, introduce the term Disjoint Subset Link to describe the inference that follows from the situation where a total of n+1 values appear within n cells from a single sector in such a way that two of those values occur in one cell only. Clearly, if one of the two cells doesn't contain its candidate, the other must or we'd be left with n-1 values to fill n cells.

E.g., in the first grid, we have four values 1, 4, 8 and 9 in three cells r3c2, r3c4 and r7c4. The values 1 and 4 each occur in only one of those three cells, so r3c4 must contain 1 if r3c7 doesn't contain 4 and vice-versa.

It's possible to include this inference as a link within a chain. The notation r3c4-1-{r3c2}-4-r3c7 names the cells in the disjoint subset and makes it straightforward to read the logical inference. The critical chain is then:
r8c4-2-r8c7~4~r3c7-4-{r3c2}-1-r3c4~1~r9c4-2-r8c4
which gives us r8c4=2 => r8c4<>2.

The second grid uses an extended link, a concept that I've used (but not documented) for a while. I write the link e.g. r7c3=9=r9c7. The action of the cells r9c2 and r9c3 means that r9c7 contains a 9 if and only if r7c3 contains a 9. The critical chain here is:
r7c3~3~r7c6-3-r8c6-3-r8c8~4~r9c7=9=r7c3
so r7c3=3 => r7c3=9.

As a general comment, I prefer the short, 'clever' chains used by bennys to the sometimes lengthy chains my solver sometimes spits out at the moment. Accordingly, I'll update my solver so that it looks at chains in the following order:
i. Single-Valued chains with strong and weak links, in order to cover X-Wing, Swordfish, Turbot Fish etc.
ii. Many-valued chains with strong, weak, extended and (when implemented) disjoint subset links. (Previously, the solver had sought chains built only from strong, then from strong & weak links and only after that introduced extended links).
iii. Many-valued chains with Tabling.

[r.e.s.]

iii. Many-valued chains with Tabling.

Could you explain briefly what "Tabling" means in this context? (Is it related to MadOverlord's use of similar terminology?)

[Guest]

Code: Select all

[  579][ 5789][ 1279][    3][    4][  129][  589][   59][    6]
[ 3459][    6][ 2349][    7][    8][   29][    1][ 3459][ 3459]
[  349][   89][ 1349][   19][    6][    5][  489][    7][    2]
[   79][    4][    8][    5][    2][   79][    3][    6][    1]
[    6][    1][    5][   89][    3][  489][    7][    2][   49]
[    2][    3][   79][    6][    1][  479][  459][    8][  459]
[    1][    2][   39][    4][    7][   38][    6][  359][ 3589]
[ 3457][   57][    6][  128][    9][ 1238][ 2458][ 1345][34578]
[    8][   79][ 3479][   12][    5][    6][  249][ 1349][ 3479]


[Carcul]

bennys,

Thanks for your reply. I find your solution very intelligent and simple. I guess I have very much to learn.

Regards, Carcul

[ronk]

To parrot rubylips, I'd like to couch the excellent observations from bennys in my own learner's vocabulary. Copying bennys' illustrations of candidates, I shall do so without assigning terms and using only two symbols common in algebra: '=' for equals and '<>' for 'not equals'.

The first sticking point is ...

Code: Select all

+----------------+----------------+----------------+
| 579  5789 12   | 3    4    12   | 589  59   6    |
| 459  6    249  | 7    8    29   | 1    3459 3459 |
| 34  *89   1349 |*19   6    5    |*489  7    2    |
+----------------+----------------+----------------+
| 79   4    8    | 5    2    79   | 3    6    1    |
| 6    1    5    | 89   3    489  | 7    2    49   |
| 2    3    79   | 6    1    479  | 459  8    459  |
+----------------+----------------+----------------+
| 1    2    39   | 4    7    38   | 6    359  3589 |
| 3457 57   6    | 128  9    138  | 24   134  3478 |
| 8    79   3479 | 12   5    6    | 249  1349 3479 |
+----------------+----------------+----------------+


A set of three cells in row 3 (r3c2, r3c4, r3c7) has the four candidates 1489 (89, 19, 489). There are four possible combinations of three candidates from this set of four: 148, 149, 189, and 489. Note that each possibility includes the 4 or the 1 or both.

The only possible cell in the set for the 4 is r3c7. If r3c7=4, then r8c7=2.
The only possible cell in the set for the 1 is r3c4. If r3c4=1, then r9c4=2, r8c4<>2, and r8c7=2.
In either case, r8c7=2.

After pinning r8c7 to 2 and making additional steps, the next sticking point is ...

Code: Select all

+----------------+----------------+----------------+
| 579  5789 12   | 3    4    12   | 589  59   6    |
| 459  6    249  | 7    8    29   | 1    3459 3459 |
| 34   89   1349 | 19   6    5    | 489  7    2    |
+----------------+----------------+----------------+
| 79   4    8    | 5    2    79   | 3    6    1    |
| 6    1    5    | 89   3    489  | 7    2    49   |
| 2    3    79   | 6    1    479  | 459  8    459  |
+----------------+----------------+----------------+
| 1    2    39   | 4    7    38   | 6    359  3589 |
| 3457 57   6    | 18   9    138  | 2   *34   378  |
| 8    79   3479 | 2    5    6    |*49   1    3479 |
+----------------+----------------+----------------+

A set of two cells in box 9 (r8c8,r9c7) has the three candidates 349 (34,49). There are three possible combinations of two candidates from this set of three: 34, 39, and 49. Note that each possibility includes the 9 or the 3 or both.

The only possible cell in the set for the 9 is r9c7. If r9c7=9, then r9c2=7.
The only possible cell in the set for the 3 is r8c8. If r8c8=3, then r8c6<>3, r7c6=3, r7c3=9, r9c2=7.
In either case, r9c2=7.

Now that I understand the technique ... a very clever technique indeed ... I'll try to understand the syntax of equations presented by others. IOW I've got to walk before I can run.

[rubylips]

Could you explain briefly what "Tabling" means in this context? (Is it related to MadOverlord's use of similar terminology?)

Yes, I've borrowed the term from him.

[rubylips]

I've now implemented the Disjoint Subset Link, as described earlier in this thread, but it's still not as good as bennys!

Here's the first part of the log, which starts from the candidate grid given by MikeF:

Code: Select all

1. Consider the cell r9c7.
When it contains the value 9, the values 3, 4 and 7 in Row 9 must occupy the cells r9c2, r9c3 and r9c9 in some order.
When it contains the value 2, the value 4 in Box 9 must occupy the cell r8c7.
Whichever value it contains, the cell r9c8 cannot contain the value 4.
- The move r9c8:=4 has been eliminated.
Consider the chain r2c3~4~r2c8-4-r8c8~4~r8c1-4-r9c3.
When the cell r2c3 contains the value 4, so does the cell r9c3 - a contradiction.
Therefore, the cell r2c3 cannot contain the value 4.
- The move r2c3:=4 has been eliminated.
The values 3, 4 and 5 occupy the cells r2c1, r2c8 and r2c9 in some order.
- The moves r2c1:=9, r2c8:=9 and r2c9:=9 have been eliminated.
Consider the chain r2c6-9-r2c3~9~r6c3-9-r4c1-9-r4c6.
When the cell r4c6 contains the value 9, so does the cell r2c6 - a contradiction.
Therefore, the cell r4c6 cannot contain the value 9.
- The move r4c6:=9 has been eliminated.
The value 7 is the only candidate for the cell r4c6.
2. The value 9 is the only candidate for the cell r4c1.
3. The value 7 is the only candidate for the cell r6c3.


Here's the candidate grid at this stage, which is slightly different to that given by bennys:

Code: Select all

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


and the remainder of the log:

Code: Select all

Consider the chain r2c3-9-r2c6+<2|3>+r7c6+<8|9>+r7c3.
The cell r7c3 must contain the value 9 if the cell r2c3 doesn't.
Therefore, these two cells are the only candidates for the value 9 in Column 3.
- The moves r3c3:=9 and r9c3:=9 have been eliminated.
Consider the chain r7c3+<3|2>+r2c3-9-r2c6+<2|3>+r7c6.
The cell r7c6 must contain the value 3 if the cell r7c3 doesn't.
Therefore, these two cells are the only candidates for the value 3 in Row 7.
- The moves r7c8:=3 and r7c9:=3 have been eliminated.
The values 1, 3 and 4 occupy the cells r2c8, r8c8 and r9c8 in some order.
- The moves r2c8:=5 and r9c8:=9 have been eliminated.
Consider the chain r1c2~9~r1c8-9-r7c8~9~r7c3-9-r2c3.
When the cell r1c2 contains the value 9, so does the cell r2c3 - a contradiction.
Therefore, the cell r1c2 cannot contain the value 9.
- The move r1c2:=9 has been eliminated.
The value 9 in Box 3 must lie in Row 1.
- The move r3c7:=9 has been eliminated.
Consider the chain r5c6+<8|1>+r1c6-1-r1c3+<1|3>+r7c3+<9|8>+r7c6.
The cell r7c6 must contain the value 8 if the cell r5c6 doesn't.
Therefore, these two cells are the only candidates for the value 8 in Column 6.
- The move r8c6:=8 has been eliminated.
Consider the chain r9c2+<7|8>+r3c2+<9|4>+r2c1=4=r3c7+<8|9>+r9c7.
When the cell r9c2 contains the value 9, so does the cell r9c7 - a contradiction.
Therefore, the cell r9c2 cannot contain the value 9.
- The move r9c2:=9 has been eliminated.
The value 7 is the only candidate for the cell r9c2.


The notation r2c6+<2|3>+r7c6 (which appears in the first chain) means that when r2c6 doesn't contain a 2, r7c6 contains a 3. (Similarly, when r7c6 doesn't contain a 3, r2c6 contains a 2). The justification is that the cells {r2c6,r5c6,r6c6,r7c6} contain the values {2,3,4,8,9}, with 2 and 3 in just one cell each.

The Disjoint Subset link lends itself to X-Wing-like conclusions, i.e. it will often identify the two possible locations of a value within a sector, which allows the value to be eliminated from other locations. It does this because the link requires as its initial postulate that a cell DOESN'T contain a given value. This type of logic is often productive because it allows multiple candidates to be eliminated at a single stroke.

As you see, the link is a useful addition to the armoury but it's no replacement for careful judgement.