10 July 2007: Mutant Fish Eliminations

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

10 July 2007: Mutant Fish Eliminations

Post by Ron Moore »

Start position for the 10 July 2007 Nightmare:

Code: Select all

800790010000000030014500000000000800000301090072000000000020067069005000080000305

8 . .|7 9 .|. 1 .
. . .|. . .|. 3 .
. 1 4|5 . .|. . .
-----+-----+-----
. . .|. . .|8 . .
. . .|3 . 1|. 9 .
. 7 2|. . .|. . .
-----+-----+-----
. . .|. 2 .|. 6 7
. 6 9|. . 5|. . .
. 8 .|. . .|3 . 5
Until recently, my study of exotic fish, by which I mean Frankenfish and mutant fish, had been limited. Actually, it still is, though I have taken a cursory look at the following references:

From the Sudoku Player's Forum:From Sudopedia:There's a tremendous amount of material here, and I probably never will absorb all of it. I may well have some misconceptions, so perhaps an experienced Sudoku ichthyologist can correct any errors or provide some additional insight.

In my past limited readings on exotic fish, I had noted that in some cases (but certainly not all), the eliminations from these fish could be obtained from single digit AIC loops, in general requiring grouped nodes. These are AIC's for a single digit, in which the nodes may consist of single cells or possibly a group of two or three aligned cells within a box, and which form a continuous loop with alternating links of strong and weak inference. As regular readers of this forum know, the existence of such a loop means that the links of weak inference are actually strong conjugate links as well. Thus, the subject digit can be removed from any cell which sees (all cells of) any two consecutive nodes of the loop.

Since chains propogate one link at a time, in one dimension only, I'm much more likely to find a single digit grouped AIC loop rather than an entire fish structure, which requires visualization in two dimensions simultaneously. When the possibility of exotic fish is introduced, the visualization becomes even more difficult. So basically I've been content to limit myself to looking for grouped AIC's, rather than exotic fish structures as such.

Now to the puzzle. After initial basics we have the grid shown below for digit 6.

Code: Select all

·-------------·-------------·-------------·
|  ·   ·  A6  |  ·   ·  -6  | F6   ·  F6  |
| -6   ·   ·  | D6   ·  -6  | E6   ·   ·  |
|  6   ·   ·  |  ·   ·   6  |  ·   ·   ·  |
·-------------+-------------+-------------·
| -6   ·  B6  | C6   ·  -6  |  ·   ·  -6  |
|  6   ·   ·  |  ·   ·   ·  |  6   ·   6  |
|  6   ·   ·  |  ·   ·   6  |  6   ·   6  |
·-------------+-------------+-------------·
|  ·   ·   ·  |  ·   ·   ·  |  ·   6   ·  |
|  ·   6   ·  |  ·   ·   ·  |  ·   ·   ·  |
|  ·   ·   ·  |  ·   6   ·  |  ·   ·   ·  |
·-------------·-------------·-------------·
It's possible to derive many of the eliminations shown above from several successive basic single digit patterns (such as skyscrapers, two-string kites, finned X-wings). Nodes A, B, C, and D form a skyscraper which gives the eliminations shown at r1c6 and r2c1. In this case, it's good to remember that there is an underlying AIC behind these patterns, because the AIC for the skyscraper can be easily extended to form a grouped AIC loop, with significantly greater payoff.

In the diagram, the successive nodes of the loop are identified by letters A through F. Node F is the only grouped node. We have

(6): r1c3 = r4c3 - r4c4 = r2c4 - r2c7 = r1c79 - r1c3 => AIC loop, which means that
  • r4c3 = r4c4, giving the eliminations shown in row 4

    r2c4 = r2c7, giving the eliminations shown in row 2

    r1c79 = r1c3, giving the elimination shown in row 1
After this discovery I determined that a mutant fish was indeed present in the grid. The Sudopedia and the "up front" post of the Ultimate Fish Guide use different terminology but the same idea to define general unfinned fish structures and resultant eliminations. Something like this:

**********************************

