The third toughest puzzle

Advanced methods and approaches for solving Sudoku puzzles

The third toughest puzzle

Postby Jeff » Wed Dec 14, 2005 9:01 pm

This is the third toughest puzzle known in this forum and I have just learnt that at least two logical solutions have been found by using different techniques. It is the intension of this thread to collectively capture all logical solutions for this grid. All contributions are welcome.

Original grid:

Code: Select all
 *-----------*
 |..2|.9.|1.7|
 |.38|6..|...|
 |4..|...|...|
 |---+---+---|
 |...|..5|...|
 |..9|.1.|3..|
 |...|4..|...|
 |---+---+---|
 |...|...|..4|
 |...|..7|92.|
 |8.6|.3.|7..|
 *-----------*


Listed below is the candidate grid subsequent to application of some basic rules. All solutions should start from this point.

Code: Select all
 *-----------------------------------------------------------------------------*
 | 56      56      2       | 38      9       348     | 1       348     7       |
 | 179     3       8       | 6       2457    12      | 245     59      259     |
 | 4       179     17      | 123578  2578    1238    | 2568    35689   235689  |
 |-------------------------+-------------------------+-------------------------|
 | 12367   12678   1347    | 39      2678    5       | 2468    16789   12689   |
 | 2567    245678  9       | 278     1       268     | 3       45678   2568    |
 | 123567  125678  1357    | 4       2678    39      | 2568    156789  125689  |
 |-------------------------+-------------------------+-------------------------|
 | 123579  12579   1357    | 12589   2568    12689   | 68      368     4       |
 | 135     15      1345    | 158     4568    7       | 9       2       368     |
 | 8       249     6       | 29      3       249     | 7       15      15      |
 *-----------------------------------------------------------------------------*

Thanks
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Wed Dec 14, 2005 9:27 pm

Hi Jeff.

I have concluded that my solution needs "only" 23 chains. Here is my solution.

Part 1

Starting from the grid above we have:

Chain 1 (Turbot Fish): [r5c9]-6-[r5c6]=6=[r7c6]-6-[r8c5]=6=[r8c9]-6-[r5c9] => r5c9<>6.

Chain 2 (Turbot Fish): [r5c1]-7-[r5c4]=7=[r3c4]-7-[r2c5]=7=[r2c1]-7-[r5c1] => r5c1<>7.

Chain 3: [r4c7]=4=[r2c7]-4-[r1c8]=4=[r1c6]-4-[r9c6]=4=[r8c5]=6=[r8c9]-6-[r7c7]-8-[r4c7] => r4c7<>8

Chain 4: [r4c3]=4=[r8c3]-4-[r8c5]=4=[r2c5]=7=[r2c1]-7-[r3c3]-1-[r4c3] => r4c3<>1.

Chain 5: [r9c2]=4=[r9c6]-4-[r8c5]=4=[r2c5]=7=[r2c1]=9=[r3c2]-9-[r9c2] => r9c2<>9.

Chain 6: [r1c8]=4=[r1c6]-4-[r9c6]=4=[r8c5]=6=[r8c9]=3=[r7c8]-3-[r1c8] => r1c8<>3.

Chain 7: [r7c1]=9=[r7c2]-9-[r3c2]=9=[r2c1]=7=[r2c5]=4=[r8c5]=6=[r8c9]=3=[r7c8]-3-[r7c1] => r7c1<>3.

Chain 8: [r3c9]=3=[r3c8]-3-[r7c8]=3=[r8c9]=6=[r8c5]=4=[r2c5]=7=[r2c1]=9=[r3c2]-9-[r3c9] => r3c9<>9.

Chain 9: [r4c3]=4=[r8c3]-4-[r9c2]-2-[r9c4]-9-[r4c4]-3-[r4c3] => r4c3<>3.

Chain 10: [r4c1]=3=[r4c4]-3-[r1c4]=3=[r1c6]=4=[r2c5]=7=[r2c1]-7-[r4c1] => r4c1<>7,

and we get:

Code: Select all
 *-----------------------------------------------------------------------------*
 | 56      56      2       | 38      9       34      | 1       48      7       |
 | 179     3       8       | 6       2457    12      | 245     59      259     |
 | 4       179     17      | 12578   2578    128     | 2568    35689   23568   |
 |-------------------------+-------------------------+-------------------------|
 | 1236    12678   47      | 39      2678    5       | 246     16789   12689   |
 | 256     245678  9       | 278     1       268     | 3       45678   258     |
 | 123567  125678  1357    | 4       2678    39      | 2568    156789  125689  |
 |-------------------------+-------------------------+-------------------------|
 | 12579   12579   1357    | 1258     2568    1268   | 68      368     4       |
 | 135     15      1345    | 158     4568    7       | 9       2       368     |
 | 8       24      6       | 29      3       49      | 7       15      15      |
 *-----------------------------------------------------------------------------*


Part 2

Chain 11: [r3c4]-8-[r8c4]=8|4=[r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r3c4] => r3c4<>8.

The “=8|4=” is a disjoint subset link (due to the ALS r8c1, r8c2, r8c3, r8c4) as defined by Rubylips.

Chain 12: [r5c4]-8-[r8c4]=8|4=[r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r5c4] => r5c4<>8.

Chain 13: [r7c4]-8-[r8c4]=8|4=[r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r7c4] => r7c4<>8.

Although not necessary, the following deduction could also be made:

