16 November 2007 Nightmare: Mutant Jellyfish

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

16 November 2007 Nightmare: Mutant Jellyfish

Post by Ron Moore »

Start position for the 16 November 2007 Nightmare:

000000300040030068000205090000008027080060030120700000050804000960020050002000000

or

Code: Select all

. . .|. . .|3 . .
. 4 .|. 3 .|. 6 8
. . .|2 . 5|. 9 .
-----+-----+-----
. . .|. . 8|. 2 7
. 8 .|. 6 .|. 3 .
1 2 .|7 . .|. . .
-----+-----+-----
. 5 .|8 . 4|. . .
9 6 .|. 2 .|. 5 .
. . 2|. . .|. . .
A mutant fish of size N = 4 is enough to solve this one. After opening basics (including three naked triples), the single digit grid for digit 7 is:

Code: Select all

·-------------·-------------·-------------·
|  7  *7   7  |  ·  *7   7  |  ·   7   ·  |
| *7   ·  *7  |  ·   ·  *7  |  ·   ·   ·  |
|  7  *7   7  |  ·  *7   ·  | #7   ·   ·  |
·-------------+-------------+-------------·
|  ·   ·   ·  |  ·   ·   ·  |  ·   ·   7  |
|  7   ·   7  |  ·   ·   ·  |  ·   ·   ·  |
|  ·   ·   ·  |  7   ·   ·  |  ·   ·   ·  |
·-------------+-------------+-------------·
|  7   ·   7  |  ·   ·   ·  |  ·   7   ·  |
|  ·   ·   ·  |  ·   ·   7  |  7   ·   ·  |
|  ·  *7   ·  |  ·  *7   7  |  7   7   ·  |
·-------------·-------------·-------------·
I first noticed a grouped AIC loop for digit 7 (sometimes called "fishy cycle"):
  • (7): r2c13 = r2c6 - r13c5 = r9c5 - r9c2 = r13c2 - r2c13
The 7's in the loop are marked with "*" in the diagram. The general conclusion for an AIC loop (of any form) is that the links of weak inference are links of strong inference as well. In this case, that means that all of the unmarked 7's in box 1, box 2, and row 9 can be eliminated.

A previous thread (here) which I introduced some time ago discussed general fish patterns. To recap: For a general fish of size N for some particular digit X, we look for some set of N houses, called the "base set," such that each digit X candidate in the base set is "covered by" (i.e., lies within the union of) some other set of N houses, called the "cover set". If such sets can be identified, then each digit X candidate in the cover set, but not the base set, can be eliminated. (In some cases we can say a bit more, as discussed in the referenced thread, but this will suffice for the present discussion.)

A conclusion of the referenced thread was that for any single-digit AIC loop, there naturally corresponds a fish pattern. If the loop has 2*N nodes, the fish will be of size N. The base set will be those N houses in which the links of strong inference occur, and the cover set will be those N houses in which the links of weak inference occur. The AIC loop conclusion, that the (initially identified) links of weak inference are links of strong inference as well, translates directly into the general fish conclusion, that candidates in the cover set but not the base set can be eliminated.

I find it much easier to see single digit AIC loops than general fish patterns. In this case, though, it was well worth the effort to consider the above loop in its equivalent fish formulation, because it's then fairly easy to see how to augment the associated base and cover sets to produce a fish one size larger.

Diagram and AIC loop repeated for convenience:

Code: Select all

·-------------·-------------·-------------·
|  7  *7   7  |  ·  *7   7  |  ·   7   ·  |
| *7   ·  *7  |  ·   ·  *7  |  ·   ·   ·  |
|  7  *7   7  |  ·  *7   ·  | #7   ·   ·  |
·-------------+-------------+-------------·
|  ·   ·   ·  |  ·   ·   ·  |  ·   ·   7  |
|  7   ·   7  |  ·   ·   ·  |  ·   ·   ·  |
|  ·   ·   ·  |  7   ·   ·  |  ·   ·   ·  |
·-------------+-------------+-------------·
|  7   ·   7  |  ·   ·   ·  |  ·   7   ·  |
|  ·   ·   ·  |  ·   ·   7  |  7   ·   ·  |
|  ·  *7   ·  |  ·  *7   7  |  7   7   ·  |
·-------------·-------------·-------------·
  • (7): r2c13 = r2c6 - r13c5 = r9c5 - r9c2 = r13c2 - r2c13
The fish naturally corresponding to the AIC loop is of size N = 3.
  • Base set: row 2, column 2, column 5 (all candidates marked with "*" in the diagram)

    Cover set: box 1, box 2, row 9 (all candidates marked with "*" lie in these houses)
