## The Ultimate FISH Guide

Advanced methods and approaches for solving Sudoku puzzles

### Re: The Ultimate FISH Guide

StrmCkr wrote:Currently my rules of construction do not allow overlapping active cells with in base sectors.

for all of the following ideas to work correctly this must be true: {until i figure out how to incorporate overlapping active sectors}

It's simple actually. When searching for base sets and cover sets with a useable set of exo-fins, ignore the candidates in the intersections of base sets, i.e., the endo-fins. Then when processing the effect of fins, use the union of endo-fins and exo-fins.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:In general:
Code: Select all
`Sets:  Base (size N):   B  = B1 + B2 ... + BN  Base Intersect:  BI = B1*B2 + B1*B3 ... + B1*BN + B2*B3 ... + (BN-1)*BN  Cover (size N):  C  = C1 + C2 ... + CN  Cover Intersect: CI = C1*C2 + C1*C3 ... + C1*CN + C2*C3 ... + (CN-1)*CN  Hidden:          H  = (B \ C) + BI  Exclusion:       E  = (C \ B) + CISymbol Key:    Bn    <=> units (sectors) of the base set    Cn    <=> units (sectors) of the cover set    '+'   <=> union operator ('|' in C++)    '*'   <=> intersection operator ('&' in C++)    '\'   <=> difference operator (substraction) ("X & ~Y" in C++)  "(...)" <=> operator precedence`

Conjecture: If the "hidden set" is empty, then the "exclusion set" is empty also.

I know that ronk is unavailable for awhile, but I wanted to get this posted before I forget the details. In particular, I'm lost on the Conjecture mentioned. In a later post, Pat "confirmed" it and ronk was satisfied with Pat's arguments/proof?

However, I just implemented a sets version of the Fish() routine in my general solver, and did not find the conjecture to be true. Maybe I misunderstood what they see as happening. Anyway, here's what I found to be the case:

Code: Select all
`DAJ Note #1: Hidden    contains fin cellsDAJ Note #2: Exclusion contains EE's for unfinned fish and PE's for finned fish`

So, an unfinned fish would have "Hidden" empty ... but not necessarily "Exclusion".
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

daj95376 wrote:
ronk wrote:

Conjecture: If the "hidden set" is empty, then the "exclusion set" is empty also.

I'm lost on the Conjecture mentioned.

---did not find the conjecture to be true. Maybe I misunderstood what they see as happening.

Anyway, here's what I found to be the case:
---an unfinned fish would have "Hidden" empty ... but not necessarily "Exclusion".

in an (un-finned) fish,

If the "hidden set" is empty,---
if the digit is known to not be in the "hidden set"

---then the "exclusion set" is empty also.
then the fish excludes the digit in the "exclusion set"

Pat

Posts: 3676
Joined: 18 July 2005

Pat wrote:_
---then the "exclusion set" is empty also.
then the fish excludes the digit in the "exclusion set"

I never would have guessed that ronk's statement was equivalent to your statement.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: The Ultimate FISH Guide

Same here, I also programmed sets with this style notation but could never get it to work out. That clears the air abit. Instead I developed my own version of sets and post that idea a page back. Its limitations are in the fact I use mutiplication over addition subrtraction which typically runs slower when coded.. perhaps ill recode it and see if I can get the function to work correctly now.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 889
Joined: 05 September 2006

### Re: The Ultimate FISH Guide

I've presented this puzzle previously, but please use the current results for now.