Chain A: [r7c5]-8-[r7c7]-6-[r7c6]=6=[r5c6]=8=[r4c5|r6c5]-8-[r7c5] => r7c5<>8.

Next, we have more chains:

Chain 14: [r5c2]=4=[r9c2]=2=[r9c4]-2-[r5c4]-7-[r5c2] => r5c2<>7.

Chain 15: [r3c3]-7-[r4c3]-4-[r8c3|r8c2|r8c1|r7c3]-7-[r3c3] => r3c3<>7.

Chain 16: [r6c3]-7-[r4c3]-4-[r8c3|r8c2|r8c1|r7c3]-7-[r6c3] => r6c3<>7.

Chain 17: [r3c4]-2-[r9c4]=2=[r9c2]=4=[r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r3c6]-2-[r3c4] => r3c4<>2.

Chain 18: [r2c5]=4=[r2c7]-4-[r4c7]=4=[r5c8]=7=[r5c4]-7-[r3c4]-5-[r2c5] => r2c5<>5.

Chain 19: [r7c1]=9=[r7c2]-9-[r3c2]=9=[r2c1]=7=[r2c5]=4=[r2c7]-4-[r4c7]=4=[r4c3]=7=[r7c3]-7-[r7c1] => r7c1<>7.

Although not necessary, we could also make the following two deductions:

Chain B: [r5c2]=4=[r9c2]-4-[r9c6]-9-[r6c6]-3-[r6c3]-5-[r5c2] => r5c2<>5.
Chain C: [r4c5]-7-[r5c4]=7=[r5c8]=4=[r4c7]-4-[r4c3]-7-[r4c5] => r4c5<>7.

Two more nice loops:

Chain 20: [r8c3]=4=[r9c2]=2=[r9c4]=9=[r4c4]-9-[r6c6]-3-[r6c3]-5-[r8c3] => r8c3<>5.

Chain 21: [r2c1]-9-[r7c1]=9=[r7c2]=7=[r7c3]=5=[r6c3]-5-[r6c7]=5=[r2c7]-5-[r2c8]-9-[r2c1] => r2c1<>9.

Now the grid must be updated. After that:

Chain 22: [r9c2]=2=[r7c2]=7=[r7c3]=5=[r6c3]-5-[r6c7]=5=[r2c7]=4=[r2c5]-4-[r8c5]=4=[r8c3]-4-[r9c2] => r9c2<>4.

The grid needs to be updated again. Then:

Chain 23: [r8c9]-8-[r8c5]-6-[r4c5]-8-[r4c2]-6-[r5c1]-5-[r5c9]-8-[r8c9] => r8c9<>8

and that solve the puzzle.

Regards, Carcul.
Last edited by Carcul on Thu Dec 15, 2005 3:42 am, edited 1 time in total.
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Wed Dec 14, 2005 10:07 pm

Carcul wrote:Chain 11: [r3c4]-8-[r8c4]=8|4=[r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r3c4] => r3c4<>8.

The “=8|4=” is an extended disjoint subset link (due to the ALS r8c1, r8c2, r8c3, r8c4) as defined by Rubylips.

Firstly: Congratulations on achieving a logical solution to the puzzle.

Secondly:To clarify, the "=8|4=" is an example of rubylips' Conditional Disjoint Subset, nee bennys' Almost Locked Set. There is nothing 'extended' about it. There are N cells and N+1 candidates, with two candidates each occuring once only in two different cells. When one of these two candidates is eliminated, the *almost* disjoint set in then disjoint (locked, naked) ... with N cells and N candidates ... so the location of the other of the two candidates is known.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby rubylips » Wed Dec 14, 2005 11:56 pm

It's possible to eliminate two candidates from the grid with fairly straightforward chains:

Code: Select all
Consider the chain r5c9~6~r5c6-6-r7c6~6~r8c5-6-r8c9.
When the cell r5c9 contains the value 6, so does the cell r8c9 - a contradiction.
Therefore, the cell r5c9 cannot contain the value 6.
- The move r5c9:=6 has been eliminated.
Consider the chain r5c1~7~r2c1-7-r2c5~7~r3c4-7-r5c4.
When the cell r5c1 contains the value 7, so does the cell r5c4 - a contradiction.
Therefore, the cell r5c1 cannot contain the value 7.
- The move r5c1:=7 has been eliminated.

which leaves the following candidate grid:

Code: Select all
      56      56     2 |      38     9    348 |     1     348       7
     179       3     8 |       6  2457     12 |   245      59     259
       4     179    17 |  123578  2578   1238 |  2568   35689  235689
-----------------------+----------------------+----------------------
   12367   12678  1347 |      39  2678      5 |  2468   16789   12689
     256  245678     9 |     278     1    268 |     3   45678     258
  123567  125678  1357 |       4  2678     39 |  2568  156789  125689
-----------------------+----------------------+----------------------
  123579   12579  1357 |   12589  2568  12689 |    68     368       4
     135      15  1345 |     158  4568      7 |     9       2     368
       8     249     6 |      29     3    249 |     7      15      15

From here, I use 16 chains to solve the puzzle, plus three much more straightforward chains (two of which appear above) and a single Conditional Disjoint Subsets elimination. I'd like to use the solution to illustrate some of my terminology, particularly the difference between what I refer to as disjoint subset and extended disjoint subset links.

The first chain, which features a disjoint subset link, eliminates a candidate immediately.

