Big fish

Advanced methods and approaches for solving Sudoku puzzles

Postby ravel » Mon Mar 13, 2006 6:07 pm

aeb wrote:It follows that there is never the need to search for N-fish with N > 4
But it helps to find bugs:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby tarek » Mon Mar 13, 2006 6:11 pm

The example which you showed aeb has finned swordfish as you said, I've already demonstrated that.

what about this one
Code: Select all
 1358   7      138    |  2      6      4      |  35     389    389   
 2      9     *4      |  3     *5     *78     | *6     *78     1     
 3568   68    *368    |  1     *78    *9      | *357   *4      2     
----------------------+-----------------------+-----------------------
-379    5     *2      |  6     *789   *78     | *1     *37     4     
 3678   68    #3678   |  4      1      2      |  9      5      367   
 4      1     #679    |  79     3      5      |  8      2      67   
----------------------+-----------------------+-----------------------
 6789   2     *678    |  5     *79    *36     | *4     *1      389   
 16789  4     *16789  |  89    *2     *36     | *37    *3789   5     
 89     3      5      |  789    4      1      |  2      6      789


This has 2 fins, The inverse will lead to the fins being vertices restricting elimination to cell r4c3, if it was a single fin it would have worked & we would have the finned swordfish with the exact elimination....
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby ravel » Mon Mar 13, 2006 6:15 pm

As i said above, this is a problem of the definition of a finned swordfish. aeb's conclusion is correct. Maybe the finned swordfish definition has to be extended.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby aeb » Mon Mar 13, 2006 6:52 pm

tarek wrote:The example which you showed aeb has finned swordfish as you said, I've already demonstrated that.

what about this one
Code: Select all
 1358   7      138    |  2      6      4      |  35     389    389   
 2      9     *4      |  3     *5     *78     | *6     *78     1     
 3568   68    *368    |  1     *78    *9      | *357   *4      2     
----------------------+-----------------------+-----------------------
-379    5     *2      |  6     *789   *78     | *1     *37     4     
 3678   68    #3678   |  4      1      2      |  9      5      367   
 4      1     #679    |  79     3      5      |  8      2      67   
----------------------+-----------------------+-----------------------
 6789   2     *678    |  5     *79    *36     | *4     *1      389   
 16789  4     *16789  |  89    *2     *36     | *37    *3789   5     
 89     3      5      |  789    4      1      |  2      6      789


This has 2 fins, The inverse will lead to the fins being vertices restricting elimination to cell r4c3, if it was a single fin it would have worked & we would have the finned swordfish with the exact elimination....

Well, let us just repeat the proof. All 7s in columns 35678 are in rows 23478 with the possible exception of cells (5,3), (6,3). Now (4,1)7 kills both exceptions and also row 4, contradiction: five 7s cannot be in four rows.
Now stop looking at the picture and apply logic only. Entirely equivalent to the sentences above is: All 7s in rows 1569 are in columns 1249 with the possible exception of cells (5,3), (6,3). Now (4,1)7 kills both exceptions and also column 1, contradiction: four 7s cannot be in three columns.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby vidarino » Mon Mar 13, 2006 6:54 pm

tarek wrote:...

This has 2 fins, The inverse will lead to the fins being vertices restricting elimination to cell r4c3, if it was a single fin it would have worked & we would have the finned swordfish with the exact elimination....


Spot on!:)

I have just completed running my solver on a few thousand puzzles, it now only finds high-order fish (Squirmbag and up) with 2 fin cells. In other words, all the one-finned big fish have a lower order companion that is found instead.

They're pretty rare, though. Of the 12486 puzzles I ran it on, 53 (0.42%) were found to have a Finned Squirmbag, and 4 (0.03%) had a Finned Whale (N=6). (The puzzles are all rated pretty high, though, which might skew the results.)

So, with the current rules for finned fish, I am now fairly convinced that there *are* big two-finned fish that don't have an easily identified smaller counterpart. Perhaps the rules can be extended to cover these cases, but for now, I'm content.:)

And I do realize that there are logical shortcuts that can perform the same eliminations. My quest, however, was to show that there aren't any smaller finned fishes that do it, as is the case with the unfinned ones.

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby vidarino » Mon Mar 13, 2006 7:10 pm

Hmm, this discussion got me thinking...