Code: Select all
` +-----------------------+ | . . 2 | 3 . 9 | 1 5 . | | . . . | 2 . . | . . 6 | | 9 . 4 | . . 6 | . . . | |-------+-------+-------| | 2 6 . | 5 . 4 | 3 . . | | . . . | . 2 . | . . . | | 5 . 3 | 1 . . | . . . | |-------+-------+-------| | 3 . . | 4 . . | . 1 5 | | 8 . . | . . . | 6 . . | | . 2 . | . . . | 4 . 3 | +-----------------------+   # P_Set_D:  8 +--------------------------------------------------------------------------------+ |  6       78      2       |  3       478     9       |  1       5       478     | |  17      3       18      |  2       4578    578     |  789     489     6       | |  9       5       4       |  78      1       6       |  278     3       278     | |--------------------------+--------------------------+--------------------------| |  2       6       789     |  5       789     4       |  3       789     1       | |  4       1       789     |  6789    2       3       |  5       6789    789     | |  5       789     3       |  1       6789    78      |  2789    246789  24789   | |--------------------------+--------------------------+--------------------------| |  3       79      679     |  4       6789    2       |  789     1       5       | |  8       4       15      |  79      3       15      |  6       279     279     | |  17      2       1569    |  6789    56789   1578    |  4       789     3       | +--------------------------------------------------------------------------------+ # 86 eliminations remain 7-Fish r1458c16b7\r2c2389b5+r9|c5|b8  <> 7    r9c5 7-Fish r1458c1b27\r2c23489 +r9|c5     <> 7    r9c5 7-Fish r18c167b47\r26c23b39+r9|c5|b8  <> 7    r9c5 7-Fish r18c16b467\r26c2389 +r9|c5|b8  <> 7    r9c5`

While converting my Fish algorithm to use sets, I also generated the one fish combination that was disallowed by my previous Fish algorithm. The distinction seems to be in how cannibalism in r8c4 is treated.

Code: Select all
` 7-Fish r1458c1b27\r2c23489 +      b8  <> 7    r9c5 +-----------------------------------------------+ |   /   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   |   *  **   *   |   .   *   *   | +-----------------------------------------------+`

Code: Select all
` candidate grid -- "x" represents missing vertices from the exemplar ... not uncommon                -- leading to [b8]<>7 (due to cannibalism) if the fish is true                -- forcing at least one of the fin cells to be true +------------------------------------+ |  .  7  x  |  .  #7  .  |  .  x  7  | |  7  .  .  |  x   7  7  |  7  .  .  | |  .  .  .  |  7   .  .  |  7  .  7  | |-----------+------------+-----------| |  .  x  7  |  x  #7  .  |  .  7  x  | |  .  x  7  |  7   .  .  |  .  7  7  | |  .  7  .  |  .   7  7  |  7  7  7  | |-----------+------------+-----------| |  .  7  7  |  .  *7  .  |  7  .  .  | |  .  .  .  | *7   x  x  |  .  7  7  | | #7  x  x  | *7 **7 *7  |  .  7  .  | +------------------------------------+`

I don't remember if this scenario of cannibalism was previously resolved.

Requesting opinions on the acceptability of using this fish for this grid?
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

ronk wrote:
Code: Select all
`Sets:  Base (size N):   B  = B1 + B2 ... + BN  Base Intersect:  BI = B1*B2 + B1*B3 ... + B1*BN + B2*B3 ... + (BN-1)*BN  Cover (size N):  C  = C1 + C2 ... + CN  Cover Intersect: CI = C1*C2 + C1*C3 ... + C1*CN + C2*C3 ... + (CN-1)*CN  Hidden:          H  = (B \ C) + BI  Exclusion:       E  = (C \ B) + CISymbol Key:    Bn    <=> units (sectors) of the base set    Cn    <=> units (sectors) of the cover set    '+'   <=> union operator ('|' in C++)    '*'   <=> intersection operator ('&' in C++)    '\'   <=> difference operator (substraction) ("X & ~Y" in C++)  "(...)" <=> operator precedence`

FWIW: My opinion on what's missing from the above.

Code: Select all
`DAJ Note #1: Hidden      contains fin cellsDAJ Note #2: Exclusion   contains EE's for unfinned fish and PE's for finned fish`

Code: Select all
`Let P[J] be the peers of the J'th fin cell in Hidden.EE = Exclusion * P[1] * P[2] ... P[m]   (where Hidden has "m" fin cells)When Hidden is empty, then we get:EE = Exclusion`
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### re: "finned fish"

daj95376 wrote:

Let P[J] be the peers of the J'th fin-cell in Hidden.