Code: Select all
Consider the chain r3c3~7~r2c1-7-r2c5-4-r8c5-4-r8c3-<4|7>-r7c3.
When the cell r3c3 contains the value 7, so does the cell r7c3 - a contradiction.
Therefore, the cell r3c3 cannot contain the value 7.
- The move r3c3:=7 has been eliminated.
The value 1 is the only candidate for the cell r3c3.

The link r8c3-<4|7>-r7c3 is based upon the Almost Locked Set {r7c3,r8c1,r8c2,r8c3}, which contains 5 values, 4 and 7 just once each. The point is that when r8c3 doesn't contain a 4, r7c3 contains a 7 and when r7c3 doesn't contain a 7, r8c3 contains a 4.

The solution proceeds as follows:

Code: Select all
The cell r2c6 is the only candidate for the value 1 in Row 2.

      56      56    2 |     38     9   348 |     1     348       7
      79       3    8 |      6  2457     1 |   245      59     259
       4      79    1 |  23578  2578   238 |  2568   35689  235689
----------------------+--------------------+----------------------
   12367   12678  347 |     39  2678     5 |  2468   16789   12689
     256  245678    9 |    278     1   268 |     3   45678     258
  123567  125678  357 |      4  2678    39 |  2568  156789  125689
----------------------+--------------------+----------------------
  123579   12579  357 |  12589  2568  2689 |    68     368       4
     135      15  345 |    158  4568     7 |     9       2     368
       8     249    6 |     29     3   249 |     7      15      15

Consider the chain r1c8=<3|4>=r1c6-4-r9c6-4-r8c5-6-r8c9=<6|3>=r7c8.
When the cell r1c8 contains the value 3, so does the cell r7c8 - a contradiction.
Therefore, the cell r1c8 cannot contain the value 3.
- The move r1c8:=3 has been eliminated.
The value 3 in Box 2 must lie in Row 1.
- The moves r3c4:=3 and r3c6:=3 have been eliminated.

The links r1c8=<3|4>=r1c6 and r8c9=<6|3>=r7c8 are examples of extended disjoint subset links, which are related to but distinct from disjoint subset links. Since they are somewhat degenerate examples, I will illustrate a better example later in the solution. The link states that when r1c8 contains a 3, r1c6 contains a 4 and when r1c6 doesn't contain a 4, r1c8 doesn't contain a 3. The construction comprises an Almost Locked Set, here {r1c4,r1c6} in Box 2, which has a value that occurs once, here the 4, and a value that occurs many times but entirely within an orthogonal sector. Here the orthogonal sector is Row 1 and the value is 3, though it could equally be 8.

The next section uses a Conditional Disjoint Subsets construction, which is a term I used on the solver before the Almost Locked Sets xz-rule occurred in the public domain. Essentially, it's a very straightforward locked sets elimation that it's possible to perform outside of a chain framework. I'll probably remove from my solver as it has been superseded by the new link types.

Code: Select all
      56      56    2 |     38     9   348 |     1      48       7
      79       3    8 |      6  2457     1 |   245      59     259
       4      79    1 |   2578  2578    28 |  2568   35689  235689
----------------------+--------------------+----------------------
   12367   12678  347 |     39  2678     5 |  2468   16789   12689
     256  245678    9 |    278     1   268 |     3   45678     258
  123567  125678  357 |      4  2678    39 |  2568  156789  125689
----------------------+--------------------+----------------------
  123579   12579  357 |  12589  2568  2689 |    68     368       4
     135      15  345 |    158  4568     7 |     9       2     368
       8     249    6 |     29     3   249 |     7      15      15

Consider the cell r1c4.
When it contains the value 3, the values 2 and 9 in Column 4 must occupy the cells r4c4 and r9c4 in some order.
When it contains the value 8, the value 2 in Box 2 must occupy the cell r3c6.
Whichever value it contains, the cells r2c4 and r3c4 cannot contain the value 2.
- The move r3c4:=2 has been eliminated.
Consider the chain r9c6~2~r9c4=<9|4>=r9c6.
When the cell r9c6 contains the value 2, it likewise contains the value 4 - a contradiction.
Therefore, the cell r9c6 cannot contain the value 2.
- The move r9c6:=2 has been eliminated.
Consider the chain r7c6~2~r3c6=<2|8>=r1c4-<8|2>-r9c4.
When the cell r7c6 contains the value 2, so does the cell r9c4 - a contradiction.
Therefore, the cell r7c6 cannot contain the value 2.
- The move r7c6:=2 has been eliminated.

      56      56    2 |     38     9   348 |     1      48       7
      79       3    8 |      6  2457     1 |   245      59     259
       4      79    1 |    578  2578    28 |  2568   35689  235689
----------------------+--------------------+----------------------
   12367   12678  347 |     39  2678     5 |  2468   16789   12689
     256  245678    9 |    278     1   268 |     3   45678     258
  123567  125678  357 |      4  2678    39 |  2568  156789  125689
----------------------+--------------------+----------------------
  123579   12579  357 |  12589  2568   689 |    68     368       4
     135      15  345 |    158  4568     7 |     9       2     368
       8     249    6 |     29     3    49 |     7      15      15

The next chain features a superior example of an extended disjoint subsets link. The Almost Locked Set {r1c8,r2c7,r2c8,r2c9} in Box 3 contains the values {2,4,5,8,9} such that the 8 occurs just once and all the 9s occur in Row 2. Therefore, when r1c8 doesn't contain an 8, r2c1 can't contain a 9. (Furthermore, though of no significance here, when r2c1 contains a 9, r1c8 must contain an 8).

