The New Sudoku Players' Forum

by **ronk** » Wed Mar 15, 2006 8:35 pm

Havard wrote:
Code: Select all
*(X)X | 7 7 . | . X . 7 # | | . 7 7 | . | 7 . # | | 7 7 7 | . | 7 --|-|-+-------+---|-- 7 | | | 7 7 . | . | 7 . X X | 7 . . | . X . 7 | | | . 7 7 | . . 7 --|-|-+-------+------ . | | | . . . | 7 . . 7 | # | 7 7 . | . . . . # # | . 7 7 | . . . eliminating *

what do you think? does Frankenfish have the right of life, or should we send him back to the deep?

Isn't there a rule that an "exclusion cell" must see ALL the fin cells?

[edit: restored to what Havard quoted]

Ron

by **Havard** » Wed Mar 15, 2006 8:37 pm

ronk wrote:
Havard wrote:
Code: Select all
*(X)X | 7 7 . | . X . 7 # | | . 7 7 | . | 7 . # | | 7 7 7 | . | 7 --|-|-+-------+---|-- 7 | | | 7 7 . | . | 7 . X X | 7 . . | . X . 7 | | | . 7 7 | . . 7 --|-|-+-------+------ . | | | . . . | 7 . . 7 | # | 7 7 . | . . . . # # | . 7 7 | . . . eliminating *

what do you think? does Frankenfish have the right of life, or should we send him back to the deep?

Isn't there a rule that an "exclusion cell" must see ALL the fin cells?

Ron

Frankenfish does not care about rules...

Frankenfish EATS rules! ...mmmm....jummy rules... ..mmm...

Frankenfish

by **tarek** » Wed Mar 15, 2006 8:48 pm

Havard wrote:Frankenfish EATS rules! ...mmmm....jummy rules... ..mmm...

This fish clearly is hazardous in shallow waters.......

I assume that some of the candidates in Box 7 should act as Vertices for the finned swordfish........

There will be at least 1 Fin that doesn't see the the elimination cell...

Tarek

by **ronk** » Wed Mar 15, 2006 8:57 pm

Havard wrote:Frankenfish does not care about rules...

Frankenfish EATS rules! ...mmmm....jummy rules... ..mmm...

The exclusion is obviously valid, since r1c1 true eliminates all candidates in box 4. It's "rule 3" of simple coloring ... a rule hardly anyone implements. But a finned-fish too? I don't think so.

BTW what ALS sets did you use to (edit: directly or indirectly) make the exclusion r6c3<>7?

Ron

by **Ruud** » Thu Mar 16, 2006 3:16 am

I have been reading this thread and checked most of the examples.

Now I will throw in my 2 cents worth.

(I have posted this theory also on the programmers forum, so sorry if you have to read this twice)

Considering the remaining candidates of a digit, where P placements have been made for that digit (including the givens)

When we can find a set of A columns with candidates CA, and a set of B rows with candidates CB, where the size of A + B equals 9 - P, and the intersection on CA and CB is confined to a single box, we have found a finned fish of size (A or B whichever is larger) with the intersection as the fin.

Each candidate in the box containing the fin, that does not belong to CA or CB can be eliminated.

Extra feature: If there is NO intersection, every candidate that does not belong to CA or BC can be eliminated, as we have discovered the non-finned variety.

I have checked this simple rule agains many examples and it holds every time, even for lines with no vertices.

Ruud.

by **ronk** » Thu Mar 16, 2006 4:15 am

Ruud wrote:When we can find a set of A columns with candidates CA, and a set of B rows with candidates CB, where the size of A + B equals 9 - P, and the intersection on CA and CB is confined to a single box, we have found a finned fish of size (A or B whichever is larger) with the intersection as the fin.

Each candidate in the box containing the fin, that does not belong to CA or CB can be eliminated.

Extra feature: If there is NO intersection, every candidate that does not belong to CA or BC can be eliminated, as we have discovered the non-finned variety.

Nice description, Ruud, and the beauty is in its simplicity. It's been quite a while since I've considered sets from the POV of Constraint subsets, but I suspect this "fits that mold."

Ron

by **Myth Jellies** » Thu Mar 16, 2006 5:21 am

Code: Select all: -X- *X *X | X X X | X *X X X #X #X | X X X | X . X X #X #X | X X X | X . X -----------+-----------+----------- X . . | X X X | X . X X *X *X | X X X | X *X X X . . | X X X | X . X -----------+-----------+----------- X **X **X | X X X | X **. X X ##X ##X | X X X | X . X X ##X ##X | X X X | X . X

