20 April 2006 Nightmare is very tough

Discuss the <a href="http://www.sudocue.net/daily.php">Daily Sudoku Nightmare</a> here
Post Reply
David Bryant
Gold Member
Gold Member
Posts: 86
Joined: Fri Jan 20, 2006 6:21 pm
Location: Denver, Colorado
Contact:

20 April 2006 Nightmare is very tough

Post by David Bryant »

I thought today's "nightmare" was tougher than most.

Code: Select all

1..7.....
......84.
8.6.5...2
...18.9..
2.......3
..7.34...
3...1.7.8
.65......
.....5..6
After avoiding a non-unique rectangle, I found a non-unique hexagon growing out of the same configuration. After dealing with that I found 5 double-implication chains (all closely associated with the non-unique hexagon) that finally cracked it wide open.

I'll post my complete solution tomorrow -- I'm curious if anyone found a simpler path through this thicket. dcb
David Bryant
Gold Member
Gold Member
Posts: 86
Joined: Fri Jan 20, 2006 6:21 pm
Location: Denver, Colorado
Contact:

How I got through this one

Post by David Bryant »

After making all the "obvious" moves (including the avoidance of a non-unique rectangle at r5&9, c2&3) I reached this position.

Code: Select all

  1   23459 2349    7    249    8    356   369   59
 59   23579  239  2369   269  12369   8     4   1579
  8   3479    6    349    5    139   13   1379    2
 456   345   34     1     8    276    9    276   457
  2    459   18*   569   679   679  1456  1678*   3
 569   18*    7   2569    3     4   1256  1268*  15
  3    249   249   469    1    69     7     5     8
 479    6     5     8   2479  2379  1234  1239   149
 479   18*   18*  2349  2479    5    234   239    6
1. Potential "non-unique hexagon" in r56&9, c23&8.
Since "8" must lie in r5c8 or r6c8, eliminate "1" from those two cells.

2. 5-star constellation from r6c9 eliminates "1" at r3c6.
A. r6c9 = 1 ==> the "1" in top right box lies in row 3 ==> r3c6 <> 1.
B. r6c9 = 5 ==> r1c7 = 5 ==> r1c8 = 6 ==> {2, 7, 8} triplet in c8r456 ==> r2c9 = 7 ==> pair {1, 3} in r3c7&8 ==> r3c6 <> 1.

3. r2c6 = 1 (unique vertical).

Now the grid looks like this.

Code: Select all

  1   23459 2349    7    249    8    356   369   59
 59   23579  239  2369   269    1     8     4    579
  8   3479    6    349    5    39    13   1379    2
 456   345   34     1     8    276    9    276   457
  2    459   18    569   679   679  1456   678    3
 569   18     7   2569    3     4   1256   268   15
  3    249   249   469    1    69     7     5     8
 479    6     5     8   2479  2379  1234  1239   149
 479   18    18   2349  2479    5    234   239    6
4. 6-star constellation from r6c9 eliminates "6" at r5c8.
A. r6c9 = 1 ==> r6c2 = 8 ==> r5c3 <> 8 ==> r5c8 = 8; 8 <> 6.
B. r6c9 = 5 ==> r1c7 = 5 ==> r1c8 = 6 ==> r5c8 <> 6.

5. A long double-implication chain proves that r5c8 <> 7.
A. r5c8 = 7 ==> {6, 9} pair in r5c5&6 ==> r5c4 = 5 ==> r5c2 = 4.
B. r5c8 = 7 ==> {1, 3, 9} triplet in row 3 ==> r3c4 = 4 ==> {6, 9} pair in r7c4&6.
{6, 9} pair ==> {2, 4} pair in r7c2&3 ==> {7, 9} pair in c1r8&9 ==> r2c1 = 5 ==> r6c1 = 6 ==> r4c1 = 4.

But we can't have two "4"s in the middle left 3x3 box, so r5c8 = 8.

6. r5c3 = 1; r6c2 = 8; r9c2 = 1; r9c3 = 8 (sole candidates); the "7" in row 5 lies in the middle center 3x3 box.

Now a couple more constellations finish it off. The grid has been reduced to this state.

Code: Select all

  1   23459 2349    7    249    8    356   369   59
 59   23579  239  2369   269    1     8     4    579
  8   3479    6    349    5    39    13   1379    2
 456   345   34     1     8    26     9    276   457
  2    459    1    569   679   679  1456    8     3
 569    8     7   2569    3     4   1256   26    15
  3    249   249   469    1    69     7     5     8
 479    6     5     8   2479  2379  1234  1239   149
 479    1     8   2349  2479    5    234   239    6
7. 4-star constellation from r6c8 proves that r4c6 = 2.
A. r6c8 = 2 ==> r4c6 = 2 (only spot left in middle center 3x3 box).
B. r6c8 = 6 ==> r4c1 = 6 (only spot left in column 1) ==> r4c6 = 2.