Here's the alternative almost-swordfish aeb points out:
Code: Select all
 .  7  .  |  .  .  .  |  .  .  .
 .  .  .  |  .  .  7  |  .  7  .
 .  .  .  |  .  7  .  |  7  .  .
----------+-----------+----------
 *  .  .  |  .  7  7  |  .  7  .
 #  .  X  |  .  .  .  |  .  .  X
 .  .  X  |  X  .  .  |  .  .  X
----------+-----------+----------
 7  .  7  |  .  7  .  |  .  .  .
 7  .  7  |  .  .  .  |  7  7  .
 .  .  .  |  X  .  .  |  .  .  X

(X=fish cell, #=fin, *=elimination in question)


Wild speculation; Since the row that hosts the fin cell(s) would be a conjugate pair if the fins weren't present, you can actually eliminate the candidate from the entire box containing the fins (except the participating cells)?

(Edit: Nah, doesn't seem to work... Needs more tinkering...)

Vidar
Last edited by vidarino on Mon Mar 13, 2006 4:01 pm, edited 1 time in total.
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby ronk » Mon Mar 13, 2006 7:56 pm

tarek wrote:
Code: Select all
 1358   7      138    |  2      6      4      |  35     389    389   
 2      9     *4      |  3     *5     *78     | *6     *78     1     
 3568   68    *368    |  1     *78    *9      | *357   *4      2     
----------------------+-----------------------+-----------------------
-379    5     *2      |  6     *789   *78     | *1     *37     4     
 3678   68    #3678   |  4      1      2      |  9      5      367   
 4      1     #679    |  79     3      5      |  8      2      67   
----------------------+-----------------------+-----------------------
 6789   2     *678    |  5     *79    *36     | *4     *1      389   
 16789  4     *16789  |  89    *2     *36     | *37    *3789   5     
 89     3      5      |  789    4      1      |  2      6      789

That example has a continuous x-cycle of length 6 ... which also eliminates r4c1.
Code: Select all
 . . . |  . . . |  . . .
 . . . |  . . 7 |  . 7 .
 . . . |  . 7 . |  7 . .
-------+--------+--------
 7 . . |  . A A |  . a .
 7 . 7 |  . / . |  . \ A
 . . 7 |  a . . |  . . A
-------+--|-----+------|-
 7 . 7 |  | 7 . |  . . |
 7 . 7 |  | . . |  7 7 |
 . . . |  A----------- a

Note that 5 links are strong links. The nodes of the x-cycle are colored to show that simple grouped coloring also could be used.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby aeb » Mon Mar 13, 2006 8:07 pm

vidarino wrote:Hmm, this discussion got me thinking...

Here's the alternative almost-swordfish aeb points out:
Code: Select all
 .  7  .  |  .  .  .  |  .  .  .
 .  .  .  |  .  .  7  |  .  7  .
 .  .  .  |  .  7  .  |  7  .  .
----------+-----------+----------
 *  .  .  |  .  7  7  |  .  7  .
 #  .  X  |  .  .  .  |  .  .  X
 .  .  X  |  X  .  .  |  .  .  X
----------+-----------+----------
 7  .  7  |  .  7  .  |  .  .  .
 7  .  7  |  .  .  .  |  7  7  .
 .  .  .  |  X  .  .  |  .  .  X

(X=fish cell, #=fin, *=elimination in question)


Not precisely - it is
Code: Select all
 .  7  .  |  .  .  .  |  .  .  .
 .  .  .  |  .  .  7  |  .  7  .
 .  .  .  |  .  7  .  |  7  .  .
----------+-----------+----------
 *  .  .  |  .  7  7  |  .  7  .
 X  .  #  |  .  .  .  |  .  .  X
 .  .  #  |  X  .  .  |  .  .  X
----------+-----------+----------
 7  .  7  |  .  7  .  |  .  .  .
 7  .  7  |  .  .  .  |  7  7  .
 .  .  .  |  X  .  .  |  .  .  X

(A big finned fish and the complementary small finned fish have the same fin.)

vidarino wrote:Wild speculation; Since the row that hosts the fin cell(s) would be a conjugate pair if the fins weren't present, you can actually eliminate the candidate from the entire box containing the fins (except the participating cells)?

Why start wild speculation when the situation is absolutely clear? We have a counting argument. The three digits 7 found in rows 569 cannot be in columns 49. So (4,1)!7.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby tarek » Mon Mar 13, 2006 9:11 pm

You're right aeb, it is a smaller fish........

It is a finned swordfish...........

There nothing wrong with the definition of finned fish...

The problem with this pattern is that is that I've never seen it before, slipped away completely, as long as you have a The fin in the line of other vertices it would still apply.........

This would mean that we may have a maximum of 6 cells (between vertices & fins) per box....

up until now, I have been using a maximum of 3 cells (between vertices & fins) per box........

I think that this thread had added to my info about these fish, & has definitely benifited me as a programmer.

As aeb demonstrated this is the smaller fish with all vertices activated.... this to me would slip through the net every time, I#'m glad we caught it in time.....

Code: Select all
 .  7  .  |  .  .  .  |  .  .  .
 .  .  .  |  .  .  7  |  .  7  .
 .  .  .  |  .  7  .  |  7  .  .
----------+-----------+----------
 *  .  .  |  .  7  7  |  .  7  .
 X  .  #  | [X] .  .  |  .  .  X
[X] .  #  |  X  .  .  |  .  .  X
----------+-----------+----------
 7  .  7  |  .  7  .  |  .  .  .
 7  .  7  |  .  .  .  |  7  7  .
[X] .  .  |  X  .  .  |  .  .  X

Only the vertices with fins can eliminate & only within the box...

I think we need that diagram now ronk:D as we should be talking now not just about 2 dorsal fins only, but about dorsal & ventral fins as well (i think):D

Tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby vidarino » Mon Mar 13, 2006 9:43 pm

Indeed. I stand corrected and quite a bit more informed on the intricacies of life in the sea...:)

What my solver (and apparently tarek's, too) was blissfully unaware of was the fact that fin cells can not only occur in one of the rows, but several of them, as long as they are confined to one box. (I.e. in this example, the swordfish lies in the rows, and the fin straddles two of them. Traditionally, the fin cells lie only in one row.)

(Don't ask me why I imposed such a limit on myself. I'm still not sure what I was thinking...:) )

With this new(?) variant, I'm finally fairly convinced that all big fish, finned or not, will have a smaller counterpart. This is exactly the scenario I was certain did *not* have such a counterpart, because I wasn't aware of the cross-row fin possibility.

Oh, and by the way:
Code: Select all
 .  7  .  |  .  .  .  |  .  .  .
 .  .  .  |  .  .  7  |  .  7  .
 .  .  .  |  .  7  .  |  7  .  .
----------+-----------+----------
 *  .  .  |  .  7  7  |  .  7  .
 X  .  #  |  .  .  .  |  .  .  X
 .  .  #  |  X  .  .  |  .  .  X
----------+-----------+----------
 7  .  7  |  .  7  .  |  .  .  .
 7  .  7  |  .  .  .  |  7  7  .
 .  .  .  |  X  .  .  |  .  .  X


I'm still not 100% ready to call this a plain Finned Swordfish, though, since it has only one cell in column 1. Is it perhaps a Finned Sashimi Swordfish? But I'll let that lie for now.:)

Anyway, thanks for your input, all. Off to tune some code... ;-)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Mike Barker » Tue Mar 14, 2006 3:09 am

