25-clue Toughie

Everything about Sudoku that doesn't fit in one of the other sections

25-clue Toughie

Postby Draco » Mon Jun 16, 2008 6:10 am

Here's one that my solver rates as pretty hard, SE gives a 7.3 and both need several forcing chains (16 if I recall SE's list correctly, 20 for my solver if I let it go after short chains first, which I tend to do) to solve.

Any one able to bring some brevity to this situation, please chime in! The solution I have so no need for that (just in case submacrolize reads this thread). PMs after SSTS applied:
Code: Select all
.......91..48.1....6...534....4...89....5....29...6....872...3....6.75..62.......

378   357  235  | 37   23467 234  | 2678  9    1   
379   37   4    | 8    23679 1    | 267   2567 2567
1789  6    1289 | 79   279   5    | 3     4    278
----------------+-----------------+----------------
137   1357 1356 | 4    237   23   | 1267  8    9   
13478 1347 1368 | 1379 5     2389 | 1267  1267 2367
2     9    138  | 137  378   6    | 147   157  3457
----------------+-----------------+----------------
5     8    7    | 2    149   49   | 1469  3    46 
1349  134  139  | 6    1389  7    | 5     12   28 
6     2    139  | 5    13489 3489 | 14789 17   478


Cheers...

- drac
Last edited by Draco on Sat Jun 28, 2008 1:37 am, edited 1 time in total.
Draco
 
Posts: 143
Joined: 14 March 2008

Postby daj95376 » Mon Jun 16, 2008 8:27 am

There's probably a shorter solution, but I worked hard enough on this one that you're going to get the whole solution.

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

Code: Select all
   c5b8  Locked Candidate 1              <> 1    [r4c5],[r6c5]
 r5  b4  Locked Candidate 1              <> 4    [r5c79]
 r8  b7  Locked Candidate 1              <> 4    [r8c59]
 r2  b3  Locked Candidate 1              <> 5    [r2c2]
 r6  b6  Locked Candidate 1              <> 5    [r6c3]
   c167  Swordfish f/s                   <> 8    [r1c3] -or-
 r368    Swordfish f/s                   <> 8    [r1c3]

 +-----------------------------------------------------------------------+
 |  378    357    235    |  37     23467  234    |  2678   9      1      |
 |  379    37     4      |  8      23679  1      |  267    2567   2567   |
 |  1789   6      1289   |  79     279    5      |  3      4      278    |
 |-----------------------+-----------------------+-----------------------|
 |  137    1357   1356   |  4      237    23     |  1267   8      9      |
 |  13478  1347   1368   |  1379   5      2389   |  1267   1267   2367   |
 |  2      9      138    |  137    378    6      |  147    157    3457   |
 |-----------------------+-----------------------+-----------------------|
 |  5      8      7      |  2      149    49     |  1469   3      46     |
 |  1349   134    139    |  6      1389   7      |  5      12     28     |
 |  6      2      139    |  5      13489  3489   |  14789  17     478    |
 +-----------------------------------------------------------------------+

 r5c6 =8= r9c6 -8- r9c7 =8= r1c7 =6= r1c5 =4= r1c6 -4- r7c6 -9- r5c6  =>  [r5c6]<>9
___________________________________________________________________________________

Code: Select all
   c9    Naked  Pair                     <> 28   [r2c9],[r5c9],[r9c9]
   c5b2  Locked Candidate 1              <> 9    [r7c5],[r8c5],[r9c5]
 r8  b7  Locked Candidate 2              <> 9    [r9c3]

 +-----------------------------------------------------------------------+
 |  78     57     25     |  3      246    24     |  2678   9      1      |
 |  379    37     4      |  8      269    1      |  267    2567   567    |
 |  189    6      1289   |  7      29     5      |  3      4      28     |
 |-----------------------+-----------------------+-----------------------|
 |  137    1357   1356   |  4      237    23     |  1267   8      9      |
 |  13478  1347   1368   |  9      5      238    |  1267   1267   367    |
 |  2      9      38     |  1      378    6      |  47     57     3457   |
 |-----------------------+-----------------------+-----------------------|
 |  5      8      7      |  2      14     49     |  1469   3      46     |
 |  1349   134    139    |  6      138    7      |  5      12     28     |
 |  6      2      13     |  5      1348   3489   |  14789  17     47     |
 +-----------------------------------------------------------------------+

 2- r1c6 -4- r7c6 -9- r7c8 =9= r9c7 =8= r1c7 -8- r3c9 -2  =>  [r3c5]<>2
