Big fish

Advanced methods and approaches for solving Sudoku puzzles

Postby Havard » Thu May 11, 2006 12:01 am

Hi guys!

Those fishes I posted are a result of my "all-purpose-fishing-tool", which I am testing at the moment. There still are a bit of stuff to be sorted out (like why he spots a cannibalistic jellyfish instead of a finned swordfish like you Mike have correctly pointed out twice now...), but as soon as I think it is ready, I will post the whole thing here!:)

It is maybe more of an algorithm than a technique, but I am sure it will be of some interest to at least two or three people!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Mike Barker » Fri May 12, 2006 1:42 pm

Havard, I've updated the summary of big fish/frankenfish here. Could you verify its complete and correct. Also what was the original Frankenfish?

Everything I've read says the Squirmbags are supposed to be extinct, but having updated my solver for Frankenfish and using your fishy puzzle:
Code: Select all
..36...97
1...9.623
69.2731.5
3.6...7.9
.5..39.6.
4.9..63..
931..8.76
74.36.9..
.6.9.7.3.

I get a finned X-wing, 2 finned swordfish, a Franken Jellyfish, and, I guess I've got to believe it because my eyes have seen it, a Franken Squirmbag!
Code: Select all
Locked Column: r46c8 => r8c8<>5
Locked Column Box: r19c5|r18c6 => r4c5<>1,r6c5<>1,r4c6<>1
Row X-Wing Fillet-o-Fish: r2c346|r8c36 => r1c6<>5
Column Swordfish Fillet-o-Fish: r159c17|r146c5 => r5c4<>8
Column Swordfish Fillet-o-Fish: r23c3|r124c6|r34c8 => r2c4<>4
Row Franken Jellyfish: r3c38|r59c1379|r8c389 => r4c8<>8,r6c8<>8
Column Franken Squirmbag: r159c17|r1246c2|r246c4|r146c5 => r5c3<>8

I guess its back to the drawing board for those who claim there is a smaller fish or I've still got more work to do on my solver. Does this mean Vidar's whale may still be lurking out there somewhere?
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Fri May 12, 2006 6:09 pm

Mike Barker wrote:Column Franken Squirmbag:
(...)
r159c17|r1246c2|r246c4|r146c5 => r5c3<>8
(...)
I guess its back to the drawing board for those who claim there is a smaller fish or I've still got more work to do on my solver.

Might be the latter. Most of those cells are not required for the deduction. Though the technique may be valid, are any human solvers able to find it? Or when the deduction of a programmed solver, can you even explain it?

On the other hand, consider the following:
Code: Select all
 8  8  .  | .  8  .  | 8  .  . 
 .  8  8  | 8  .  .  | .  .  . 
 .  . #8  | .  .  .  | . #8  . 
----------+----------+---------
 .  8  .  | 8  8  .  | .  .  . 
 8  . -8  | .  .  .  |*8  . *8 
 .  8  .  | 8  8  .  | .  . *8 
----------+----------+---------
 .  .  .  | .  .  8  | .  .  . 
 .  . *8  | .  .  .  | . #8 *8 
*8  . *8  | .  .  .  |*8  . *8 

If r8c8<>8, there is a grouped conjugate chain (ERs) in boxes 6, 9, and 7 for r5c3<>8.
If r8c8=8, there is a simple conjugate chain in col 8 and row 3 for r5c3<>8
Either way, r5c3<>8
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Fri May 12, 2006 7:21 pm

I agree. In fact I previously posted a VWXYZ-wing which also does the job
Code: Select all
+------------------+------------------+------------------+
|  258    28     3 |     6  1458   14 |    48    9     7 |
|    1    78  4578 |    58     9   45 |     6    2     3 |
|    6     9    48 |     2     7    3 |     1   48     5 |
+------------------+------------------+------------------+
|    3   128     6 |  1458  2458  245 |     7 *145     9 |
|  #28     5  -278 |   147     3    9 |  *248    6 *1248 |
|    4  1278     9 |  1578   258    6 |     3  *15   128 |
+------------------+------------------+------------------+
|    9     3     1 |    45   245    8 |   245    7     6 |
|    7     4   258 |     3     6  125 |     9   18   128 |
|  258     6   258 |     9  1245    7 |  2458    3  1248 |
+------------------+------------------+------------------+

and you're right, I doubt a human solver (except maybe Carcul, RW and a few others) could find the Squirmbag. What I'm specifically interested in here is the question of the existance of a squirmbag or higher order fish. They are not supposed to exist if the 9-N-P argument is true. I interpret that to mean than given a squirmbag, a jellyfish or something smaller should also do the same job. I happily programmed up my solver expecting to debunk Havard's squirmbag and failed.