Seems like lots of fish tails or is that fish tales? Can one of you tell me if this finned squirmbag suffers from the same problems? I assume there is something wrong because based on the above discussion it doesn't seem like it should exist.

3.1...64.6.49.35.7.5.64...34.586.1...6.3.24....84.....5.67843...7..36.54.43......
Code: Select all
+-----------------+------------------+------------------+
|     3 *289    1 |   25    27   578 |    6     4  *289 |
|     6   28    4 |    9    12     3 |    5   128     7 |
|   279    5  279 |    6     4    18 |  289  1289     3 |
+-----------------+------------------+------------------+
|     4 *239    5 |    8     6   *79 |    1    37   *29 |
|  *179    6  *79 |    3 *1579     2 |    4  *789  *589 |
|  1279 -1239   8 |    4  1579  1579 |  279   367  2569 |
+-----------------+------------------+------------------+
|     5 *129    6 |    7     8     4 |    3   *29  *129 |
|  1289    7   29 |   12     3     6 |  289     5     4 |
|   128    4    3 |  125  *259   *59 |  278  2678   168 |
+-----------------+------------------+------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby re'born » Tue Mar 14, 2006 5:10 am

Mike,

There is a finned swordfish in ([368], [137]) with fins at (5,1) and (5,3). This implies (6,2)!9.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ronk » Tue Mar 14, 2006 6:38 am