_______________________________________________________________________

Code: Select all
 r1  b1  Locked Candidate 1              <> 7    [r1c7]

 +-----------------------------------------------------------------------+
 |  78     57     25     |  3      246    24     |  268    9      1      |
 |  9      3      4      |  8      26     1      |  267    2567   567    |
 |  18     6      128    |  7      9      5      |  3      4      28     |
 |-----------------------+-----------------------+-----------------------|
 |  137    157    1356   |  4      237    23     |  1267   8      9      |
 |  13478  147    1368   |  9      5      238    |  1267   1267   367    |
 |  2      9      38     |  1      378    6      |  47     57     3457   |
 |-----------------------+-----------------------+-----------------------|
 |  5      8      7      |  2      14     49     |  1469   3      46     |
 |  134    14     9      |  6      138    7      |  5      12     28     |
 |  6      2      13     |  5      1348   3489   |  14789  17     47     |
 +-----------------------------------------------------------------------+

 r5c6 =8= r6c5 -8- r6c3 -3- r6c9 =3= r5c9 -3- r5c6  =>  [r5c6]<>3
_________________________________________________________________

Code: Select all
   c36   X-Wing    f/s                   <> 3    [r4c1]
   c1    Naked  Triple                   <> 178  [r5c1],[r8c1]
   c3b4  Locked Candidate 1              <> 8    [r3c3]
         XYZ-Wing [r4c2]/[r1c2]+[r4c1]   <> 7    [r5c2]
         XYZ-Wing [r5c2]/[r4c1]+[r8c2]   <> 1    [r4c2]
 r4  b4  Locked Candidate 1              <> 7    [r4c57]
 r4  b5  Naked  Pair                     <> 23   [r4c37]

3-Fish c28b7\r589               AF 021\300  <> 1  [r8c5]

 +--------------------------------------------------------------+
 |  78    57    25    |  3     246   24    |  268   9     1     |
 |  9     3     4     |  8     26    1     |  267   267   5     |
 |  18    6     12    |  7     9     5     |  3     4     28    |
 |--------------------+--------------------+--------------------|
 |  17    57    156   |  4     23    23    |  16    8     9     |
 |  34    14    136   |  9     5     8     |  1267  1267  67    |
 |  2     9     8     |  1     7     6     |  4     5     3     |
 |--------------------+--------------------+--------------------|
 |  5     8     7     |  2     14    49    |  169   3     46    |
 |  34    14    9     |  6     38    7     |  5     12    28    |
 |  6     2     13    |  5     1348  349   |  1789  17    47    |
 +--------------------------------------------------------------+

 r9c6 =9= r9c7 =8= r8c9 -8- r8c5 -3- r9c6  =>  [r9c6]<>3
________________________________________________________

The 1st, 3rd, and 4th chains are forcing chains w/o the obvious companion statement.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Draco » Tue Jun 17, 2008 1:52 am

Danny,

Hard work indeed; thanks for taking the time to detail it!

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby daj95376 » Fri Jun 20, 2008 7:17 am

Since Draco started the thread, I hope it's okay to add to it.

I've added some logic to my chains routine to (hopefully) help me decide which chains are more productive than others. However, I often run into a wall where multiple chains are needed and none stand out. For example:

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

Code: Select all
 +-----------------------------------------------------------------------+
 |  2      4      5      |  178    368    1678   |  1369   139    169    |
 |  13     9      8      |  5      2      16     |  136    4      7      |
 |  6      7      13     |  19     39     4      |  5      8      2      |
 |-----------------------+-----------------------+-----------------------|
 |  37     5      39     |  68     1      89     |  679    2      4      |
 |  17     6      19     |  2      4      5      |  8      79     3      |
 |  4      8      2      |  69     7      3      |  169    5      169    |
 |-----------------------+-----------------------+-----------------------|
 |  589    3      4      |  1789   5689   16789  |  2      179    189    |
 |  589    1      7      |  3      589    2      |  4      6      89     |
 |  89     2      6      |  4      89     17     |  137    137    5      |
 +-----------------------------------------------------------------------+