8. A long double-implication chain proves that r4c8 <> 7.
A. r4c8 = 7 ==> r4c1 = 6 (only spot left in row 4).
B. r4c8 = 7 ==> r4c1 = 4 (by the same logic used in 5B, above).

And with r4c8 = 6 this very tough nut finally splits wide open. dcb
gerund
New kid on the Grid
New kid on the Grid
Posts: 2
Joined: Tue Apr 25, 2006 2:03 pm

20th. April Nightmare

Post by gerund »

Correct me if I am wrong, but aren't the official solution and David's
producing a non unique situation at (2, 7-8) and(5, 7-8)?
David Bryant
Gold Member
Gold Member
Posts: 86
Joined: Fri Jan 20, 2006 6:21 pm
Location: Denver, Colorado
Contact:

Re: 20th. April Nightmare

Post by David Bryant »

gerund wrote:Correct me if I am wrong, but aren't the official solution and David's producing a non unique situation at (2, 7-8) and (5, 7-8)?
Good question, gerund. In the final solution, the pair {8, 4} appears in row 2, c7&8, and the pair {4, 8} appears in row 5, same columns.

The thing is, the pair {8, 4} in row 2 was given as part of the original set of clues. So it's not a non-unique rectangle, because the values at two of the corners can't be changed, by definition. dcb

PS Those darned smilies are always getting in the way! You might want to use something besides parentheses (say square brackets, or curly braces) to avoid that problem -- or you can always check the "disable smilies" box before submitting your message.
gerund
New kid on the Grid
New kid on the Grid
Posts: 2
Joined: Tue Apr 25, 2006 2:03 pm

Nightmare 20th.April

Post by gerund »

Thank you David. My mistake.
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

Hi gerund, welcome to the forum.

I have removed the offending 8) smiley. 8-)

Ruud.
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

An XY ring

Post by Ron Moore »

While slowly working through the archives I decided to skip ahead to this one, since it figured to be challening if David found it tough. Indeed it was. I'm posting my solution since I came across what I expect is a rare configuration -- a continuous, cyclic XY chain. After some quick research on another site I think the accepted term for this is "XY ring." This comes as the last major step in my solution.

I got to this point with basic techniques and avoidance of the non-unique rectangle which David mentioned. (I did not see the non-unique hexagon possibility).

Code: Select all

 .------------------.-------------------.------------------.
| 1     23459 2349 |  7     249   8    | 356   369   59   |
| 59    23579 239  |  2369  269   12369| 8     4     1579 |
| 8    A3479  6    | B349   5     139  | 13    1379  2    |
&#58;------------------+-------------------+------------------&#58;
|F456  -345   34   |  1     8     267  | 9     267   457  |
| 2    -459   18   |  569   679   679  | 1456  1678  3    |
| 569   18    7    |  2569  3     4    | 1256  1268  15   |
&#58;------------------+-------------------+------------------&#58;
| 3    D249  D249  | C469   1     69   | 7     5     8    |
|E479   6     5    |  8     2479  2379 | 1234  1239  149  |
|E479   18    18   |  2349  2479  5    | 234   239   6    |
'------------------'-------------------'------------------'

Here I found a grouped Alternating Inference Chain (please correct my terminology if necessary) which shows that 4 can be removed from r45c2. The nodes in the chain for candidate 4 are identified by letters A (cell r3c2) through F (cell r4c1) in the diagram. Nodes D and E are groups of cells, in this case pairs. The chain

A = B - C = D - E = F

shows that A and F are strongly linked so that 4 can be removed from any cell seeing both A and F. (Note that the link between D and E is actually a strong link, but a strong link can serve as a weak link in an alternating chain.)

Following up these eliminations at r45c2, I then found
  • an Empty Rectangle for digit 9 in box 7, eliminating 9 from r7c4 (actually this is available in the diagram position).
    a naked triple of {1,2,3} in column 7.
    a hidden pair of {1,8} in row 5.
These steps along with more basic techniques reduce the grid to the following:

Code: Select all

.------------------.------------------.------------------.
| 1     23459 2349 | 7     249   8    | 56    36    59   |
| 59    23579 239  |-2369  269   1    | 8     4     579  |
| 8     3479  6    |-349   5    A39   |B13   C137   2    |
&#58;------------------+------------------+------------------&#58;
| 456   35    34   | 1     8     2    | 9    D67    57   |
| 2     59    1    | 569   679  -679  | 4     8     3    |
| 569   8     7    |F59    3     4    |E56    2     1    |
&#58;------------------+------------------+------------------&#58;
| 3     249   249  | 46    1     69   | 7     5     8    |
| 79    6     5    | 8     279   379  | 123   139   4    |
| 479   1     8    | 2349  2479  5    | 23    39    6    |
'------------------'------------------'------------------' 
At this point I found an "almost" XY chain in cells A (r3c6) through F (r6c4) above. Cell C is not a bivalued cell, but when traversing the chain one of the candidates will be eliminated by a previous cell. (I suppose it could be more formally considered a grouped XY chain with B and C grouped as one node). Candidate 9 can be removed from those cells which see both of cells A and F (marked with "-" in the diagram).