vidarino wrote:What my solver (and apparently tarek's, too) was blissfully unaware of was the fact that fin cells can not only occur in one of the rows, but several of them, as long as they are confined to one box.

Fin cells occur in at most two rows. If the "several" rows were three rows, there would not be a cell from which to make an elimination.

vidarino wrote:(I.e. in this example, the swordfish lies in the rows, and the fin straddles two of them. Traditionally, the fin cells lie only in one row.)

Myth Jellies illustrated a theoretical four-celled fin in late Jan, so I think he would consider such a fin uncommon, rather than non-traditional. (I'm surprised he hasn't posted on this thread.)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Tue Mar 14, 2006 9:10 am

:)First chance that I've seen the thread. Looked like fun...sorry I missed it!
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Havard » Tue Mar 14, 2006 12:09 pm

I have to see if I can sum this thing up for myself. Please correct me if I am wrong!:)

The whole "finned" approach, comes from this fact:
Code: Select all
. . . | . . . | c . .
. . . | . A . | c * *
. . . | . | . | c . .
------+---|---+-|----
. . . | . | . | | . .
. . . | . B . | D . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
A-B is a strong link
D-ccc is a grouped strong link, where it does not matter how many "c"'s there actually are.
* is the elimination that can be done


Now this can be extended to three links with this general pattern (finned swordfish):
Code: Select all
. . . | . . . | x . .
. X . | . X . | x * *
. | . | . | . | x . .
--|---+---|---+-|----
. | . | . | . | | . .
. X . | . X . | X . .
. | . | . | . | | . .
--|---+---|---+-|----
. | . | . | . | | . .
. | . | . | . | | . .
. X . | . X . | X . .


Now the beautiful thing about this is that you can actually take out one X from each link, and it will still hold true!
Code: Select all
. . . | . . . | x . .
.(X). | . X . | x * *
. | . | . | . | x . .
--|---+---|---+-|----
. | . | . | . | | . .
. X . | .(X). | X . .
. | . | . | . | | . .
--|---+---|---+-|----
. | . | . | . | | . .
. | . | . | . | | . .
. X . | . X . |(X). .

(notice that if you took out two X's in the same row, it would still hold true, but it would become an elimination due to an X-wing instead)

The small x's you can have as many or as little as you want of...

Now, if you have two grouped strong links in the same box, you will get:
Code: Select all
. . . | . . . | a c *
. . . | . . . | a c *
. . . | . . . | a c *
------+-------+-|-|--
. . . | . . . | | | *
* * * | * * * | B D *
. . . | . . . | . . *
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
again, it does not matter how many of the "a"'s and "c"'s that are actually candidates!


but now when applying this to a three link system, while the same rules applies for how you not need all three X's in each link, you will have two different outcomes depending on wether the X in the link that can "see" the two x-groups exists or not:

not existing:
Code: Select all
. . . | . . . | x x *
. . . | .(X). | x x *
. . . | . | . | x x *
------+---|---+-|-|--
. . . | . | . | | | .
* * * | * X * | X X *
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
* * * | * X * | X X *

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


so that in the example given in this thread, you could actually have more candidates present (in theory), and do more eliminations, like this:
Code: Select all
 .  .  .  |  *  .  .  |  .  .  *
 .  .  .  |  *  .  .  |  .  .  *
 .  .  .  |  *  .  .  |  .  .  *
----------+-----------+----------
 *  *  *  |  *  .  .  |  .  .  *
 X  #  #  | [X] .  .  |  .  .  X
[X] #  #  |  X  .  .  |  .  .  X
----------+-----------+----------
 .  .  .  |  *  .  .  |  .  .  *
 .  .  .  |  *  .  .  |  .  .  *
[X] .  .  |  X  .  .  |  .  .  X


because the X in R9C1 is NOT existing.

Havard
Last edited by Havard on Tue Mar 14, 2006 8:32 am, edited 1 time in total.
Havard
 
Posts: 377
Joined: 25 December 2005

PreviousNext

Return to Advanced solving techniques