Code: Select all
{  1} -8r4c4  8r4c6  9r7c6  8r9c5                      [chain__5] <> 8 [r7c4]
{  5} -3r2c7  3r2c1  7r4c1  7r9c7  3r9c8               [chain__5] <> 3 [r1c8],[r9c7]
{ 13} -6r1c9  6r6c9  9r6c4  1r3c4  6r2c6               [chain__5] <> 6 [r1c56],[r2c7]
{  1} -9r3c4  1r3c4  1r5c3  9r4c3  9r7c6               [chain__5] <> 9 [r7c4]
{  1} -9r4c6  9r6c4  1r3c4  1r5c3  9r5c8               [chain__5] <> 9 [r4c7]
{  1} -6r7c5  6r1c5  6r6c9  9r6c4  9r3c5 -9r7c5        [chain__2] <> 9 [r7c5]
{  1} -3r9c8  3r1c8  3r2c1  1r5c1  7r5c8 -7r9c8        [chain__2] <> 7 [r9c8]
{  1} -6r1c9  6r6c9  9r6c4  9r7c6  9r8c9 -9r1c9        [chain__2] <> 9 [r1c9]
{ 15} -1r3c4  1r3c3  1r5c1  7r4c1  7r9c7  1r9c6        [chain__5] <> 1 [r12c6],[r7c4]
{ 10} -6r2c6  6r2c7  6r4c4  8r4c6  9r7c6  6r7c5        [chain__5] <> 6 [r1c5],[r7c6]
{  2}  1r9c8  7r9c6  7r4c7  3r4c1  3r2c7  3r9c8        [chain__9] <> 1 [r9c8]
{  1}  8r7c5  9r9c5  9r3c4  6r6c4  6r1c9  6r7c5        [chain__9] <> 8 [r7c5]
{  1} -9r7c6  9r4c6  3r4c3  7r4c1  7r9c7  1r9c6 -1r7c6 [chain__2] <> 1 [r7c6]
{  1} -5r8c5  5r7c5  6r1c5  6r6c9  9r6c4  9r3c5 -9r8c5 [chain__2] <> 9 [r8c5]
{  1} -5r7c1  5r7c5  6r1c5  6r6c9  9r6c4  9r7c6 -9r7c1 [chain__2] <> 9 [r7c1]
{  1}  6r1c7  6r4c4  9r6c4  1r3c4  1r5c3  9r5c8  9r1c7 [chain__9] <> 6 [r1c7]
{  1}  8r8c5  9r9c5  9r3c4  6r6c4  6r1c9  6r7c5  5r8c5 [chain__9] <> 8 [r8c5]
_____________________________________________________________________________________

Note: the chain__5 chains are really forcing chains, but of the most basic format where one implication stream is trivial. Otherwise, I'm not using forcing chains to resolve the puzzle.

What's the smallest number of chains from this list that will render the puzzle solvable through Singles?

[Edit: added specific chains and added/reworded last paragraphs.]
Last edited by daj95376 on Fri Jun 20, 2008 12:59 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby eleven » Fri Jun 20, 2008 8:07 am

I dont know, but you should not miss the MUG 589 in r789c15, so r7c5 must be 6.
eleven
 
Posts: 1564
Joined: 10 February 2008

Postby hobiwan » Fri Jun 20, 2008 1:32 pm

daj95376 wrote:What's the smallest number of chains in this PM that, when their eliminations are combined, will render the puzzle solvable through Singles?

If the chains can be done sequentially I am down to two:
Code: Select all
Forcing Chain Contradiction in b8   r9c6=1

                                r6c4=9 r3c4=1 r7c4<>1
                               /
  r9c6<>1 r9c6=7 r4c7=7 r4c4=6
                               \
                                r4c6=8 r7c6=9 r7c6<>1

Discontinuous Nice Loop r4c7 -7- r4c1 -3- r2c1 =3= r2c7 -3- r9c7 -7- r4c7 => r4c7<>7

Singles

If all chains have to come from the original pm I'll have to look again.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby daj95376 » Fri Jun 20, 2008 5:04 pm

eleven wrote:I dont know, but you should not miss the MUG 589 in r789c15, so r7c5 must be 6.

Thanks for the feedback!

I don't understand MUGs, but the recent messages on the topic caused that pattern of 589 to jump out at me. I didn't know (for sure) what to do with it, but I guessed and tested [r7c5]=6 ... and Simple Sudoku allowed it!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby daj95376 » Fri Jun 20, 2008 5:08 pm