This of course begs the question of what is a fish. I'm inclined to define them as an almost constraint subset with the "A" set consisting of N rows or columns. I think you've shown that most of fish we've encountered fit this bill. I'm not sure what might be excluded except maybe your latest puzzle with the box in the "A" set. This may also answer your question - its not a Frankenfish.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Fri May 12, 2006 8:28 pm

Mike Barker wrote:What I'm specifically interested in here is the question of the existance of a squirmbag or higher order fish. They are not supposed to exist if the 9-N-P argument is true. I interpret that to mean than given a squirmbag, a jellyfish or something smaller should also do the same job.

That rule was developed for standard N-fish. While I believe it also holds for single-finned fish, the rule for these complex creatures-of-the-deep could easily be different.

Mike Barker wrote:This of course begs the question of what is a fish. I'm inclined to define them as an almost constraint subset with the "A" set consisting of N rows or columns. I think you've shown that most of fish we've encountered fit this bill.

I wish I understood why they don't all "fit this bill."
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Steve R » Sun May 21, 2006 6:41 pm

Mike

I am not sure that you published the grid exactly as it was when you found the 5-fish so what follows is guesswork.

If you can retrieve the grid position, it might be worth checking for a 4-fish based on rows 3, 5, 8, and 9, boxes 8 and 9. Its target columns are 1, 3 and 8. If you find the fish, it should eliminate 8 from r46c8.

My knowledge of these things is limited to Myth Jellies’ note of 19 March. The note is a paradigm but it may be just one step short of being comprehensive in covering fish with two fins in two different boxes.

The pattern I have is mind (not adjusted to fit your specific puzzle) is this:
Code: Select all
 .   .   . | .   .   . | .   .   .
 X   .   . | .   X   . | .   X   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   -   .
 X   .   . | .   X   . | X   .   X
 .   .   . | .   .   . | .   -   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 X   .   . | .   X   . | X   X   X
 X   .   . | .   X   . | X   X   X



I expect it has been discussed in this long thread but wonder if your computer missed it.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby ronk » Sun May 21, 2006 7:44 pm

Steve R wrote:The pattern I have is mind (not adjusted to fit your specific puzzle) is this:
Code: Select all
 .   .   . | .   .   . | .   .   .
 X   .   . | .   X   . | .   X   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   -   .
 X   .   . | .   X   . | X   .   X
 .   .   . | .   .   . | .   -   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   -   .
 X   .   . | .   X   . | X   X   X
 X   .   . | .   X   . | X   X   X

As added above, this pattern also has the exclusion r7c8<>X.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Sun May 21, 2006 10:46 pm

The pattern you describe is basically the same as the Franken Jellyfish which my solver reported:
    Row Franken Jellyfish: r3c38|r59c1379|r8c389 => r4c8<>8,r6c8<>8
This type of reduction is summarized here. At this point my PM look like:
Code: Select all
+------------------+------------------+------------------+
|  258    28     3 |     6  1458   14 |    48    9     7 |
|    1    78  4578 |    58     9   45 |     6    2     3 |
|    6     9   *48 |     2     7    3 |     1  *48     5 |
+------------------+------------------+------------------+
|    3   128     6 |  1458  2458  245 |     7 -1458    9 |
|  *28     5  *278 |   147     3    9 |  *248    6 *1248 |
|    4  1278     9 |  1578   258    6 |     3  -158  128 |
+------------------+------------------+------------------+
|    9     3     1 |    45   245    8 |   245    7     6 |
|    7     4  *258 |     3     6  125 |     9  *18  *128 |
| *258     6  *258 |     9  1245    7 | *2458    3 *1248 |
+------------------+------------------+------------------+

The next step after this is the Squirmbag:
    Column Franken Squirmbag: r159c17|r1246c2|r246c4|r146c5 => r5c3<>8
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Havard » Mon May 22, 2006 9:20 am

Just to keep stirring things up a bit...:D

Code: Select all
Cannibalistic Franken-Whale in columns: 3 4 5 6 7 9
19     159    37     | 1368X  1578X  4      | 2      356789 1358X
8      125    37     | 1236X  1257X  9      | 1346X  3567   1345X
129    6      4      | 1238X  1578X  178X   | 1389X  35789  1358X
---------------------+----------------------+---------------------
3      4      128X   | 7      1268X  5      | 168X   268    9
5      7      128X   | 9      4      16X-   | 1368X  2368   138X
129    289    6      | 128X   128X   3      | 5      4      7
---------------------+----------------------+---------------------
4      18     9      | 5      368    168X   | 7      38     2
6      3      128X   | 18X    1789X  278    | 489    589    458
7      28     5      | 4      39     28     | 39     1      6