Code: Select all
Consider the chain r1c8=<8|9>=r2c1-9-r7c1~9~r7c6-<9|3>-r7c8.
When the cell r7c8 contains the value 8, some other value must occupy the cell r1c8, which means that the value 3 must occupy the cell r7c8 - a contradiction.
Therefore, the cell r7c8 cannot contain the value 8.
- The move r7c8:=8 has been eliminated.
Consider the chain r4c4-<9|8>-r1c4=<8|9>=r3c2=9=r7c1~9~r7c4.
When the cell r7c4 contains the value 9, so does the cell r4c4 - a contradiction.
Therefore, the cell r7c4 cannot contain the value 9.
- The move r7c4:=9 has been eliminated.
Consider the chain r7c1-9-r2c1-7-r2c5-4-r8c5-6-r8c9=<6|3>=r7c8.
When the cell r7c1 contains the value 3, so does the cell r7c8 - a contradiction.
Therefore, the cell r7c1 cannot contain the value 3.
- The move r7c1:=3 has been eliminated.
Consider the chain r7c1=<1|4>=r8c3-4-r8c5-4-r2c5-7-r2c1-9-r7c1.
When the cell r7c1 contains the value 1, it likewise contains the value 9 - a contradiction.
Therefore, the cell r7c1 cannot contain the value 1.
- The move r7c1:=1 has been eliminated.
Consider the chain r3c4=<8|4>=r1c6-4-r9c6-4-r8c5-4-r8c3-<4|8>-r8c4.
When the cell r3c4 contains the value 8, so does the cell r8c4 - a contradiction.
Therefore, the cell r3c4 cannot contain the value 8.
- The move r3c4:=8 has been eliminated.
Consider the chain r7c8-<3|9>-r7c6~9~r7c1-9-r2c1-7-r2c5-4-r8c5-6-r8c9.
When the cell r7c8 contains the value 6, so does the cell r8c9 - a contradiction.
Therefore, the cell r7c8 cannot contain the value 6.
When the cell r8c9 contains the value 3, some other value must occupy the cell r7c8, which means that the value 6 must occupy the cell r8c9 - a contradiction.
Therefore, the cell r8c9 cannot contain the value 3.
- The move r7c8:=6 has been eliminated.
The value 3 is the only candidate for the cell r7c8.

After a single trivial move, more chains have to be found.

Code: Select all
The cell r3c9 is the only candidate for the value 3 in Row 3.

      56      56    2 |     38     9   348 |     1      48       7
      79       3    8 |      6  2457     1 |   245      59     259
       4      79    1 |    578  2578    28 |  2568    5689       3
----------------------+--------------------+----------------------
   12367   12678  347 |     39  2678     5 |  2468   16789   12689
     256  245678    9 |    278     1   268 |     3   45678     258
  123567  125678  357 |      4  2678    39 |  2568  156789  125689
----------------------+--------------------+----------------------
   12579   12579   57 |  12589  2568  2689 |    68       3       4
     135      15  345 |    158  4568     7 |     9       2      68
       8     249    6 |     29     3   249 |     7      15      15

Consider the chain r6c1~3~r6c6-3-r4c4-<9|8>-r1c4~8~r8c4-<8|3>-r8c1.
When the cell r6c1 contains the value 3, so does the cell r8c1 - a contradiction.
Therefore, the cell r6c1 cannot contain the value 3.
- The move r6c1:=3 has been eliminated.
Consider the chain r7c1-9-r2c1=<9|8>=r1c8=<8|4>=r1c6-4-r9c6=<4|9>=r7c6.
When the cell r7c6 contains the value 9, so does the cell r7c1 - a contradiction.
Therefore, the cell r7c6 cannot contain the value 9.
- The move r7c6:=9 has been eliminated.
The value 9 in Box 7 must lie in Row 7.
- The move r9c2:=9 has been eliminated.
The values 1, 2, 5, 7 and 9 occupy the cells r7c1, r7c2, r7c3, r7c4 and r7c5 in some order.
- The moves r7c4:=8, r7c5:=6 and r7c5:=8 have been eliminated.
The values 3, 4 and 9 occupy the cells r1c6, r6c6 and r9c6 in some order.
- The move r1c6:=8 has been eliminated.
Consider the chain r1c4-<8|2>-r9c4-<9|8>-r8c4.
The cell r8c4 must contain the value 8 if the cell r1c4 doesn't.
Therefore, these two cells are the only candidates for the value 8 in Column 4.
- The move r5c4:=8 has been eliminated.
Consider the chain r6c3=3=r4c4-<3|2>-r9c4=<2|7>=r7c3.
When the cell r6c3 contains the value 7, so does the cell r7c3 - a contradiction.
Therefore, the cell r6c3 cannot contain the value 7.
- The move r6c3:=7 has been eliminated.
Consider the chain r2c5=<5|8>=r1c8-<4|3>-r1c4-<8|5>-r3c4.
When the cell r2c5 contains the value 5, so does the cell r3c4 - a contradiction.
Therefore, the cell r2c5 cannot contain the value 5.
- The move r2c5:=5 has been eliminated.
The value 5 in Box 3 must lie in Row 2.
- The moves r3c7:=5 and r3c8:=5 have been eliminated.
Consider the chain r1c8-<4|3>-r1c4-<8|9>-r4c4=3=r6c3~5~r6c7-5-r2c7.
When the cell r2c7 contains the value 4, some other value must occupy the cell r1c8, which means that the value 5 must occupy the cell r2c7 - a contradiction.
Therefore, the cell r2c7 cannot contain the value 4.
- The move r2c7:=4 has been eliminated.
The cell r2c5 is the only candidate for the value 4 in Row 2.