For any given digit, a fish structure of size N consists of:
  • A "base" or "defining" set of N houses, and

    A "cover" or "secondary" set of N houses, such that:

    No two houses of the base set share a common candidate for the given digit, and

    Each candidate in the base set is "covered by" the cover set (i.e., each candidate in the base set lies in at least one house of the cover set).
Then each candidate in the cover set but not in the base set can be eliminated. (I have a slight problem with this, as it doesn't quite go far enough.)

**********************************

When we limit the base set to a set of rows in the grid, and the cover set to a set of columns (or vice versa), then we have a standard fish -- X wing, swordfish, jellyfish, .... When we allow boxes in either set, or the possibility of mixed house types within either set, then we have an exotic fish.

The diagram below shows how base and cover sets can be chosen in the configuration above, for a fish of size N = 3.

Code: Select all

X = candidates in base &#40;or "defining"&#41; set&#58;  row 3, box 4, box 5

Cover &#40;or "secondary"&#41; set is&#58;  column 1, column 6, row 4

Each X'd candidate lies in at least one house of the cover set 

* = candidates in cover set which are not in base set &#40;eliminations&#41;
 
 cover                 cover
   |                     |
   |                     |
   V                     V
·-------------·-------------·-------------·
|  ·   ·   6  |  ·   ·  *6  |  6   ·   6  |
| *6   ·   ·  |  6   ·  *6  |  6   ·   ·  |
| X6   ·   ·  |  ·   ·  X6  |  ·   ·   ·  |
·-------------+-------------+-------------·
| X6   ·  X6  | X6   ·  X6  |  ·   ·  *6  |   <-- cover 
| X6   ·   ·  |  ·   ·   ·  |  6   ·   6  |
| X6   ·   ·  |  ·   ·  X6  |  6   ·   6  |
·-------------+-------------+-------------·
|  ·   ·   ·  |  ·   ·   ·  |  ·   6   ·  |
|  ·   6   ·  |  ·   ·   ·  |  ·   ·   ·  |
|  ·   ·   ·  |  ·   6   ·  |  ·   ·   ·  |
·-------------·-------------·-------------·
The "*" cells are in the cover set set but not in the base set, and indeed these are among the eliminations given by the grouped AIC above. However, the AIC additionally gives eliminations at r4c1 and r4c6. These cells are in the base set, so that these eliminations would not follow from the general rule that "each candidate in the cover set but not in the base set can be eliminated." Evidently what distinguishes these cells is that each lies in the intersection of two of the houses of the cover set. So, to accommodate mutant fish, the general statement for unfinnned fish eliminations should be something like: each candidate which lies in the cover set but not the base set, or which lies in the intersection of two houses of the cover set, may be eliminated.

It's easy to see in the above case that this must be true. Placing "6" at r4c1, for example, would leave (6)r3c6 as the only candidate in row 3, and would also leave (6)r6c6 as the only candidate in box 5; both of these are in column 6 so that configuration would be invalid.

This may be obvious to many, but it did take a bit of thought for me to understand and state clearly to myself the argument in the general case. For an unfinned fish of size N, since each house of the base set must contain one placement of the subject digit, and since no two houses of the base set share a common candidate, the base set of houses must contain N distinct placements of the subject digit. After any placement in any of the houses of the base set, consider the reduced structure obtained by removing that house of the base set, and any house(s) of the cover set containing the placed candidate. (Since the cover set is in fact a cover, at least one house of the cover set will be removed.) Now, any candidate which was covered by the eliminated cover house(s) will be removed from the structure when that (those) cover house(s) are removed. So, in the reduced structure, each candidate in the reduced base set will still remain covered by (will lie within) one or more houses of the reduced cover set.

Now, successively continuing this placement/reduction process, if at any step a placement is made in the intersection of two of the cover houses, both of those cover houses will be removed, so that the reduced structure will contain one less cover house than base house -- say M - 1 houses in the reduced cover set, and M houses in the reduced base set. Continuing the placement/reduction process from that point, we eventually must obtain a configuration in which zero houses are in the remaining cover set, but one or more houses are in the remaining base set. Clearly this is an impossible situation, since one placement must be made in each house of the base set.
__________________

A general question: When there exists a single digit AIC loop (sometimes called a "fishy cycle", and I'm beginning to see why), is there always an associated fish structure, as in this puzzle?
Myth Jellies
Hooked
Hooked
Posts: 42
Joined: Tue Apr 04, 2006 7:07 am

Post by Myth Jellies »

I believe the answer is yes for closed loop single-digit AICs. I don't know if that has actually been proven yet.

I did cover that intersection concept in the constraint set section of that fish groups in AICs post. It hasn't been noticed by very many others working on fishy stuff though. Check out the post I made in our jigsaw section for an interesting application involving those intersections.
Jean-Christophe
Addict
Addict
Posts: 92
Joined: Mon Apr 23, 2007 12:50 pm
Location: Belgium

Post by Jean-Christophe »

Ron Moore wrote:The diagram below shows how base and cover sets can be chosen in the configuration above, for a fish of size N = 3.

Code: Select all

X = candidates in base &#40;or "defining"&#41; set&#58;  row 3, box 4, box 5

Cover &#40;or "secondary"&#41; set is&#58;  column 1, column 6, row 4

Each X'd candidate lies in at least one house of the cover set 

* = candidates in cover set which are not in base set &#40;eliminations&#41;
 
 cover                 cover
   |                     |
   |                     |
   V                     V
·-------------·-------------·-------------·
|  ·   ·   6  |  ·   ·  *6  |  6   ·   6  |
| *6   ·   ·  |  6   ·  *6  |  6   ·   ·  |
| X6   ·   ·  |  ·   ·  X6  |  ·   ·   ·  |
·-------------+-------------+-------------·
| X6   ·  X6  | X6   ·  X6  |  ·   ·  *6  |   <-- cover 
| X6   ·   ·  |  ·   ·   ·  |  6   ·   6  |
| X6   ·   ·  |  ·   ·  X6  |  6   ·   6  |
·-------------+-------------+-------------·
|  ·   ·   ·  |  ·   ·   ·  |  ·   6   ·  |
|  ·   6   ·  |  ·   ·   ·  |  ·   ·   ·  |
|  ·   ·   ·  |  ·   6   ·  |  ·   ·   ·  |
·-------------·-------------·-------------·
The "*" cells are in the cover set set but not in the base set, and indeed these are among the eliminations given by the grouped AIC above. However, the AIC additionally gives eliminations at r4c1 and r4c6. These cells are in the base set, so that these eliminations would not follow from the general rule that "each candidate in the cover set but not in the base set can be eliminated."
This could also be expressed as an AIC closed loop, with the strong links in the base/defining set, weak links in the cover/secondary set:
(6): r3c1 = r3c6 - r46c6 = r4c4 - r4c3 = r456c1 - r3c1 => AIC loop
=> r4c4 = r4c3 => r4c169 <> 6

One may also "break" closed loops into chains of length N-1 by removing each strong link in turn. And then deduce the intersection for the removed strong link cannot hold the digit:
(6): r3c1 = r3c6 - r46c6 = r4c4 => r4c1 <> 6
(6): r4c3 = r456c1 - r3c1 = r3c6 => r4c6 <> 6

BTW: there is also a simpler AIC loop, with "regular" strong links only:
(6): r3c1 = r3c6 - r2c4 = r4c4 - r4c3 = r1c3 - r3c1
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

Sushimi Fish

Post by Ron Moore »

Ron Moore wrote:A general question: When there exists a single digit AIC loop (sometimes called a "fishy cycle", and I'm beginning to see why), is there always an associated fish structure, as in this puzzle?
This was really an idle question, not all that important. I much prefer working with AIC loops (when those are available) than with base and cover sets for a fish. What puzzled me was that, for the few exotic fish I had been able to see, there didn't seem to be any natural relationship between the fish and AIC loops I had observed, even if they yielded the same eliminations.

The answer occurred to me when I was working on zoltag's recent Sashimi Swordfish thread. Jean-Cristophe, perhaps this is really one of your points in your response here, I'm not entirely sure. In any case, to form a fish naturally corresponding to a given (possibly grouped) AIC loop, all we have to do is take the houses containing the strong links as the base set, and the houses containing the weak links as the cover set. Since each node in the AIC loop is incident with a strong link, the "strong houses" will contain all nodes of the AIC loop, and exactly those nodes since the links are strong. Each node in the loop is also incident with a weak link of the loop, so the "weak houses" will indeed cover all of the candidates in the AIC loop. Finally, since it is in fact a loop, the number of "strong" and "weak" houses will be equal.
Myth Jellies wrote:I did cover that intersection concept in the constraint set section of that fish groups in AICs post.
Yes, I was aware of that -- just hadn't completed a careful reading of that last section. In the past few days I revisited an old Nightmare puzzle from the archives that I had mentally set aside to reconsider some day. I now see that there is a mutant jellyfish in the grid, with a similar "intersection" elimination. I matched it up with one of the examples in the Ultimate Fish Guide, and the corresonding elimination is in fact shown in that example. So the concept is probably understood, and the "up front" wording for eliminations just needs to be updated accordingly.

On a slightly different matter, I mentioned a Sashimi Swordfish thread above. After working on that thread, I thought it might be a good idea to confirm my understanding of the "sashimi" term. I consulted the Sudopedia (for the first time on this topic), and the presentation there suggests that a sashimi fish must become "unstable" or "degenerate" upon removal of the fin candidates. This means that the removal of the fin candidates creates a single in some line, and (after eliminations from that single) a smaller standard fish. Then any candidate which would be eliminated by the reduced fish, and which also lies in the box of the fin, can be eliminated.

The working definition which I had been following was not so restrictive. That was something like: A sashimi fish is a pattern which is "almost" a finned fish, but for the absence of candidates in one or more vertices of the (unfinned) fish which lie in the box of the fin. Then any eliminations from the finned fish are also valid eliminations for the sashimi fish.

I then reread your Filet-O-Fish Rule thread (which I do remember seeing, long ago). After rereading it, I think the Sudopedia interpretation might be construed as consistent with that presentation.

A few hours ago I then read for the first time Myth Jellies' Sashimi/Filet of Anything Concept. Your presentation there is more general and would seem to encompass my working definition. So is my working definition consistent with your intent?
Last edited by Ron Moore on Thu Jul 19, 2007 4:15 pm, edited 1 time in total.
Sudtyro
Hooked
Hooked
Posts: 49
Joined: Tue Jan 16, 2007 8:17 pm

Mutant Fish Eliminations

Post by Sudtyro »

Really learning a lot on this thread...
Ron Moore wrote: (6): r1c3 = r4c3 - r4c4 = r2c4 - r2c7 = r1c79 - r1c3 => AIC loop...
So, isn't this "Fishy Cycle" also a Franken swordfish?
Base: c3, c4, b3
Cover: r1, r2, r4
If so, it would appear to provide all six of the AIC loop's original eliminations without any intersections to worry about.

Of course, the key piece of information (for me) regarding AIC loops came when
Jean-Christophe wrote: ... an AIC closed loop, with the strong links in the base/defining set, weak links in the cover/secondary set ...
I'd never seen that stated anywhere else before and would sure like to see that statement included in Sudopedia's article on "Fishy Cycles." It seems to provide the direct links among AIC loops, Fishy Cycles, and Fish of all types.
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

Re: Mutant Fish Eliminations

Post by Ron Moore »

Sudtyro wrote:Really learning a lot on this thread...
Ron Moore wrote: (6): r1c3 = r4c3 - r4c4 = r2c4 - r2c7 = r1c79 - r1c3 => AIC loop...
So, isn't this "Fishy Cycle" also a Franken swordfish?
Base: c3, c4, b3
Cover: r1, r2, r4
If so, it would appear to provide all six of the AIC loop's original eliminations without any intersections to worry about.
Sudtyro,

Yes, you're correct on that. There are plenty of AIC loops and corresponding fish in this grid. The first fish I happened to see wasn't the one that naturally corresponds to the AIC loop above (your Franken swordfish). On the positive side, my oversight did lead me to the problem in the Sudopedia and Ultimate Fish Guide in the wording about general fish eliminations.
Post Reply