1   1   .   | 1X  1X  .   | .   .   1X
.   1   .   | 1X  1X  .   | 1X  .   1X
1   .   .   | 1X  1X  1X  | 1X  .   1X
------------+-------------+------------
.   .   1X  | .   1X  .   | 1X  .   .
.   .   1X  | .   .   1X- | 1X  .   1X
1   .   .   | 1X  1X  .   | .   .   .
------------+-------------+------------
.   1   .   | .   .   1X  | .   .   .
.   .   1X  | 1X  1X  .   | .   .   .
.   .   .   | .   .   .   | .   1   .


Found him in nr. 1313 (hmm... could this be some sort of sign to leave him alone...?) of the top1465.

Code: Select all
.....42..8....9....64......3..7.5..957.........6..3.4...95..7.2.3.......7..4...16


Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Mon May 22, 2006 5:31 pm

Havard wrote:Just to keep stirring things up a bit...:D

Code: Select all
Cannibalistic Franken-Whale in columns: 3 4 5 6 7 9
(...)
1   1   .   | 1X  1X  .   | .   .   1X
.   1   .   | 1X  1X  .   | 1X  .   1X
1   .   .   | 1X  1X  1X  | 1X  .   1X
------------+-------------+------------
.   .   1X  | .   1X  .   | 1X  .   .
.   .   1X  | .   .   1X- | 1X  .   1X
1   .   .   | 1X  1X  .   | .   .   .
------------+-------------+------------
.   1   .   | .   .   1X  | .   .   .
.   .   1X  | 1X  1X  .   | .   .   .
.   .   .   | .   .   .   | .   1   .

Simple (single chain) grouped coloring -- of ER in b4 and conjugate links in r7, b7, c3 and r6 -- does the same.:D
Code: Select all
 1  1  .  |  1  1  .  |  .  .  1     
 .  1  .  |  1  1  .  |  1  .  1     
 1  .  .  |  1  1  1  |  1  .  1     
----------+-----------+----------
 .  .  A  |  .  1  .  |  1  .  .
 .  .  A  |  .  . *1  |  1  .  1   
 a  .  .  |  A  A  .  |  .  .  .
----------+-----------+----------
 .  A  .  |  .  .  a  |  .  .  .
 .  .  a  |  1  1  .  |  .  .  .   
 .  .  .  |  .  .  .  |  .  1  .

 r5c6-1-r7c6=1=r7c2-1-r8c3=1=r45c3-1-r6c1=1=r6c45-1-r5c6, implying r5c6<>1

If you must use something more sophisticated, consider the following:
Code: Select all
 .  .  -  |  .  .  .  |  .  .  .
 .  .  -  |  .  .  .  |  .  .  .
 .  .  -  |  .  .  .  |  .  .  .
----------+-----------+----------
 *  *  X  |  *  *  *  |  .  .  .
 *  *  X  |  *  *  *  |  .  .  .
 X  X  -  |  X  X  X  |  -  -  -
----------+-----------+----------
 X  X  -  |  -  -  #  |  -  -  -
 *  * *X  |  X  X  X  |  *  *  *
 *  *  X  |  -  -  -  |  .  .  .

Either r7c6=1 is ultimately false, or it's true. If false, the 1s candidates in r6, r7, c3, and b8 are covered by b4, b5, b7, and r8 ... yielding exclusions r4c5<>1, r5c6<>1, and r8c3<>1. If true, exclusion r5c6<>1 still occurs.

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

Postby Mike Barker » Tue May 23, 2006 1:43 am

If it looks like a whale and acts like a whale ...

In my book, if a pattern meets the definition of a fish and is not composed of smaller fish then its a real fish. My working definition of a fish is an almost constrained subset with set A consisting of N rows or N columns. In this case the A set is columns 3, 4, 5, 6, 7, and 9. The B set consists of boxes 2, 3, and 5 and rows 4, 5, and 8. This makes the fin r7c6. If r7c6 is true then all other candidates in column 6 can be eliminated. If it is false then the other candidates of the fish form the constrained subset which because rows 4 and 5 intersect box 5 allows, in addition to all others, elimination of candidates in r45c6. So it appears to be a valid fish, although its interesting that the elimination is in a different box than the fin.

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