EE = Exclusion * P[1] * P[2] ... P[m] (where Hidden has "m" fin cells)

yes, the "finned fish" is
merely shorthand for a "forcing net"

• case the digit is in fin-cell 1
exclude P(1)
• case the digit is in fin-cell 2
exclude P(2)
...
• otherwise
the (un-finned) fish exists

Pat

Posts: 3676
Joined: 18 July 2005

### re: "finned fish" of order 7

daj95376 wrote:
While converting my Fish algorithm to use sets, I also generated the one fish combination that was disallowed by my previous Fish algorithm. The distinction seems to be in how cannibalism in r8c4 is treated.

Code: Select all
` 7-Fish r1458c1b27\r2c23489 +      b8  <> 7    r9c5 +-----------------------------------------------+ |   /   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 don't remember if this scenario of cannibalism was previously resolved.

Requesting opinions on the acceptability of using this fish for this grid?

looks good

"vertices" may be convenient
but are not part of the fish logic

Pat

Posts: 3676
Joined: 18 July 2005

### Re:

ronk wrote:
Code: Select all
`Hidden:          H  = (B \ C) + BIExclusion:       E  = (C \ B) + CISymbol Key:    Bn    <=> units (sectors) of the base set    Cn    <=> units (sectors) of the cover set    '+'   <=> union operator ('|' in C++)    '*'   <=> intersection operator ('&' in C++)    '\'   <=> difference operator (substraction) ("X & ~Y" in C++)  "(...)" <=> operator precedence`

I'm sure this has been already mentioned but as you remeber a fin cell has to be in more base sectors than cover sectors & potential elimination cells should be in more cover sectors than base sectors so if there a situation where BI * CI > 0 then you might run into problems if programming didn't take this into account!!

tarek

Posts: 2761
Joined: 05 January 2006

### Re: Re:

[Withdrawn: Someone forgot to tell me that we were talking about Sudoku variants.]
Last edited by daj95376 on Sun Jul 28, 2013 10:00 pm, edited 1 time in total.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

### Re: The Ultimate FISH Guide

In vanilla sudoku you have a maximum of three sectors passing through a cell. So there will be no CI*BI, So this situation shouldn't be of concern. When talking about sudoku variants then this should be considered.

When the fish concept is extended (multi digit or multi cell) then there is a possibility of a CI*BI

tarek

Posts: 2761
Joined: 05 January 2006

### Re: Re:

daj95376 wrote:[Withdrawn: Someone forgot to tell me that we were talking about Sudoku variants.]

Would that someone be me
I didn't mean to distract because I think it has applications in multi fish and extended fish concepts

tarek

Posts: 2761
Joined: 05 January 2006

tarek wrote:
daj95376 wrote:[Withdrawn: Someone forgot to tell me that we were talking about Sudoku variants.]

Would that someone be me
I didn't mean to distract because I think it has applications in multi fish and extended fish concepts

Actually, you don't need to depart into Sudoku variants or multi-fish to find an acceptable scenario for BI * CI > 0. It'll be true in vanilla Sudoku if you expand your perspective from NxN Fish to Nx(N+k) Fish.

For Nx(N+k) Fish, the following constraints are present from Obi-Wahn's arithmetic:

Code: Select all
`( B  * C  ) = B( BI * CI ) = BI`

This means that my 7x7-Fish above would need to be expressed as:

Code: Select all
`7x11-Fish r1458c1b27\r2c23489b8 + r99 + c55  =>  r9c5<>7`

... because r9c1 is in base sectors c1b7, and r1c5 is in base sectors r1b2. From Obi-Wahn's arithmetic, we need to add [r9] twice to the cover set in order to cancel r9c1. Similarly for adding [c5] twice to cancel r1c5.

Note: r4c5 in the base set, but resolved during the addition of additional cover sectors for r1c5.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

same house twice in the cover?
can't comment (this gets us into the area where i gave up on his arithmetic)

however, your puzzle should only need 7\8

r1458c1b27\r29c234589
to exclude r9c5

Pat

Posts: 3676
Joined: 18 July 2005

PreviousNext