I like Franken-swordfish and its exchangeable quantum or superposition of fins and nodes (marked with the double symbols). It can also be seen nicely as a hinge or ER and a conjugate pair.

Code: Select all: -X- X X | X X X | X *X X X X X | X X X | X . X X X X | X X X | X . X -----------+-----------+----------- *X . . | X X X | X . X *X *X *X | X X X | X *X X *X . . | X X X | X . X -----------+-----------+----------- X X X | X X X | X . X X X X | X X X | X . X X X X | X X X | X . X

Now Franken-jellyfish is not nearly so hinge friendly

...

Code: Select all: -X- *X *X | X *X X | X *X X X #X #X | X . X | X . X X #X #X | X . X | X . X -----------+-----------+----------- X . . | X . X | X . X X *X *X | X *X X | X *X X X *X *X | X *X X | X *X X -----------+-----------+----------- X **X **X | X **. X | X **. X X ##X ##X | X . X | X . X X ##X ##X | X . X | X . X

by **Havard** » Thu Mar 16, 2006 11:37 am

Myth Jellies wrote:I like Franken-swordfish and its exchangeable quantum or superposition of fins and nodes (marked with the double symbols). It can also be seen nicely as a hinge or ER and a conjugate pair.

Code: Select all
-X- X X | X X X | X *X X X X X | X X X | X . X X X X | X X X | X . X -----------+-----------+----------- *X . . | X X X | X . X *X *X *X | X X X | X *X X *X . . | X X X | X . X -----------+-----------+----------- X X X | X X X | X . X X X X | X X X | X . X X X X | X X X | X . X

Now Franken-jellyfish is not nearly so hinge friendly ...

Code: Select all
-X- *X *X | X *X X | X *X X X #X #X | X . X | X . X X #X #X | X . X | X . X -----------+-----------+----------- X . . | X . X | X . X X *X *X | X *X X | X *X X X *X *X | X *X X | X *X X -----------+-----------+----------- X **X **X | X **. X | X **. X X ##X ##X | X . X | X . X X ##X ##X | X . X | X . X

Great observation, that Franken-Swordfish is actually just an ER...

But Franken-Jellyfish looks frightening... How many of the vertices could you remove and still make it valid? Would it be right to say that you can pick out one X of every column in this diagram:

Code: Select all: * ? ? | . X . | . X . ? ? ? | . | . | . | . ? ? ? | . | . | . | . --|-|-+---|---+---|-- ? | | | . | . | . | . ? X X | . X . | . X . ? X X | . X . | . X . --|-|-+-------+------ ? ? ? | . . . | . . . ? ? ? | . . . | . . . ? ? ? | . . . | . . .

so you can have:

Code: Select all: * ? ? | . X . | . X . ? ? ? | . . . | . . . ? ? ? | . . . | . . . ------+-------+------ ? . . | . . . | . . . ? . X | . . . | . X . ? X . | . X . | . . . ------+-------+------ ? ? ? | . . . | . . . ? ? ? | . . . | . . . ? ? ? | . . . | . . .

and it would still be valid? Looks like it to me! crazy!

ronk wrote:BTW what ALS sets did you use to (edit: directly or indirectly) make the exclusion r6c3<>7?

R67C6(78,89) and R7C13,R89C3 (359,345,457,47) x=9 z=7

havard

by **vidarino** » Thu Mar 16, 2006 11:54 pm

Well, well, this thread really went somewhere.

I'm declaring it a success on my part, too, since I *did* find a big fish pattern without a till-now discernable smaller counterpart. It later turned out to be a freaky smaller fish, but hey...

And, boy, it will be interesting to try to concoct the necessary bits of code to pick this one up.

To celebrate everybody's good work, here another one for you all;

Code: Select all: 125 3 25 | 249 6 7 | 14 8 29 *26 7 *4 | 1 58 *289 | *259 *2569 3 126 9 8 | 234 245 23 | 14 256 7 -------------------+--------------------+-------------------- *7 26 *29 | 68 #289 *5 | *3 *14 14 *259 8 *1 | #29 3 *4 | *259 *7 6 4 256 3 | 7 1 -269 | 259 259 8 -------------------+--------------------+-------------------- *59 125 *7 | 2348 248 *2389 | *6 *124 145 *3 125 *259 | 246 7 *26 | *8 *1249 145 8 4 6 | 5 29 1 | 7 3 29