I've run the pm through my solver and wasn't able to find a smaller fish. That doesn't mean they don't exist for its seems new species continue to be found and I'm sure my solver has bugs in it, but for now it looks to be a whole fish. So after 189 posts, several advances in fish finding and a lot of false starts it looks like Vidar has been justified with Havard's find and in the immortal words of Scotty, "Captain, there be whales here!"
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Tue May 23, 2006 2:46 am

Mike Barker wrote:In this case the A set is columns 3, 4, 5, 6, 7, and 9. The B set consists of boxes 2, 3, and 5 and rows 4, 5, and 8. This makes the fin r7c6. If r7c6 is true then all other candidates in column 6 can be eliminated. If it is false then the other candidates of the fish form the constrained subset which because rows 4 and 5 intersect box 5 allows, in addition to all others, elimination of candidates in r45c6.

Nice description, which sounds vaguely familiar.:)

Mike Barker wrote:My working definition of a fish is an almost constrained subset with set A consisting of N rows or N columns.

Constraint sets come in complementary pairs. Sets A and B of one puzzle may be sets B and A, respectively, in another puzzle. IOW if boxes are allowed in set B, it only makes sense they also be allowed in set A.

With a mix of rows, columns, and boxes allowed in both sets A and B, I now again believe the maximum N required for a 9x9 sudoku is four. Therefore, while creatures larger than the finned jellyfish exist, I still think they are unnecessary.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Steve R » Tue May 23, 2006 11:10 pm

Mike

Thanks for the further information.

If I now have the position right, I think there is a finned 4-fish on rows 3, 4, 6, and 8, boxes 4 and 5.
Code: Select all
|  258    28     3 |     6  1458   14 |    48    9     7 |
|    1    78  4578 |    58     9   45 |     6    2     3 |
|    6     9   *48 |     2     7    3 |     1  *48     5 |
+------------------+------------------+------------------+
|    3  *128     6 | *1458 *2458  245 |     7  145     9 |
|   28     5  -278 |   147     3    9 |   248    6  1248 |
|    4 *1278     9 | *1578  *258    6 |     3   15  *128 |
+------------------+------------------+------------------+
|    9     3     1 |    45   245    8 |   245    7     6 |
|    7     4  *258 |     3     6  125 |     9  *18  *128 |
|  258     6   258 |     9  1245    7 |  2458    3  1248 |
+------------------+------------------+------------------+

There again, I might just be getting too croos-eyed to tell a jellyfish from a heap of seaweed.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Mike Barker » Wed May 24, 2006 3:54 am

Steve, good work. I fear the Franken Squirmbag is another phantom fish. I've fixed my solver and reproduce your results which is a nice example of a Franken Jellyfish. Still can't detect any fish smaller than the whale so I have hope, but not alot.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Wed May 24, 2006 11:42 am

Steve R wrote:If I now have the position right, I think there is a finned 4-fish on rows 3, 4, 6, and 8, boxes 4 and 5.

Mike Barker wrote:Steve, good work.

Yes, excellent work indeed. When viewed as Almost-Constrained-Sets (ACS), the 8s candidates in r3, r4, r6 and r8 are almost covered by c3, c8, c9 and b5.
Code: Select all
 
 .  .  *  | .  .  .  | .  *  *
 .  .  *  | .  .  .  | .  *  *
 -  -  X  | -  -  -  | -  X  X
----------+----------+---------
 #  #  X  | X  X  X  | -  X  X
 .  .  *  | *  *  *  | .  *  *
 #  #  X  | X  X  X  | -  X  X
----------+----------+---------
 .  .  *  | .  .  .  | .  *  *
 -  -  X  | -  -  -  | -  X  X
 .  .  *  | .  .  .  | .  *  *
Key: '-' <=> cells void of candidate X
     '*' <=> potential exclusions of X if no extra candidate(s) ('#') in box 4
     '#' <=> possible extra candidate(s) for exclusion r5c3<>X only
[edit: added key and the voids in r3]

If all the fin cells (in box 4) are ultimately false, the asterisked exclusions apply. If any one of the fin cells is true, the exclusion r5c3<>X still holds.

Mike Barker wrote:I've fixed my solver and reproduce your results which is a nice example of a Franken Jellyfish.

Mike, why isn't this simply a finned jellyfish? Is it one or more boxes in the "cover" that frankenizes it?:D
Last edited by ronk on Wed May 24, 2006 10:27 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques

cron