hobiwan wrote:If all chains have to come from the original pm I'll have to look again.

Nice solution hobiwan!

I'm sorry for not providing enough information. I've updated my original message and hope that my goal is now more specific. I know that the combined effect of my chains reduces the PM to Singles. What I'm having a difficult time doing is finding a (descent) subset of them that'll do the same thing.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Mon Jun 23, 2008 5:38 pm

I don't know whether you are still interested, but this is the best I could find:
Code: Select all
{ 13} -6r1c9  6r6c9  9r6c4  1r3c4  6r2c6               [chain__5] <> 6 [r1c56],[r2c7]

1 XY-Chain, 1 W-Wing, 1 Finned X-Wing


{ 13} -6r1c9  6r6c9  9r6c4  1r3c4  6r2c6               [chain__5] <> 6 [r1c56],[r2c7]
{  1} -9r7c6  9r4c6  3r4c3  7r4c1  7r9c7  1r9c6 -1r7c6 [chain__2] <> 1 [r7c6]

1 W-Wing, 1 Finned X-Wing

{ 13} -6r1c9  6r6c9  9r6c4  1r3c4  6r2c6               [chain__5] <> 6 [r1c56],[r2c7]
{  1} -9r7c6  9r4c6  3r4c3  7r4c1  7r9c7  1r9c6 -1r7c6 [chain__2] <> 1 [r7c6]
{  5} -3r2c7  3r2c1  7r4c1  7r9c7  3r9c8               [chain__5] <> 3 [r1c8],[r9c7]

1 Skyscraper

{ 13} -6r1c9  6r6c9  9r6c4  1r3c4  6r2c6               [chain__5] <> 6 [r1c56],[r2c7]
{  1} -9r7c6  9r4c6  3r4c3  7r4c1  7r9c7  1r9c6 -1r7c6 [chain__2] <> 1 [r7c6]
{  5} -3r2c7  3r2c1  7r4c1  7r9c7  3r9c8               [chain__5] <> 3 [r1c8],[r9c7]
{ 15} -1r3c4  1r3c3  1r5c1  7r4c1  7r9c7  1r9c6        [chain__5] <> 1 [r12c6],[r7c4]

Singles

[Edit: copied wrong chain in last example, thanks daj95376]
Last edited by hobiwan on Tue Jun 24, 2008 1:57 pm, edited 1 time in total.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby Draco » Mon Jun 23, 2008 7:16 pm

Danny,

Always enjoy more puzzles... glad you "hijacked" this.:)

I don't have chains for your PM's to crack to singles, but I do have a single contradiction net. Perhaps someone else can reduce this to a nice loop or two:

r4c6=8 r6c4=9 r3c4=1 r3c5=9 r1c5=3
r4c6=8 r7c6=9 r9c5=8
r4c6=8 [r1c6<>8] + r9c5=8 [r1c5<>8] = r1c4=8 r7c4=7 r9c6=1
r3c5=9 r4c1=3 r4c7=7
r3c5=9 r2c7=3 [r9c7<>3] r9c8=3
[r9c6<>7 + r9c8<>7] = r9c7=7

r4c6<>8

Singles to solve.

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby daj95376 » Mon Jun 23, 2008 11:56 pm

hobiwan wrote:I don't know whether you are still interested, but this is the best I could find:
Code: Select all
{ 13} -6r1c9  6r6c9  9r6c4  1r3c4  6r2c6               [chain__5] <> 6 [r1c56],[r2c7]
{  1} -9r7c6  9r4c6  3r4c3  7r4c1  7r9c7  1r9c6 -1r7c6 [chain__2] <> 1 [r7c6]
{  5} -3r2c7  3r2c1  7r4c1  7r9c7  3r9c8               [chain__5] <> 3 [r1c8],[r9c7]
{  1} -6r7c5  6r1c5  6r6c9  9r6c4  9r3c5 -9r7c5        [chain__2] <> 9 [r7c5]
_____________________________________________________________________________________

Nice try hobiwan. Yes, I'm still interested. However, don't you still need ...