Now it's easy to see that if we add row 3 to the base set, we are introducing only one new uncovered candidate in the configuration, at r3c7 (marked with "#"); we can easily take care of covering this candidate by adding box 3 to the cover set. Summarizing, the larger fish pattern is
  • Base set: row 2, row 3, column 2, column 5

    Cover set: boxes 1, 2, and 3; and row 9
This larger fish adds one new elimination, of (7)r1c8, and this, along with the previously identified eliminations, is enough to complete the puzzle with singles only thereafter.

(Observant readers may have noticed that the originally claimed eliminations of (7)r3c13 from the smaller fish do not directly follow from the larger fish, since those cells become part of the larger fish's base set. However, the larger fish produces a hidden single in box 3, at r3c7, and this of course eliminates (7)r3c13, among others.)
Sudtyro
Hooked
Hooked
Posts: 49
Joined: Tue Jan 16, 2007 8:17 pm

Re: 16 November 2007 Nightmare: Mutant Jellyfish

Post by Sudtyro »

Ron Moore wrote:

Code: Select all

·-------------·-------------·-------------·
|  7  *7   7  |  ·  *7   7  |  ·   7   ·  |
| *7   ·  *7  |  ·   ·  *7  |  ·   ·   ·  |
|  7  *7   7  |  ·  *7   ·  | #7   ·   ·  |
·-------------+-------------+-------------·
|  ·   ·   ·  |  ·   ·   ·  |  ·   ·   7  |
|  7   ·   7  |  ·   ·   ·  |  ·   ·   ·  |
|  ·   ·   ·  |  7   ·   ·  |  ·   ·   ·  |
·-------------+-------------+-------------·
|  7   ·   7  |  ·   ·   ·  |  ·   7   ·  |
|  ·   ·   ·  |  ·   ·   7  |  7   ·   ·  |
|  ·  *7   ·  |  ·  *7   7  |  7   7   ·  |
·-------------·-------------·-------------·
Hi Ron,

That’s a very interesting grid to illustrate AIC loops and fishy cycles. And I very much agree that it’s easier to spot the AIC loops vice the general fish patterns...especially after learning (from some of your previous threads) about how to use grouped AIC’s.

In fact, looking a bit further at your grid, I ran across the following AIC loop:
(7): r2c13 = r2c6 – r8c6 = r8c7 – r7c8 = r7c13 – r9c2 = r13c2 - r2c13,
which reveals a different mutant Jellyfish (N=4):
base: r2r8r7c2
cover: c6b9b7b1

Yet another AIC loop provides a mutant Squirmbag (N=5):
(7): r2c13 = r2c6 – r8c6 = r8c7 – r3c7 = r1c8 – r7c8 = r7c13 – r9c2 = r13c2 - r2c13
base: r2r8b3r7c2
cover: c6c7c8b7b1

As you pointed out, these AIC loops always correspond to a fish pattern (with the strong links forming the base set, and the initial weak links forming the cover set). But, the converse does not necessarily hold, in that your mutant Jellyfish does not seem to have a corresponding AIC loop. [Edit to add: The two new mutant fish above (and there are others) give the same eliminations as the original Swordfish, but they do not provide for the r1c8 <> 7 elimination.] Is there some sort of general rule about this?

And one more related question: If one searches a single-digit grid for AIC loops and does not find any, then it's still possible that fish are present. So, to avoid a lot of fruitless (pattern) searching, is there a simple manual test or algorithm that one can use to quickly prove that no fish patterns are present in the grid? Myth Jellies reported on one trick here, but there may be others.

[Edit to add: The base set (r2r3c2c5) of your mutant Jellyfish has two houses that share a common candidate: r3 and c2 share the digit in r3c2. Doesn't that violate one of the defining rules for a fish?]
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

Post by Ron Moore »

Sudtyro,

I'm sorry, I can't really help with your questions. The thread I referenced was basically a "learn as you go" experience for me so I don't want to claim any expertise in this area. I certainly don't know of any rule or heuristic principle which might help us in determining when a useful fish without a naturally corresponding AIC loop might be present. I like your alternative AIC loops, but the key for a single "knockout" step for the solution is the elimination at r1c8 (along with r9c8, which comes from any of the AIC loops). I'm sure this is the reason behind your question. It's seems pretty clear that no standard AIC loop can eliminate (7)r1c8, and I don't know of any way of recognizing the useful larger fish except "by inspection." For your second question, I assume you're looking for some kind of coloring or labeling procedure suitable for use by a human solver to help find general fish patterns or show that none exist. Again, I don't know of any such procedure or algorithm. However, in some further study after my referenced thread, I did come across some interesting posts by Obi-Wahn on the Sudoku Players' Forum. He gives an algorithm for computer program solvers to find general fish. At the moment I don't have time to look for the link for this, but you can search www.sudoku.com for his posts if you're interested.

So I'm afraid I've come up empty-handed in regard to your specific questions. Maybe you'll find of interest, at least theoretically, Obi-Wahn's characterization of general finned and sashimi fish in this thread. So far our discussions on exotic fish on this forum have addressed only unfinned fish. Obi-Wahn's characterization seems surprisingly simple. My paraphrase is really an oversimplification, as his full statement is more general, but for practical purposes this is the idea:

For a given digit X, a general finned (possibly sashimi) fish pattern exists if there is some base set of N houses, all of whose digit X candidates are covered by some cover set of N + 1 houses. Any candidate not in the base set, but which lies in the intersection of two of the houses of the cover set, may be eliminated.

After a little thought, it became clear that this rule readily handles our standard finned X-wings, swordfish, etc. It also occurred to me that the familiar empty rectangle (ER) pattern can be alternately considered as a general finned fish. The diagram below shows a typical ER configuration.

Code: Select all

/ = does not contain 7 as a candidate
· = may optionally contain 7 as a candidate

·-------------·-------------·-------------·
|  /   7   /  |  /   7   /  |  /   /   /  |
|  ·   ·   ·  |  ·   ·   .  |  ·   ·   ·  |
|  ·   ·   ·  |  ·   ·   ·  |  ·   ·   ·  |
·-------------+-------------+-------------·
|  ·   ·   ·  |  /   7   /  |  ·   ·   ·  |
|  ·   ·   ·  |  /   7   /  |  ·   ·   ·  |
|  ·  -7   ·  |  7   7   7  |  ·   ·   ·  |
·-------------+-------------+-------------·
|  ·   ·   ·  |  ·   ·   ·  |  ·   ·   ·  |
|  ·   ·   ·  |  ·   ·   ·  |  ·   ·   ·  |
|  ·   ·   ·  |  ·   ·   ·  |  ·   ·   ·  |
·-------------·-------------·-------------·
Viewed as an ER pattern, the ER itself is in box 5; the associated conjugate pair is in row 1, in r1c25; and the eliminated candidate is r6c2.

To view this as a general finned fish, let's take row 1 and box 5 as our base set.

Note that all of the 7's in these two houses are covered by column 2, column 5, and row 6, so let's take these houses as the cover set. r6c2 lies in two houses of the cover set, but not the base set, so the general finned fish rule gives the same elimination as the ER pattern.

Perhaps it's already obvious to you -- "2 string kites" and "skyscrapers" can also be viewed as general finned fish. "Skyscraper" is another term for sashimi X-wing, and sashimi and full finned X-wings are viewed in exactly the same way -- with the same base and cover sets, and the
same eliminations. Maybe this is helpful in understanding larger sashimi fish. The same base and cover sets for a finned swordfish also work for any related sashimi swordfish. The fact that the sashimi swordfish lacks one or more candidates in the base set of the finned swordfish doesn't really change anything. The cover set is still a cover (all the more so), so the same eliminations follow.

On other matters, I do want to say that although I did not respond, I have read your post on ALS search strategies and more recently the post on "simple" AIC's not involving ALS's. These were well presented. Generally, I don't quite have the patience that you seem to have in your approach, as I usually can come up with AIC's "by inspection" (and some might consider that dangerously close to "trial and error"). Every Sudoku player finds satisfaction from his/her particular approach in solving the puzzles, and I think you've done a good job in presenting the ideas you've found helpful.
Sudtyro
Hooked
Hooked
Posts: 49
Joined: Tue Jan 16, 2007 8:17 pm

Post by Sudtyro »

Many thanks, Ron, for the helpful feedback and suggestions. I had a feeling there were no “simple” answers to those two questions.

Your reference to Obi-Wahn’s posts regarding finned fish is very interesting, and I plan to take a closer look at those threads. I also found your example of the ER pattern as a finned fish to be very interesting, but I’ll need to study that a bit, as well.

I guess the only remaining loose end for me regards your original mutant Jellyfish. It would appear that the base set (r2r3c2c5) for that pattern has houses with common candidates: r3, c2 and c5 share occupied cells (r3c2 and r3c5). Doesn’t that violate one of the defining rules for a fish?
Ron Moore
Addict
Addict
Posts: 72
Joined: Sun Aug 13, 2006 3:34 am
Location: New Mexico

Post by Ron Moore »

Sudtyro wrote: I guess the only remaining loose end for me regards your original mutant Jellyfish. It would appear that the base set (r2r3c2c5) for that pattern has houses with common candidates: r3, c2 and c5 share occupied cells (r3c2 and r3c5). Doesn’t that violate one of the defining rules for a fish?
Yes, you're quite right. That's a big goof on my part. I had difficulty in submitting my previous post the first time I tried (perhaps you were editing yours at the time), and in my later attempt I was rushed and didn't notice your edits. When time permits I'll try to salvage anything useful here with some edits.
Post Reply