The puzzle is now trivial for many moves, though one slightly tricky position is reached later on:

Code: Select all
  56   56  2 |  8   9   3 |   1   4      7
   7    3  8 |  6   4   1 |  25  59    259
   4    9  1 |  7   5   2 |  68  68      3
-------------+------------+---------------
  12   68  7 |  3  68   5 |   4  19    129
  56    4  9 |  2   1  68 |   3   7     58
  12   58  3 |  4   7   9 |  25  68  12568
-------------+------------+---------------
   9    7  5 |  1   2  68 |  68   3      4
   3    1  4 |  5  68   7 |   9   2     68
   8    2  6 |  9   3   4 |   7  15     15

Consider the chain r5c9-8-r5c6-8-r7c6-8-r7c7-8-r8c9.
When the cell r5c9 contains the value 8, so does the cell r8c9 - a contradiction.
Therefore, the cell r5c9 cannot contain the value 8.
When the cell r8c9 contains the value 8, so does the cell r5c9 - a contradiction.
Therefore, the cell r8c9 cannot contain the value 8.
- The moves r5c9:=8 and r8c9:=8 have been eliminated.
The value 5 is the only candidate for the cell r5c9.

After this, the puzzle really is trivial.

Carcul,
Did you find all your chains by hand?
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby rubylips » Thu Dec 15, 2005 12:04 am

Carcul wrote:
Code: Select all
 *-----------------------------------------------------------------------------*
 | 56      56      2       | 38      9       34      | 1       48      7       |
 | 179     3       8       | 6       2457    12      | 245     59      259     |
 | 4       179     17      | 12578   2578    128     | 2568    35689   23568   |
 |-------------------------+-------------------------+-------------------------|
 | 1236    12678   47      | 39      2678    5       | 246     16789   12689   |
 | 256     245678  9       | 278     1       268     | 3       45678   258     |
 | 123567  125678  1357    | 4       2678    39      | 2568    156789  125689  |
 |-------------------------+-------------------------+-------------------------|
 | 12579   12579   1357    | 1258     2568    1268   | 68      368     4       |
 | 135     15      1345    | 158     4568    7       | 9       2       368     |
 | 8       24      6       | 29      3       49      | 7       15      15      |
 *-----------------------------------------------------------------------------*


Part 2

Chain 11: [r3c4]-8-[r8c4]=8|4=[r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r3c4] => r3c4<>8.

The “=8|4=” is an extended disjoint subset link (due to the ALS r8c1, r8c2, r8c3, r8c4) as defined by Rubylips.


Carcul,
Actually ronk is right here, the link in question is a plain disjoint subset link because the values 4 and 8 each occur once in the set. See the previous post for an example of what I mean by an extended disjoint subsets link.

Thanks.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Ruud » Thu Dec 15, 2005 12:22 am

I'm not sure how to classify this puzzle. It's certainly not in my top 3.

It requires (besides the obvious singles):
5 Line-Box interactions
5 Naked pairs
4 Hidden pairs
1 remote linked pair
1 Swordfish
2 Coloring chains
3 Forward implication chains (heavy ammo)

The puzzle I posted here is definitely tougher.


Part 1, upto the indicated candidate list:
Code: Select all
Box 1 found a Naked Pair with Digits {5,6}
Row 3 only has candidates for Digit 6 in Box 3
Box 1 only has candidates for Digit 5 in Row 1
Box 5 found a Hidden Pair with Digits {3,9}
Box 9 found a Naked Pair with Digits {1,5}
Box 9 only has candidates for Digit 1 in Row 9
Box 9 only has candidates for Digit 5 in Row 9
Swordfish found in Rows {1,5,9}, Columns {2,6,8} for Digit 4

Then 2 coloring eliminations, also pretty basic.
Code: Select all
Coloring value 6 found a connected pair. R5C9 eliminated.
Coloring value 7 found a connected pair. R5C1 eliminated.

At this point, 2 chains are required to make progress:
Code: Select all
Placing Digit 8 in R1C6 forces 2 different cells to Digit 9 in Column 2
Placing Digit 1 in R2C1 forces 2 different Digits in R7C1

That last chain forces a cell, but no follow up yet.
Code: Select all
Row 2 Digit 1 must be placed in R2C6

Then the last chain. This is the second 8 eliminated from row 1.
Code: Select all
Placing Digit 8 in R1C8 forces 2 different cells to Digit 5 in Row 7

