1 June 2007 - "Almost" Swordfish

Discuss the <a href="http://www.sudocue.net/daily.php">Daily Sudoku Nightmare</a> here
Post Reply
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

1 June 2007 - "Almost" Swordfish

Post by Ron Moore »

Start position for the 1 June 2007 Nightmare:

Code: Select all

5 . .|8 . 4|. . 6
. . .|. . .|. . .
9 8 .|6 . 5|. 3 1
-----+-----+-----
. 1 2|. . .|8 4 .
. . .|. . .|. . .
7 . .|. . .|. . 2
-----+-----+-----
. 7 .|5 . 3|. 9 .
8 . .|2 . 1|. . 5
. . 5|. 4 .|3 . .
After initial basics, and a naked "4678" quad in box 9, the grid appears as:

Code: Select all

·-----------------------·------------------------·------------------·
| 5       23      137   | 8       12379    4     |  279   27    6   |
| 12346   2346    13467 | 1379    12379    279   |  5     8     479 |
| 9       8      #47    | 6      *2-7      5     | #247   3     1   |
·-----------------------+------------------------+------------------·
| 36      1       2     | 379     5        679   |  8     4     379 |
| 346     34569   34689 | 13479   1236789  26789 |  1679  1567  379 |
| 7       34569   34689 | 1349    13689    689   |  169   156   2   |
·-----------------------+------------------------+------------------·
| 1246    7       146   | 5       68       3     |  12    9     48  |
| 8      #349    #349   | 2      #79       1     | #467   67    5   |
| 126     269     5     | 79      4        68    |  3     12    78  |
·-----------------------·------------------------·------------------·
Although there are simpler chains or patterns available, the following Alternating Inference Chain (AIC) gets things off to a good start:
  • (7=4)r3c3 - (4)r3c7 = (4)r8c7 - (4=397)r8c235 => r3c5 <> 7
After basic follow up, a naked "1467" quad in column 3, and a skyscraper for digit "4" in r3c37|r8c27 which eliminates (4)r2c2 and (4)r7c3, the position shown in the diagram below is reached.

