The New Sudoku Players' Forum

[ronk]

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.

[daj95376]

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

[Pat]

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"

[daj95376]

_

---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.

[StrmCkr]

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.

[daj95376]

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]

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


[Pat]

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]

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

[tarek]

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!!

[daj95376]

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

[tarek]

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]

[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

[daj95376]

[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.

[Pat]

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