After that, the puzzle can be solved with singles, a few naked/hidden pairs and 1 remote locked pair.
This is the remainder of the solver log.
Code: Select all
Row 1 Digit 8 must be placed in R1C4
Column 6 found a Hidden Pair with Digits {6,8}
Row 7 found a Naked Pair with Digits {6,8}
R7C8 has Digit 3 as the only remaining candidate
Row 1 Digit 3 must be placed in R1C6
Box 3 Digit 3 must be placed in R3C9
R1C8 has Digit 4 as the only remaining candidate
Column 6 Digit 4 must be placed in R9C6
Box 2 Digit 4 must be placed in R2C5
Column 4 Digit 3 must be placed in R4C4
R3C6 has Digit 2 as the only remaining candidate
R6C6 has Digit 9 as the only remaining candidate
Column 7 Digit 4 must be placed in R4C7
Row 5 Digit 4 must be placed in R5C2
Box 7 Digit 4 must be placed in R8C3
Row 2 Digit 7 must be placed in R2C1
Column 3 Digit 3 must be placed in R6C3
Row 8 Digit 3 must be placed in R8C1
Column 3 Digit 5 must be placed in R7C3
Column 1 Digit 9 must be placed in R7C1
Box 1 Digit 9 must be placed in R3C2
Column 3 Digit 7 must be placed in R4C3
R3C3 has Digit 1 as the only remaining candidate
Row 7 Digit 7 must be placed in R7C2
Box 7 Digit 1 must be placed in R8C2
Row 7 Digit 1 must be placed in R7C4
R7C5 has Digit 2 as the only remaining candidate
Box 7 Digit 2 must be placed in R9C2
Column 4 Digit 9 must be placed in R9C4
R8C4 has Digit 5 as the only remaining candidate
Column 4 Digit 2 must be placed in R5C4
Box 2 Digit 5 must be placed in R3C5
R3C4 has Digit 7 as the only remaining candidate
Row 5 Digit 7 must be placed in R5C8
Box 5 Digit 7 must be placed in R6C5
Box 4 found a Hidden Pair with Digits {1,2}
Column 7 found a Naked Pair with Digits {6,8}
Row 4 found a Naked Pair with Digits {6,8}
Box 6 only has candidates for Digit 6 in Row 6
Column 8 found a Hidden Pair with Digits {6,8}
R5C6 and R8C9 are a remote pair for Digits {6,8}

After that remote pair, it's singles only.

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Bob Hanson » Thu Dec 15, 2005 1:22 am

Solving this configuration using Sudoku Assistant does
require almost-locked sets. I get:

Done! (46 steps) AaMw

562 893 147
738 641 592
491 752 683

287 365 419
649 218 375
153 479 268

975 126 834
314 587 926
826 934 751

The following is not meant to be "a solution". Rather, it itemizes
all of "basic" logical conclusions that can be drawn from this
PARTICULAR configuration:

Strong Chains: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
60 cells left to solve; 21 clues; 500 tidbits of information
103 almost-locked sets (Y)
(ooh!)

r3c4 ISN'T 2: weakly linked to two almost-locked sets already weakly linked by 8: r2c6 r3c6 and r1c4 r4c4 r9c4
r7c3 ISN'T 1: weakly linked to two almost-locked sets already weakly linked by 4: r8c1 r8c2 r8c3 and r3c3 r4c3
r8c3 ISN'T 1: weakly linked to two almost-locked sets already weakly linked by 7: r3c3 and r7c3 r8c1 r8c2
r7c1 ISN'T 1: weak link to almost-locked sets r4c3 and r7c3 r8c1 r8c2 r8c3 mutually doubly-linked by 4,7
r7c2 ISN'T 1: weak link to almost-locked sets r4c3 and r7c3 r8c1 r8c2 r8c3 mutually doubly-linked by 4,7
r7c1 ISN'T 5: weak link to almost-locked sets r4c3 and r7c3 r8c1 r8c2 r8c3 mutually doubly-linked by 4,7
r7c2 ISN'T 5: weak link to almost-locked sets r4c3 and r7c3 r8c1 r8c2 r8c3 mutually doubly-linked by 4,7
r7c1 ISN'T 1: weak link to almost-locked sets r7c3 r8c1 r8c2 r8c3 and r3c3 r4c3 mutually doubly-linked by 4,7
r7c2 ISN'T 1: weak link to almost-locked sets r7c3 r8c1 r8c2 r8c3 and r3c3 r4c3 mutually doubly-linked by 4,7
r7c1 ISN'T 5: weak link to almost-locked sets r7c3 r8c1 r8c2 r8c3 and r3c3 r4c3 mutually doubly-linked by 4,7
r7c2 ISN'T 5: weak link to almost-locked sets r7c3 r8c1 r8c2 r8c3 and r3c3 r4c3 mutually doubly-linked by 4,7
r6c3 ISN'T 1: weak link to almost-locked sets r7c3 r8c1 r8c2 r8c3 and r3c3 r4c3 mutually doubly-linked by 4,7

100 almost-locked sets (X)
(oooooooooh; amazingly, nothing here, though...)

Checking strong chains
14 strong chains

r3c4 ISN'T 2: r3c4#2 is incompatibly weakly linked to 2(b) involving nodes r1c4#3 chain 2(B) and r1c6#3 chain 2(b) via ALS r1c4 r2c6 r3c6
r3c4 ISN'T 2: r3c4#2 is incompatibly weakly linked to 2(b) involving nodes r1c4#3 chain 2(B) and r1c4#8 chain 2(b) via ALS r2c6 r3c6
r3c4 ISN'T 2: r3c4#2 is incompatibly weakly linked to 2(b) involving nodes r1c4#3 chain 2(B) and r2c5#4 chain 2(b) via ALS r1c4 r1c6 r2c6 r3c6
r7c6 ISN'T 2: r7c6#2 is incompatibly weakly linked to 2(B) involving nodes r1c4#8 chain 2(b) and r9c2#4 chain 2(B) via ALS r9c4 r9c6
r7c3 ISN'T 1: r7c3#1 is incompatibly weakly linked to 2(b) involving nodes r9c2#4 chain 2(B) and r8c3#4 chain 2(b) via ALS r3c3 r4c3
r7c6 ISN'T 2: r7c6#2 is incompatibly weakly linked to 2(B) involving nodes r1c4#8 chain 2(b) and r8c5#4 chain 2(B) via ALS r9c4 r9c6
r7c6 ISN'T 2: r7c6#2 is incompatibly weakly linked to 2(B) involving nodes r1c4#8 chain 2(b) and r9c4#2 chain 2(B) block 8