Code: Select all
 *-----------------------------------------------------------*
 | 2     4     5     | 178   38    178   | 1369  19    169   |
 | 13    9     8     | 5     2     6     | 13    4     7     |
 | 6     7     13    | 19    39    4     | 5     8     2     |
 |-------------------+-------------------+-------------------|
 | 37    5     39    | 68    1     89    | 679   2     4     |
 | 17    6     19    | 2     4     5     | 8     79    3     |
 | 4     8     2     | 69    7     3     | 169   5     169   |
 |-------------------+-------------------+-------------------|
 | 5     3     4     | 1789  6     789   | 2     179   189   |
 | 89    1     7     | 3     5     2     | 4     6     89    |
 | 89    2     6     | 4     89    17    | 17    3     5     |
 *-----------------------------------------------------------*

{ 15} -1r3c4  1r3c3  1r5c1  7r4c1  7r9c7  1r9c6        [chain__5] <> 1 [r12c6],[r7c4]

I hate to admit this:( , but your missing chain led to ...

Code: Select all
{  5} -3r2c7  3r2c1  7r4c1  7r9c7  3r9c8               [chain__5] <> 3 [r1c8],[r9c7]
{ 15} -1r3c4  1r3c3  1r5c1  7r4c1  7r9c7  1r9c6        [chain__5] <> 1 [r12c6],[r7c4]
{  1} -9r7c6  9r4c6  3r4c3  7r4c1  7r9c7  1r9c6 -1r7c6 [chain__2] <> 1 [r7c6]
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Steve K » Tue Jun 24, 2008 3:29 pm

Here is what I found: (after ss) - the first puzzle, i suppose
1) (8)r1c7=(8-9)r9c7=(9)r7c7-(9=4)r7c6-(4)r1c6=(4-6)r1c5=(6)r1c7 loop =>
r9c7<>147, r7c5<>9, r9c6<>4, r1c5<>237, r1c7<>27

2) (8)r5c6=(8)r9c6-(8=9)r9c7-(9)r7c7=(9)r7c6 => r5c6<>9 some singles

3) (6)r4c7=(6-5)r4c3=(5-2)r4c1=(2-4)r1c6=(4-6)r1c5=(6)r1c7 loop => r4c3<>13, r247c7<>6 one single
4) (7)r1c12 => r2c12<>7 some singles
5) fxw(3) r8c5=r8c1-r4c1=r4c56 => r6c5<>3
6) pair 28 r38c9 => r9c9<>8, r25c9<>2
7) (2)r4c5=(2-6)r2c5=(6)r1c5-(6)r1c7=(6)r4c7 => r4c7<>2 ss from here
Steve K
 
Posts: 98
Joined: 18 January 2007

Postby hobiwan » Tue Jun 24, 2008 5:58 pm

daj95376 wrote:Nice try hobiwan. Yes, I'm still interested. However, don't you still need ...

Yes I do, I copied the wrong chain (edited my original post). Still, your last solution is shorter than mine.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby Draco » Tue Jun 24, 2008 8:02 pm

Steve K wrote:Here is what I found: (after ss) - the first puzzle, i suppose
1) (8)r1c7=(8-9)r9c7=(9)r7c7-(9=4)r7c6-(4)r1c6=(4-6)r1c5=(6)r1c7 loop =>
r9c7<>147, r7c5<>9, r9c6<>4, r1c5<>237, r1c7<>27

2) (8)r5c6=(8)r9c6-(8=9)r9c7-(9)r7c7=(9)r7c6 => r5c6<>9 some singles

3) (6)r4c7=(6-5)r4c3=(5-2)r4c1=(2-4)r1c6=(4-6)r1c5=(6)r1c7 loop => r4c3<>13, r247c7<>6 one single
4) (7)r1c12 => r2c12<>7 some singles
5) fxw(3) r8c5=r8c1-r4c1=r4c56 => r6c5<>3
6) pair 28 r38c9 => r9c9<>8, r25c9<>2
7) (2)r4c5=(2-6)r2c5=(6)r1c5-(6)r1c7=(6)r4c7 => r4c7<>2 ss from here


Nice loops! Your loops and finned X-Wing used less than half the number of steps I needed with forcing chains/nets.

Danny still seems to have the shortest solution so far.

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby daj95376 » Tue Jun 24, 2008 9:39 pm

hobiwan wrote:I copied the wrong chain (edited my original post). Still, your last solution is shorter than mine.

You discovered the importance of [r7c6]<>1. Let's call it a joint effort on reducing the solution to three chains. Thanks!!!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Next

Return to General

cron