The Ultimate FISH Guide

Advanced methods and approaches for solving Sudoku puzzles

Re: The Ultimate FISH Guide

Postby ronk » Thu Jun 27, 2013 4:47 pm

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

Postby daj95376 » Thu Jul 18, 2013 7:37 pm

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) + CI

Symbol 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 cells
DAJ 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

Postby Pat » Fri Jul 19, 2013 6:18 am

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,---
      read as:
        if the digit is known to not be in the "hidden set"

        ---then the "exclusion set" is empty also.
      read as:
        then the fish excludes the digit in the "exclusion set"
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Postby daj95376 » Fri Jul 19, 2013 3:54 pm

Pat wrote:_
    ---then the "exclusion set" is empty also.
read as:
    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

Postby StrmCkr » Sat Jul 20, 2013 5:16 am

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.
User avatar
StrmCkr
 
Posts: 625
Joined: 05 September 2006

Re: The Ultimate FISH Guide

Postby daj95376 » Sun Jul 21, 2013 4:19 pm

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

Postby daj95376 » Tue Jul 23, 2013 10:45 pm

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) + CI

Symbol 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 cells

DAJ 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"

Postby Pat » Wed Jul 24, 2013 2:27 pm

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
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

re: "finned fish" of order 7

Postby Pat » Wed Jul 24, 2013 2:35 pm

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
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Re:

Postby tarek » Fri Jul 26, 2013 11:28 pm

ronk wrote:
Code: Select all
Hidden:          H  = (B \ C) + BI
Exclusion:       E  = (C \ B) + CI

Symbol 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!!
User avatar
tarek
 
Posts: 2608
Joined: 05 January 2006

Re: Re:

Postby daj95376 » Sun Jul 28, 2013 9:36 pm

[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

Postby tarek » Sun Jul 28, 2013 9:51 pm

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
User avatar
tarek
 
Posts: 2608
Joined: 05 January 2006

Re: Re:

Postby tarek » Sun Jul 28, 2013 10:22 pm

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 :oops:
User avatar
tarek
 
Posts: 2608
Joined: 05 January 2006

Postby daj95376 » Tue Jul 30, 2013 11:26 pm

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 :oops:

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

Postby Pat » Thu Aug 01, 2013 2:11 pm


    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
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

PreviousNext

Return to Advanced solving techniques