(note the chain/ALS combo here)

Checking for weak links
51 weak links
475 weak corners

(whew!!)

r7c1 ISN'T 5: weak corner eliminated by both 2(B) and 2(b)--3(C)
r7c1 ISN'T 5: weak corner eliminated by both 2(B) and 2(b)--5(e)
r3c9 ISN'T 2: weak corner eliminated by both 2(b) and 2(B)--7(G)
r7c3 ISN'T 1: weak corner eliminated by both 2(B) and 2(b)--8(h)
r3c9 ISN'T 2: weak corner eliminated by both 2(b) and 2(B)--13(M)
r7c1 ISN'T 5: weak corner eliminated by both 3(C) and 3(c)--2(B)
r7c1 ISN'T 5: weak corner eliminated by both 3(C) and 3(c)--6(f)
r7c1 ISN'T 1: weak corner eliminated by both 3(C) and 3(c)--12(l)
r7c1 ISN'T 5: weak corner eliminated by both 5(e) and 5(E)--2(B)
r7c1 ISN'T 5: weak corner eliminated by both 6(f) and 6(F)--3(C)
r3c9 ISN'T 2: weak corner eliminated by both 7(G) and 7(g)--2(b)
r7c3 ISN'T 1: weak corner eliminated by both 8(h) and 8(H)--2(B)
r7c1 ISN'T 1: weak corner eliminated by both 12(l) and 12(L)--3(C)
r3c9 ISN'T 2: weak corner eliminated by both 13(M) and 13(m)--2(b)