This brings us to the configuration with the XY ring, in cells r37c46 (marked A, B, C, D in the diagram below). For some of the cells I've changed the natural order of the candidates to make the cyclic structure more apparent:

Code: Select all

.------------------.------------------.------------------.
| 1     23459 2349 | 7     249   8    | 56    36    59   |
| 59    23579 239  |-236   269   1    | 8     4     579  |
| 8    -3479  6    |A43    5    B39   |-13   -137   2    |
&#58;------------------+------------------+------------------&#58;
| 456   35    34   | 1     8     2    | 9     67    57   |
| 2     59    1    | 569   679   67   | 4     8     3    |
| 569   8     7    | 59    3     4    | 56    2     1    |
&#58;------------------+------------------+------------------&#58;
| 3     249   249  |D46    1    C96   | 7     5     8    |
| 79    6     5    | 8     279  -379  | 123   139   4    |
| 479   1     8    |-2349  2479  5    | 23    39    6    |
'------------------'------------------'------------------'
For any side of this rectangle (or more generally, any side of an XY ring), the common candidate shared by the two vertex cells can be removed from any cell seeing both vertices. In this case, 3 is eliminated from r2c4 and r3c278; 9 is eliminated from r8c6, and 4 is eliminated from r9c4.

After these eliminations the rest is straightforward.
Myth Jellies
Hooked
Hooked
Posts: 42
Joined: Tue Apr 04, 2006 7:07 am

Re: An XY ring

Post by Myth Jellies »

Ron, you have AICs nailed. Nice job, and those were some fairly complex chains. You might try the following for notation...

Code: Select all

 .------------------.-------------------.------------------.
| 1     23459 2349 |  7     249   8    | 356   369   59   |
| 59    23579 239  |  2369  269   12369| 8     4     1579 |
| 8    A3479  6    | B349   5     139  | 13    1379  2    |
&#58;------------------+-------------------+------------------&#58;
|F456  -345   34   |  1     8     267  | 9     267   457  |
| 2    -459   18   |  569   679   679  | 1456  1678  3    |
| 569   18    7    |  2569  3     4    | 1256  1268  15   |
&#58;------------------+-------------------+------------------&#58;
| 3    D249  D249  | C469   1     69   | 7     5     8    |
|E479   6     5    |  8     2479  2379 | 1234  1239  149  |
|E479   18    18   |  2349  2479  5    | 234   239   6    |
'------------------'-------------------'------------------'

(4)A = (4)B - (4)C = (4)D - (4)E = (4)F => r45c2 <> 4
or
(4)r3c2 = (4)r3c4 - (4)r7c4 = (4)r7c23 - (4)r89c1 = (4)r4c1 => r45c2 <> 4

Code: Select all

.------------------.------------------.------------------.
| 1     23459 2349 | 7     249   8    | 56    36    59   |
| 59    23579 239  |-2369  269   1    | 8     4     579  |
| 8     3479  6    |-349   5    A39   |B13   C137   2    |
&#58;------------------+------------------+------------------&#58;
| 456   35    34   | 1     8     2    | 9    D67    57   |
| 2     59    1    | 569   679  -679  | 4     8     3    |
| 569   8     7    |F59    3     4    |E56    2     1    |
&#58;------------------+------------------+------------------&#58;
| 3     249   249  | 46    1     69   | 7     5     8    |
| 79    6     5    | 8     279   379  | 123   139   4    |
| 479   1     8    | 2349  2479  5    | 23    39    6    |
'------------------'------------------'------------------' 
(9=3)A - (3=1&7)BC - (7=6)D - (6=5)E - (5=9)F => r23c4,r5c6 <> 9
or
(9=3)r3c6 - (3=1&7)r3c78 - (7=6)r4c8 - (6=5)r6c7 - (5=9)r6c4 => r23c4,r5c6 <> 9

The interesting step here is the use of the almost locked set (N+1 digits in N cells) in r3c78. Either r3c78 contains a 3 or it contains 1 & 7. You can always divvy up the digits from an ALS on either side of a strong link like this any way that you like. You could even combine A, B, and C together in a single ALS and start your AIC with

(9=1&3&7)r3c678 - (7=6)r4c8 ...
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

Belated Thanks and Acknowledgment

Post by Ron Moore »

MJ,

Thanks for your comments, suggestions, and insight. It would have been more decent of me to acknowledge your treatise on AIC's, which I had seen a few months earlier. My excuse is that I didn't bookmark the link and I couldn't seem to find it quickly. I recently found it, and included it in another recent post of mine. So for the record, here's the link:

Myth Jellies' post on AIC's in sudoku.com forum:

http://www.sudoku.com/forums/viewtopic.php?t=3865
Post Reply