First, some exposition. We now consider finned X-wings and higher order finned fish as familiar techniques for good intermediate or advanced level players. (That doesn't mean these patterns are always easy to spot, but that they can be recognized and used if spotted.) The logic is based on the fact that a "strong" relationship exists between the base fish pattern and the fin -- either the base fish pattern must be true, or the fin must be true. Thus, any common elimination(s) caused by both alternatives must hold true and can safely be made. In the case of a finned fish, the eliminations from the fin are immediate, as the fin directly sees the victim cells.

The idea here can be extended to include structures which are "almost" fish patterns (or just about any other familiar defined pattern), were it not for the existence of some "spoiler" candidate. The spoiler may not be usable as a fin, but, if we're lucky, the spoiler candidate may, via some inference chain, cause one or more eliminations which also result from the base pattern.

Generally, we assume that a strong link exists between the base pattern and the spoiler candidate -- either the base pattern must hold true, or the spoiler candidate must be true -- so that this strong link can be used in an AIC. Any common elimination(s) caused by the base pattern, and by the spoiler candidate (via the AIC), must hold true and can safely be made.

In the position below, there is an "almost" swordfish for digit 6.

Code: Select all

  ^ = cells of base swordfish pattern, digit 6 &#40;columns 5, 7, 8&#41;
  % = spoiler candidate for swordfish
  # = other cells in AIC
  * = eliminations

·---------------------·------------------·-------------------·
|  5      3      17   | 8     179    4   |  279    27    6   |
|  126   #26     1467 | 13    1379   79  |  5      8     479 |
|  9      8      47   | 6     2      5   |  47     3     1   |
·---------------------+------------------+-------------------·
|  36     1      2    | 79    5      679 |  8      4     379 |
|  346   *45-6   89   | 14   ^16789  2   | ^1679  ^1567  379 |
|  7     *45-6   89   | 134  ^13689  689 | ^169   ^156   2   |
·---------------------+------------------+-------------------·
| #1246   7     #16   | 5    %68     3   | #12     9     48  |
|  8     #49     3    | 2     79     1   | ^467   ^67    5   |
|  126   #269    5    | 79    4      68  |  3      12    78  |
·---------------------·------------------·-------------------·
Columns 5, 7, and 8 almost contain a swordfish pattern, but it's spoiled by the presence of (6)r7c5. The eliminations shown in r56c2 follow if the swordfish pattern is true. They also follow if (6)r7c5 is true, as we have the following AIC:
  • (6)[swordfish r56c5|r568c7|r568c8] = (6)r7c5 - (6=124)r7c137 - (4=296)r289c2 => r56c2 <> 6
After this, the solution is completed with basic techniques (including a naked pair or two).

Acknowledgments: The approach here touches on threads I've seen by Ruud on "Almost Row/Column Subsets (ARCS)" (http://www.sudoku.com/forums/viewtopic.php?t=4731), on "Kraken Fish" in the Sudopedia (http://www.sudopedia.org/wiki/Kraken_Fish), and of course on Myth Jellies' thread on Alternating Inference Chains (http://www.sudoku.com/forums/viewtopic.php?t=3865). The last is the most important, in my opinion, since, as I've tried to indicate parenthetically, the approach can be used with just about any defined pattern -- fish (including finned or sashimi), empty rectangles, skyscrapers, two string kites, or even multi-digit patterns.
rep'nA
Hooked
Hooked
Posts: 49
Joined: Fri Jan 19, 2007 11:37 am
Location: Union City, California

Re: 1 June 2007 - "Almost" Swordfish

Post by rep'nA »

Ron Moore wrote:
In the position below, there is an "almost" swordfish for digit 6.

Code: Select all

  ^ = cells of base swordfish pattern, digit 6 &#40;columns 5, 7, 8&#41;
  % = spoiler candidate for swordfish
  # = other cells in AIC
  * = eliminations

·---------------------·------------------·-------------------·
|  5      3      17   | 8     179    4   |  279    27    6   |
|  126   #26     1467 | 13    1379   79  |  5      8     479 |
|  9      8      47   | 6     2      5   |  47     3     1   |
·---------------------+------------------+-------------------·
|  36     1      2    | 79    5      679 |  8      4     379 |
|  346   *45-6   89   | 14   ^16789  2   | ^1679  ^1567  379 |
|  7     *45-6   89   | 134  ^13689  689 | ^169   ^156   2   |
·---------------------+------------------+-------------------·
| #1246   7     #16   | 5    %68     3   | #12     9     48  |
|  8     #49     3    | 2     79     1   | ^467   ^67    5   |
|  126   #269    5    | 79    4      68  |  3      12    78  |
·---------------------·------------------·-------------------·
Columns 5, 7, and 8 almost contain a swordfish pattern, but it's spoiled by the presence of (6)r7c5. The eliminations shown in r56c2 follow if the swordfish pattern is true. They also follow if (6)r7c5 is true, as we have the following AIC:
  • (6)[swordfish r56c5|r568c7|r568c8] = (6)r7c5 - (6=124)r7c137 - (4=296)r289c2 => r56c2 <> 6
After this, the solution is completed with basic techniques (including a naked pair or two).

\
Ron,

Great solution! I'm always looking for almost patterns, but I completely missed yours this morning. I have one extremely minor simplification to offer.

Code: Select all

·---------------------·------------------·-------------------·
|  5      3      17   | 8     179    4   |  279    27    6   |
|  126   26      1467 | 13    1379   79  |  5      8     479 |
|  9      8      47   | 6     2      5   |  47     3     1   |
·---------------------+------------------+-------------------·
| #36     1      2    | 79    5      679 |  8      4     379 |
| #346   *45-6   89   | 14   ^16789  2   | ^1679  ^1567  379 |
|  7     *45-6   89   | 134  ^13689  689 | ^169   ^156   2   |
·---------------------+------------------+-------------------·
| #1246   7     #16   | 5    %68     3   | #12     9     48  |
|  8     49      3    | 2     79     1   | ^467   ^67    5   |
|  126   269     5    | 79    4      68  |  3      12    78  |
·---------------------·------------------·-------------------·
Just replace the last link in the chain with:
  • (6)[swordfish r56c5|r568c7|r568c8] = (6)r7c5 - (6=124)r7c137 - (4=36)r45c1 => r56c2 <> 6
This has the advantage of begin a slightly smaller set (and it was how I spotted your deduction once I started with your almost swordfish).
"Obviousness is always the enemy to correctness."-Bertrand Russell
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

Post by Ron Moore »

repn'A,

Your simpler alternative is a nice observation. Thanks for pointing it out.
Myth Jellies
Hooked
Hooked
Posts: 42
Joined: Tue Apr 04, 2006 7:07 am

Post by Myth Jellies »

There is also a tutorial on Using Fish Groups and Constraint Groups in AICs

(note that box-line or box-box reductions are examples of simple constraint groups)
Sudtyro
Hooked
Hooked
Posts: 49
Joined: Tue Jan 16, 2007 8:17 pm

Re: 1 June 2007 - "Almost" Swordfish

Post by Sudtyro »

Ron Moore wrote: The eliminations shown in r56c2 follow if the swordfish pattern is true.
Very interesting technique! Just one loose end for me...the swordfish pattern, if true, would also eliminate the 6's in r5c1 and r6c6, so how does one decide, a priori, to disregard those two additional eliminations?
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

Post by Ron Moore »

Sudtyro,

Perhaps the way I presented things suggested that I determined a priori to consider only two of the possible swordfish eliminations and disregard the others. This was actually after the fact.

It's just like any other AIC, such as for an XY chain. When you investigate a possible XY chain beginning with some candidate, you don't start by looking at the possible eliminations which would be caused by that candidate, if true, and decide which of those eliminations you want to investigate and which to disregard. You don't know where the chain might lead (or even if it will pay off), so you keep all options open. You hope to strongly link the start candidate with some end candidate which (if true) causes one or more eliminations which also result if the start candidate is true.

Of course, it's conceivable that another chain, beginning with the same start candidate, might exist which would result in further eliminations. In this case, I didn't pursue other possible chains (beginning with the swordfish and the "spoiler" candidate), since the two eliminations from the chain I gave (or rep'nA's improvement) were enough to complete the puzzle.
Sudtyro
Hooked
Hooked
Posts: 49
Joined: Tue Jan 16, 2007 8:17 pm

Re: 1 June 2007 - "Almost" Swordfish

Post by Sudtyro »

RM,

Thanks for your response and helpful explanation. What a relief to know that you don't actually have that crystal ball! :)

I do have just one additional question. Does the "pattern + spoiler" technique guarantee that chains exist (beginning with the pattern and spoiler candidate) for all the proper eliminations? In other words, for this particular puzzle, the final solution shows in fact that r6c6 <> 6. So, in your last grid position, should a chain exist (beginning with the swordfish and spoiler candidate) to provide for that elimination?
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

Re: 1 June 2007 - "Almost" Swordfish

Post by Ron Moore »

Sudtyro wrote:RM,

I do have just one additional question. Does the "pattern + spoiler" technique guarantee that chains exist (beginning with the pattern and spoiler candidate) for all the proper eliminations? In other words, for this particular puzzle, the final solution shows in fact that r6c6 <> 6. So, in your last grid position, should a chain exist (beginning with the swordfish and spoiler candidate) to provide for that elimination?
No, in general I would not expect that to be true.
Post Reply