Squirmbag with 9s in rows, fin in box 5, zaps R6C6.

Filtered:

Code: Select all: . . . | . . . | . . . x . x | . . 9 | 9 9 . . . . | . . . | . . . ----------+-----------+---------- x . 9 | . # x | x x . 9 . x | # . x | 9 x . . . . | . . - | . . . ----------+-----------+---------- 9 . x | . . 9 | x x . x . 9 | . . x | x 9 . . . . | . . . | . . . 9=real vertex, x=virtual, #=fin, -=elimination

Sharpen those fileting knives and get cookin!

Vidar

by **Myth Jellies** » Fri Mar 17, 2006 12:12 am

Code: Select all: . . . | *9 *. . | . . *9 . . . | . . 9 | 9 9 . . 9 . | . . . | . . . ----------+-----------+---------- . . 9 | . #9 . | . . . 9 . . | #9 . . | 9 . . . . . | *. *. -9 | 9 9 *. ----------+-----------+---------- 9 . . | . . 9 | . . . . . 9 | . . . | . 9 . . . . | *. *9 . | . . *9

Another of those 2-0-2 (by rows) or 1-1-2 (by columns) sashimi swordfish.

by **Ruud** » Fri Mar 17, 2006 12:22 am

Hi Vidar,

Isn't there a movie where a Jedi Knight says: "There is always a smaller fish"

Well, here it is:

8 unresolved occurrences for digit 9,
5 rows {24578} (blue)
3 columns {459} (yellow)
all doubles occur in a single box (green)
a single victim (red)

Both of the green cells could be considered part of the swordfish or the fin. This works like the Heisenberg uncertainty principle. Not until we determine how to look at this fish do we discover which is which.

Another nice catch. Keep angling!

Ruud.

by **vidarino** » Fri Mar 17, 2006 12:39 am

Just throwing it in here, so nobody thinks I'm still looking for that elusive Big One With No Counterpart; I'm not. I have found a couple more of this type of beast, though, which my solver still tags as Squirmbag, since I haven't taught it about the empty-line Swordfish variant yet.

And I do believe that the Squirmbag is what you're finding, too, Ruud, since your algorithm need to consider the 5 rows to home in on it. The alternative Swordfish stands out in the columns, of course, but it wouldn't find them without the complementary rows. (Hmm, well, in this case, it might, since the Swordfish doubles as an rather basic X-Cycle.)

Oh, the beauty and simplicity of life in the sea before this thread... ;-)

Vidar

by **Mike Barker** » Fri Mar 17, 2006 3:40 pm

I'd like to add a link to your thread into the collection of solving techniques without requiring people to read thru all 101 posts. Let me try to summarize your results.

In solving a puzzle, the largest N*N fish that needs to be considered is the jellyfish. For all larger column (row) fish there is an 9-N-P row (column) fish or multiple smaller fish which can be used to make eliminations (P is the number of big numbers plus clues for the digit making up the fish). This is only true if fish with more than two fins or equivalently if fish with big fins which cover more than one column (row) are considered. For this to happen all fins must be in the same box, for example, a double finned column jellyfish could look like:

Code: Select all: . . . | . . . | # # . . . . | . X . | X X * . . . | . | . | # # . ------+---|---+-|-|-- . . . | . | . | | | . . . . | . X . | X X . . . . | . | . | | | . ------+---|---+-|-|-- . . . | . | . | | | . . . . | . | . | | | . . . . | . X . | X X . X - body elements of the fish # - fin elements of the fish * - valid elimination

Many of the fish cells are not required for the finned fish to still be valid. For example the "X's" in the finned box need not be present (a sashimi version). In the case where all of the fish cells in the rows (columns) with the big fin lie within the big fin box then eliminations can occur from all non-fish cells in the box and in the other rows (columns) of the fish, for example:

Code: Select all: . . . | . . . | # # * . . . | . . . | # # * . . . | . . . | # # * ------+-------+-|-|-- . . . | . . . | | | . * * * | * X * | X X * . . . | . | . | | | . ------+---|---+-|-|-- . . . | . | . | | | . . . . | . | . | | | . * * * | * X * | X X *

In addition, if a fish with a big fin appears to be missing a row (column), a so called skinny fish, other reductions are possible:

Code: Select all: . . . | * X * | X X * . . . | * X X | X X * . . . | . . . | X X * . . . | * X * | X X * . . . | * X X | X X * * X * | * X * | * * * . . . | * X * | X X * . . . | * X X | X X * . | . | . | . | X X * -------+---|---+-|-|--- -------+---|-|-+-|-|--- ---|---+---|---+-|-|--- . . . | . | . | | | . . . | . | | | | | . . | . | . | . | | | . * * * | * * * | X X * * * * | * X X | X X * * X * | * X * | X X * . . . | . | . | | | . . . | . | | | | | . . | . | . | . | | | . -------+---|---+-|-|--- -------+---|-|-+-|-|--- ---|---+---|---+-|-|--- . . . | . | . | | | . . . . | . | | | | | . . | . | . | . | | | . . . . | . | . | | | . . . . | . | | | | | . . | . | . | . | | | . . . . | . | . | | | . * * * | * X X | X X * * X * | * X * | X X *

Note that eliminations in Boxes 3 and 6 of the first puzzle can also be made because of Box/Box eliminations (Locked Candidates 2).

Additional valid fins may occur in different forms of a Frankenfish where the second form is also an empty rectangle:

Code: Select all: . . . | . . . | # # . . . . | . . . | # # . . . . | . . . | # # . ------+-------+-|-|-- . . . | . # . | | | . . . . | * X * | X X . . . . | . # . | | | . ------+---|---+-|-|-- . . . | . | . | | | . . . . | . | . | | | . . . . | . X . | X X .

Code: Select all: . . . | . . . | # # . . . . | . . . | # # . . . . | . . . | # # . ------+-------+-|-|-- . . . | . . . | | | . . . . | . X . | X X . . . . | . | . | | | . ------+---|---+-|-|-- . . . | . | . | # # . . . . | . | . | # # . . . . | . X . | X X *

These eliminations may also occur in a skinny fish with a big fin:

Code: Select all: . . . | . # . | X X . . X . | * X * | X X - . | . | . # . | X X . ---|---+---|---+-|-|--- . | . | . | . | | | . . X . | . X . | X X . . | . | . | . | | | . ---|---+---|---+-|-|--- . | . | . | . | | | . . | . | . | . | | | . . X . | . X . | X X .

It is also possible for these types to be combined into a Siamese Fish, if allowed by the candidate structure. In the above skinny Franken Jellyfish elimination occur in "*" cells as a result of the Jellyfish and in the "-" cell as a result of a big finned Swordfish. The first example below consists of two Franken Swordfish and the second of a finned X-wing and a Franken Jellyfish:

Code: Select all: . . . | . | . | # # . . . . | . . . | X X . . . . | . | . | # # . . . . | . . . | X X . . . . | . | . | # # . . . . | . . . | X X . ------+---|----+-|--|--- ------+-------+-|-|-- . . . | . X# . | | | - . . . | . # . | X X * . . . | * | * | X# X# . . . . | . | . | # # . . . . | . | . | | | . . X . | - X - | X X * ------+---|----+-|--|--- --|---+---|---+-|-|-- . . . | . | . | | | . . X . | . X . | X X . . . . | . | . | | | . . . . | . . . | . . . . . . | . X . | X X . . . . | . . . | . . .

The four types of "fish" can be understood in terms of Constraint Subsets. For fish the basis subset, "A", consists of "n" columns or rows all of which contain a given candidate. The covering subset, "B", which contains all occurances of the candidate in the columns or rows, determines the type of fish. If "A" consists of columns then the following definitions apply:

Basic Fish:

Finned Fish (Fillet-of-Fish):

Big Finned Fish:

Franken Fish:

If "A" consists of "n" rows then "columns" replaces "rows" and "rows" replaces "columns" in the above definitions. "Almost fish" fit the same definitions, however, eliminations occur via nice loops or via bivalue, ALS, strong link, grouped strong link and/or direct links to another cell. In these cases the eliminated candidate need not be the same as the one that makes up the fish. Note that, contrary to popular opinion, it is possible for Squirmbags to exist for which a smaller "dual" fish does not.

by **ronk** » Fri Mar 17, 2006 4:07 pm

Mike Barker wrote:In solving a puzzle, the largest N*N fish that needs to be considered is the jellyfish. For all larger column (row) fish there is an 9-N row (column) fish which can be used to make eliminations. This is only true if fish with more than two fins are considered.

