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
From the Sudoku Player's Forum:
- The Ultimate Fish Guide
Fish Groups and Constraint Groups in AIC's (by Myth Jellies)
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 · | · · · |
·-------------·-------------·-------------·
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
**********************************
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).
**********************************
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 (or "defining") set: row 3, box 4, box 5
Cover (or "secondary") set is: 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 (eliminations)
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 · | · · · |
·-------------·-------------·-------------·
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?