(Again, some duplicates here -- the idea is to show ALL possible
implications. These somehow involve ALS, but I don't know how from this)

Chain 1: r1c1#5(a) r1c1#6(A) r1c2#5(A) r1c2#6(a)
Chain 2: r1c4#3(B) r1c6#3(b) r1c6#4(B) r1c8#4(b) r1c4#8(b) r1c8#8(B) r2c5#4(b) r2c7#4(B) r5c2#4(b) r9c2#4(B) r4c3#4(B) r8c3#4(b) r4c1#3(B) r4c4#3(b) r4c3#7(b) r4c7#4(b) r4c4#9(B) r9c4#9(b) r6c6#3(B) r5c8#4(B) r8c5#4(B) r6c6#9(b) r9c6#4(b) r9c6#9(B) r9c2#2(b) r9c4#2(B)
Chain 3: r2c1#9(c) r7c1#9(C) r3c2#9(C) r7c2#9(c) r3c8#9(c)
Chain 5: r2c1#7(e) r2c5#7(E)
Chain 6: r2c8#5(f) r2c8#9(F)
Chain 7: r3c8#3(g) r3c9#3(G) r7c3#3(g) r7c8#3(G) r8c9#3(g)
Chain 8: r3c3#1(h) r3c3#7(H)
Chain 12: r8c2#1(l) r8c2#5(L)
Chain 13: r8c5#6(m) r8c9#6(M)
Chain 14: r9c8#1(n) r9c9#1(N) r9c8#5(N) r9c9#5(n)

(Chain 2 is the one that takes care of a lot of what Jeff suggested. Quite a monster.)
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby ronk » Thu Dec 15, 2005 2:47 am

rubylips wrote:
Code: Select all
      56      56    2 |     38     9   348 |     1     348       7
      79       3    8 |      6  2457     1 |   245      59     259
       4      79    1 |  23578  2578   238 |  2568   35689  235689
----------------------+--------------------+----------------------
   12367   12678  347 |     39  2678     5 |  2468   16789   12689
     256  245678    9 |    278     1   268 |     3   45678     258
  123567  125678  357 |      4  2678    39 |  2568  156789  125689
----------------------+--------------------+----------------------
  123579   12579  357 |  12589  2568  2689 |    68     368       4
     135      15  345 |    158  4568     7 |     9       2     368
       8     249    6 |     29     3   249 |     7      15      15

Consider the chain r1c8=<3|4>=r1c6-4-r9c6-4-r8c5-6-r8c9=<6|3>=r7c8.
[edit: ....]

The link r1c8=<3|4>=r1c6 [edit: ...] states that when r1c8 contains a 3, r1c6 contains a 4 and when r1c6 doesn't contain a 4, r1c8 doesn't contain a 3.

By just looking at the equation, how are we supposed to know it doesn't mean: if r1c8<>3 then r1c6<>6 ???
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Thu Dec 15, 2005 3:51 am

Sorry about the slightly off-topic, but I just noted a workable 5-candidate BUG cell in Rubylips final grid:

Code: Select all
  56   56  2 |  8   9   3 |   1   4      7
   7    3  8 |  6   4   1 |  25  59    29+5
   4    9  1 |  7   5   2 |  68  68      3
-------------+------------+---------------
  12   68  7 |  3  68   5 |   4  19    29+1
  56    4  9 |  2   1  68 |   3   7     58
  12   58  3 |  4   7   9 |  25  68  16+258
-------------+------------+---------------
   9    7  5 |  1   2  68 |  68   3      4
   3    1  4 |  5  68   7 |   9   2     68
   8    2  6 |  9   3   4 |   7  15     15


The 5 or the 1 or the 258 leads to r4c9 = 19. This leads to the following:
Code: Select all
  56   56  2 |  8   9   3 |   1   4      7
   7    3  8 |  6   4   1 |  25  59    29+5
   4    9  1 |  7   5   2 |  68  68      3
-------------+------------+---------------
   2   68  7 |  3  68   5 |   4  19     19
  56    4  9 |  2   1  68 |   3   7     58
   1   58  3 |  4   7   9 |  25  68   26+58
-------------+------------+---------------
   9    7  5 |  1   2  68 |  68   3      4
   3    1  4 |  5  68   7 |   9   2     68
   8    2  6 |  9   3   4 |   7  15     15


Another BUG avoidance with 5 or 58 yields r2c9 = 25, and r6c9 = 258, which solves trivially.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Thu Dec 15, 2005 5:59 am

rubylips wrote:Carcul, Did you find all your chains by hand?

Good work, Carcul. Not only that I am pleased with your solution, I am impressed on the short time required to find all these nice loops. Even though you might have written a program to assist with your effort, I know that the technique is totally human executable.:D

Carcul wrote:Chain 11: [r3c4]-8-[r8c4]=8|4=[r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r3c4] => r3c4<>8.

The “=8|4=” is an extended disjoint subset link (due to the ALS r8c1, r8c2, r8c3, r8c4) as defined by Rubylips.

Is it possible to include the coordinates of the ALS in the nice loop notation; perhaps something similar to the grouped nice loops? This would save the footnote and help the reader to follow the propagation of the nice loop with certainty.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Dec 15, 2005 6:16 am

Ruud wrote:At this point, 2 chains are required to make progress:
Code: Select all
Placing Digit 8 in R1C6 forces 2 different cells to Digit 9 in Column 2
Placing Digit 1 in R2C1 forces 2 different Digits in R7C1

Nice and concise, Rudd, Your solution is the only one that doesn't make use of the almost locked set technique. Is there is a method that we can follow to determine what digit to go into which cell in order to trigger a contradiction. As I said in the other thread, a 4 in a magic cell r8c3 would have solved the puzzle. Is there a short cut to find this magic cell?:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Dec 15, 2005 6:28 am

Nicely done, rubylips, I am overwhelmed with the responses and am amazed how much we have advanced in the last 2 months. I can see that the almost locked set technique play a fairly important role in your solution.

rubylips wrote:
Code: Select all
Consider the chain r3c3~7~r2c1-7-r2c5-4-r8c5-4-r8c3-<4|7>-r7c3.
When the cell r3c3 contains the value 7, so does the cell r7c3 - a contradiction.
Therefore, the cell r3c3 cannot contain the value 7.
- The move r3c3:=7 has been eliminated.
The value 1 is the only candidate for the cell r3c3.

The link r8c3-<4|7>-r7c3 is based upon the Almost Locked Set {r7c3,r8c1,r8c2,r8c3}, which contains 5 values, 4 and 7 just once each. The point is that when r8c3 doesn't contain a 4, r7c3 contains a 7 and when r7c3 doesn't contain a 7, r8c3 contains a 4.

Is it possible to incorporate cells for the ALS {r7c3,r8c1,r8c2,r8c3} in your chain notation to give better details.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Dec 15, 2005 6:49 am

Bob Hanson wrote:....using Sudoku Assistant does
require almost-locked sets. I get:

Done! (46 steps) AaMw....

The following is not meant to be "a solution". Rather, it itemizes
all of "basic" logical conclusions that can be drawn from this
PARTICULAR configuration:

Well done, Bob. I gather that your solution is a result of 3D-medusa and almost locked set. Without candidate grids, it is difficult to go through the deductions. However, could you tell us how many deductions were made from 3D-medusa and how many from almost locked set? I know that both techniques can be executed manually.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Dec 15, 2005 6:55 am

Myth Jellies wrote:Sorry about the slightly off-topic, but I just noted a workable 5-candidate BUG cell in Rubylips final grid:

MJ, you have just beaten me on this one. Like you, I just can't refuse to identify a BUG when I could see one.:D

BTW, have you done a POM on this grid. If so, could you post the solution?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Thu Dec 15, 2005 7:37 am

Hi Jeff.

Thanks. Maybe I can rewrite chain 11 in the following way:

Chain 11: [r3c4]-8-[r8c4]=8|4=[r8c1|r8c2|r8c3]-4-[r4c3]=4=[r4c7]-4-[r2c7]=4=[r1c8]=8=[r1c4]-8-[r3c4] => r3c4<>8.

Hi Rubylips and hi Ronk.

Thanks for your explanation, and sorry for the error. I have already edited my original post.

Rubylips wrote:Carcul,
Did you find all your chains by hand?


To be honest, contrary to most people that frequently use this forum, I dont know nothing about computer programing. So, I solve all puzzles just by hand, and that's the way I like it.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Next

Return to Advanced solving techniques

cron