That would actually be a fish of size "M = 9 - N - P", where P is the number of placements. And that fish might be degenerate, e.g., for M=4 there might be two x-wings instead of one swordfish. This holds whether the fish is finned or not.

And the common viewpoint is one fin comprised of multiple cells (1 to 6 cells) ... not "two fins."

Ron

by **Ruud** » Fri Mar 17, 2006 6:31 pm

Thanks Mike, for the summary.

I have implemented the fishing code and it works perfectly. Finned fish is very common in top-level sudokus. I placed the detection before coloring, and 2 out of 3 coloring steps were replaced by finned fish. About half the template (POM) eliminations were replaced by finned fish.

Here is a beautiful example:

Code: Select all: . . .|. . 5|. 8 . . . 6|. 9 .|. 7 4 . . .|7 . .|. . 3 -----+-----+----- . . 7|5 . .|. 9 . 4 . .|3 . 1|. . 5 . 2 .|. . 7|1 . . -----+-----+----- 3 . .|. . 4|. . . 2 5 .|. 7 .|8 . . . 7 .|2 . .|. . .

After (what we now call) basic eliminations, a sashimi X-Wing is found for digit 2:

Code: Select all: .------------------.------------------.------------------. | 7 139 23 | 4 -1236 *5 | 269 8 *1269 | | 158 138 6 | 18 9 #238 | 25 7 4 | | 1589 4 25 | 7 1268 #268 | 2569 1256 3 | :------------------+------------------+------------------: | 168 1368 7 | 5 2468 *268 | 34 9 *268 | | 4 689 89 | 3 268 1 | 7 26 5 | | 568 2 35 | 9 468 7 | 1 34 68 | :------------------+------------------+------------------: | 3 689 189 | 168 158 4 | 2569 1256 7 | | 2 5 149 | 16 7 39 | 8 1346 169 | | 689 7 1489 | 2 1358 389 | 34 13456 169 | '------------------'------------------'------------------'

Immediately followed by a Sashimi Swordfish for digit 2

Code: Select all: .------------------.------------------.------------------. | 7 139 23 | 4 136 5 | 269 8 1269 | | 158 138 6 | 18 9 *238 |*25 7 4 | | 1589 4 25 | 7 1268 268 | 2569 1256 3 | :------------------+------------------+------------------: | 168 1368 7 | 5 2468 -268 | 34 9 268 | | 4 689 89 | 3 #268 *1 | 7 *26 5 | | 568 2 35 | 9 468 7 | 1 34 68 | :------------------+------------------+------------------: | 3 689 189 | 168 158 4 |*2569 *1256 7 | | 2 5 149 | 16 7 39 | 8 1346 169 | | 689 7 1489 | 2 1358 389 | 34 13456 169 | '------------------'------------------'------------------'

Shortly after that, a Sashimi Swordfish for digit 3:

Code: Select all: .------------------.------------------.------------------. | 7 139 23 | 4 136 5 | 269 8 1269 | | 158 *138 6 | 18 9 *238 | 25 7 4 | | 1589 4 25 | 7 168 268 | 2569 1256 3 | :------------------+------------------+------------------: | 168 *1368 7 | 5 2468 68 |#34 *9 268 | | 4 689 89 | 3 268 1 | 7 26 5 | | 568 2 35 | 9 468 7 | 1 -34 68 | :------------------+------------------+------------------: | 3 689 189 | 168 158 4 | 2569 1256 7 | | 2 5 149 | 16 7 *39 | 8 *1346 169 | | 689 7 1489 | 2 1358 389 | 34 13456 169 | '------------------'------------------'------------------'

This clears up a large portion of the puzzle, until it requires a finned Jellyfish for digit 1 at this point:

Code: Select all: .------------.------------.------------. | 7 *19 2 | 4 3 5 | 69 8 *169| |*18 3 6 |*18 9 2 | 5 7 4 | | 189 4 5 | 7 18 6 | 29 12 3 | :------------+------------+------------: |*16 16 7 | 5 4 8 | 3 9 2 | | 4 89 89 | 3 2 1 | 7 6 5 | | 5 2 3 | 9 6 7 | 1 4 8 | :------------+------------+------------: | 3 689 189| 168 158 4 | 269 125 7 | | 2 5 4 |*16 7 39 | 8 #13 *169| | 69 7 189| 2 158 39 | 4 135-169| '------------'------------'------------'

The grand finale is a Jellyfish with no fins.

Bon apetit,

Ruud.

The New Sudoku Players' Forum

Big fish