Big fish

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Tue Mar 21, 2006 1:38 pm

Havard wrote:If you are referring to the Empty Rectangles, I know they are there (as pointed out several times, the Frankenswordfish is just an ER)

Havard wrote:Basically if I can make an ER on the sides of the "lookingline", then I know I have an potential ER, and a potential elimination, and hence also a potential Frankenfish!:)

But if the two strong links already make the an elimination, why bother to construct a "Frankenfish" around it?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Wed Mar 22, 2006 2:17 am

ronk wrote:But if the two strong links already make the an elimination, why bother to construct a "Frankenfish" around it?


1. 'Cause the chicks really dig a Frankenfish!:D

2. Because it's there?

3. Because if one can learn to find skinny/headless sealife (and that may be a pretty big "if"), and the filets that you can make from it, then you have a whole new set of basic patterns you can build on and make reductions from.

Just to recap (they get complex in a hurry)...

Frankenswordfish Example 1 in the general case is the same as a hinge/ER lined up with a conjugate pair.

Frankenswordfish Example 2 in the general case is the same as two lined up hinge/ERs coupled with a filet of a conjugate pair.

Frankenjellyfish and Frankensquirmbag are something else entirely. In the general case there probably isn't a simpler pattern to see for these.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Havard » Wed Mar 22, 2006 12:01 pm

ronk wrote:But if the two strong links already make the an elimination, why bother to construct a "Frankenfish" around it?

I believe this thread is called "big fish", and do you remember this?:D

Myth Jellies wrote:1. 'Cause the chicks really dig a Frankenfish!:D

I believe the men want to be him, and the chicks want to change him!

But joke aside, for algorithm purposes it would be really cool to have one great fishing-routine that picked up on most strong-link based patterns. Already the finned x-wing will deal with one of the three Turbot Fish patterns, and now the frankenswordfish can deal with another. They also handle a lot of the grouped stuff as a bonus! It might be a problem for the fish to cover those eliminations that require the links to have different orientations (row-column), but that might also be the only thing they will end up not handling!

havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Wed Mar 22, 2006 12:32 pm

Havard wrote:... for algorithm purposes it would be really cool to have one great fishing-routine that picked up on most strong-link based patterns.

Maybe that is "cool" and "great" for a programmed solver. But do you really think a human solver spotting an exclusion using one technique then looks for a more complex technique that subsumes the first?

I sure don't think that, and I don't think much of programmed solvers that don't emulate human solvers either.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Mon Mar 27, 2006 11:06 am

It has already been pointed out that the headless fish seem to eat a lot more candidates than the ones that still have a good fish-head on their shoulders. (How they do it without a head is another question...) But the gruesome properties of the headless jellyfish is almost to terrible to be spoken of. Because the headless finned jellyfish is not only a cannibal, it eats itself!

Concider:
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 X . . | X . X | . . X
 |-----+-|---|-+-----|
 | . . | # . # | . . |
 X . . | X . X | . . X
(X). . | # . # | . .(X)
 |-----+-|---|-+-----|
 X . . | X . X | . . X
 . . . | . . . | . . .
 . . . | . . . | . . .
(X) the non-existing head...


which can be reduced to say:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
X . . | X . . | . . .
|-----+-|-----+------
| . . | # . # | . . .
X . . | X . X | . . X
. . . | # . # | . . |
------+-----|-+-----|
. . . | . . X | . . X
. . . | . . . | . . .
. . . | . . . | . . .


And then we can eliminate:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
X * * | X * . | * * .
|-----+-|-----+------
| . . | # * # | . . .
X * * | * * * | * * X
. . . | # * # | . . |
------+-----|-+-----|
. * * | . * X | * * X
. . . | . . . | . . .
. . . | . . . | . . .


And am I the only one who is disgusted by this?? IT EATS ITSELF!!!!!!! Yuck! Surly this fish should be avoided at all cost!

Havard

edit: Added another two eliminations pointed out by ronk
Last edited by Havard on Mon Mar 27, 2006 9:30 am, edited 2 times in total.
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ravel » Mon Mar 27, 2006 12:13 pm

Maybe i just cant stand this extreme form of cannibalism, but i think it must not eat itself.

Code: Select all
. . . | . . . | . . .    . . . | . . . | . . .     . . . | . . . | . . .
. . . | . . . | . . .    . . . | . . . | . . .     . . . | . . . | . . .
X * * | X * . | * * .    X . . | . . . | . . .     X . . | . . . | . . .
|-----+-|-----+------    ------+-------+------     ------+-------+------
| . . | # . # | . . .    . . . | . . . | . . .     . . . | . . . | . . .
X * * | * * * | * * X    . . . | . . X | . . .     . . . | X . . | . . .
. . . | # . # | . . |    . . . | X . . | . . .     . . . | . . X | . . .
------+-----|-+-----|    ------+-------+------     ------+-------+------
. * * | . * X | * * X    . . . | . . . | . . X     . . . | . . . | . . X
. . . | . . . | . . .    . . . | . . . | . . .     . . . | . . . | . . .
. . . | . . . | . . .    . . . | . . . | . . .     . . . | . . . | . . .

Edit: Ok, i accept the horrible truth - better self-eater than 2 in a box.
Last edited by ravel on Mon Mar 27, 2006 9:57 am, edited 1 time in total.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Mon Mar 27, 2006 1:18 pm

Havard wrote:And then we can eliminate:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
X * * | X * . | * * .
|-----+-|-----+------
| . . | # . # | . . .
X * * | * * * | * * X
. . . | # . # | . . |
------+-----|-+-----|
. * * | . * X | * * X
. . . | . . . | . . .
. . . | . . . | . . .

Candidates in r4c5 and r6c5 may also be eliminated.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Mon Mar 27, 2006 1:26 pm

ronk wrote:
Havard wrote:And then we can eliminate:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
X * * | X * . | * * .
|-----+-|-----+------
| . . | # . # | . . .
X * * | * * * | * * X
. . . | # . # | . . |
------+-----|-+-----|
. * * | . * X | * * X
. . . | . . . | . . .
. . . | . . . | . . .

Candidates in r4c5 and r6c5 may also be eliminated.


True, I'll add that to the original post! Thanks!:)
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Mon Mar 27, 2006 2:36 pm

Havard wrote:And then we can eliminate:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
X * * | X * . | * * .
|-----+-|-----+------
| . . | # * # | . . .
X * * | * * * | * * X
. . . | # * # | . . |
------+-----|-+-----|
. * * | . * X | * * X
. . . | . . . | . . .
. . . | . . . | . . .

From a coloring point of view:
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 A . . | b . . | . . .
 ------+-------+------
 . . . | B . c | . . .
 a . . | B . c | . . D
 . . . | B . c | . . .
 ------+-------+------
 . . . | . . C | . . d
 . . . | . . . | . . .
 . . . | . . . | . . .


Using "X!Y" for "X true excludes Y true":
  • since a!D and A!d, D=A and d=a
  • since A!c and a!C, C=A and c=a
  • since A!b and a!B, B=A and b=a
Recoloring per the above equalities:
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 A . . | a . . | . . .
 ------+-------+------
 . . . | A . a | . . .
 a . . | A . a | . . A
 . . . | A . a | . . .
 ------+-------+------
 . . . | . . A | . . a
 . . . | . . . | . . .
 . . . | . . . | . . .

This is a continuous grouped x-cycle, and all candidates that see both an 'A' and an 'a' may be eliminated. This includes group members at r5c4 and r5c6.

An easier way is to just use alternating 'true' (T) and 'false' (F) for chainable strong links:
Code: Select all
 . . . | . . . | . . .
 . . . | . . . | . . .
 T . . | F . . | . . .
 ------+-------+------
 . . . | T . F | . . .
 F . . | T . F | . . T
 . . . | T . F | . . .
 ------+-------+------
 . . . | . . T | . . F
 . . . | . . . | . . .
 . . . | . . . | . . .

Then candidates that see both a 'true' and a 'false' may be eliminated.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Mon Mar 27, 2006 2:37 pm

I even have a horrible example of this finned-headless-selfeating-jellyfish.-.. Try not to be sick...

Code: Select all
6 . 7 | 3 . 8 | 5 1 4
5 . 1 | 4 7 6 | 8 . 9
. 4 . | . 1 5 | . . .
------+-------+------
9 6 . | . 5 1 | . 4 8
. . 4 | . 6 . | 1 . .
7 1 5 | 8 4 . | . 9 6
------+-------+------
1 7 . | 6 3 . | . . .
4 . . | 5 . 7 | . . 1
3 5 6 | 1 . 4 | 9 . 7


The 2's:
Code: Select all
. 2 . | . 2 . | . . .
. 2 . | . . . | . 2 .
2 . 2 | 2 . . | 2 2 2
------+-------+------
. . 2 | 2 . . | 2 . .
2 2 . | 2 . 2 | . 2 2
. . . | . . 2 | 2 . .
------+-------+------
. . 2 | . . 2 | 2 2 2
. 2 2 | . 2 . | 2 2 .
. . . | . 2 . | . 2 .


and here he is...gross:
Code: Select all
. 2 . | . 2 . | . . .
. 2 . | . . . | . 2 .
X . * | X . . | * * X
|-----+-|-----+-----|
| . 2 | # . . | 2 . |
X * . | * . * | . * X
. . . | . . # | 2 . |
------+-----|-+-----|
. . * | . . X | * * X
. 2 2 | . 2 . | 2 2 .
. . . | . 2 . | . 2 .


Luckily there is a much healthier oldschool (pun intended) Swordfish in the rows... (he just eats 9 candidates compared to the cannibals 10, but hey, at least he don't eat himself...)
Code: Select all
. X-------X . | . . .
. X---------------X .
* . * | 2 . . | 2 * 2
------+-------+------
. . 2 | 2 . . | 2 . .
2 * . | 2 . 2 | . * 2
. . . | . . 2 | 2 . .
------+-------+------
. . 2 | . . 2 | 2 * 2
. * 2 | . * . | 2 * .
. . . | . X-------X .


havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Wed Mar 29, 2006 2:03 pm

Havard wrote:
Code: Select all
. 2 . | . 2 . | . . .
. 2 . | . . . | . 2 .
X . * | X . . | * * X
|-----+-|-----+-----|
| . 2 | # . . | 2 . |
X * . | * . * | . * X
. . . | . . # | 2 . |
------+-----|-+-----|
. . * | . . X | * * X
. 2 2 | . 2 . | 2 2 .
. . . | . 2 . | . 2 .


Luckily there is a much healthier oldschool (pun intended) Swordfish in the rows... (he just eats 9 candidates compared to the cannibals 10 ...

Ten candidates is pretty darn good. According to the constraint subset technique, the max possible is 19. The generalized pattern with the 19 potential eliminations is:
Code: Select all
 .  .  .  |  .  .  .  |  .  .  . 
 .  .  .  |  .  .  .  |  .  .  . 
 X  *  *  |  X  *  X  |  *  *  X 
----------+-----------+-----------
 .  .  .  |  X  *  X  |  .  .  . 
 X  *  *  | *X  * *X  |  *  *  X 
 .  .  .  |  X  *  X  |  .  .  . 
----------+-----------+-----------
 X  *  *  |  X  *  X  |  *  *  X 
 .  .  .  |  .  .  .  |  .  .  . 
 .  .  .  |  .  .  .  |  .  .  . 

Note that candidates may initially exist in all cells marked X. Note also the elimination of candidates within the pattern in the row 5 and box 5 intersection.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Wed Mar 29, 2006 7:37 pm

Did you spot your favorite, the FRANKENFISH as well?:D
Code: Select all
 . 2 . | . 2 . | . . .
 . 2 . | . . . | . # .
 X . 2 | 2 . . | * X X
 |-----+-------+---|-|
 | . 2 | 2 . . | 2 | |
 X 2 . | 2 . 2 | . X X
 | . . | . . 2 | 2 | |
 |-----+-------+---|-|
(X). 2 | . . 2 | 2 X X
 . 2 2 | . 2 . | 2 # .
 . . . | . 2 . | . # .


Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Wed Mar 29, 2006 8:00 pm

Havard wrote:Did you spot your favorite, the FRANKENFISH as well?:D
[code]

I did not. But since that lone elimination can be made with two strong links (col 1 and box 6), I don't see why anyone would even bother with the "FRANKENFISH".
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Fri Mar 31, 2006 5:11 am

Lummox' Constraint Subsets look useful. It’s easy to see that one of the big fish is in fact one of his constraint subset configurations. In this case, the "A" subset consists of columns 5, 7, and 8 and subset "B" consists of box 3 and rows 5 and 9.
Code: Select all
. . . | . . . | # # *
. . . | . . . | # # *
. . . | . . . | # # *
------+-------+-|-|--
. . . | . . . | | | .
* * * | * X * | X X *
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
* * * | * X * | X X *

Similarly for the "carnivorous" jellyfish with the "A" subset composed of columns 1, 4, 6, and 9 and the "B" subset of box 5 and rows 3, 5, and 7, which is okay since set "B" is allowed to have intersections.
Code: Select all
| . . | | . | | . . |
| . . | | . | | . . |
X * * | X * X | * * X
|-----+-|---|-+-----|
| . . | X * X | . . |
X * * | * * * | * * X
| . . | X * X | . . |
|-----+-|---|-+-----|
X * * | X * X | * * X
| . . | | . | | . . |
| . . | | . | | . . |

Unfortunately I don't see how to apply the theory to the other forms of big fish. Can it be used or is POM or some other technique the correct approach? Also do Constraint Subsets stand on their own as a solving technique or are they consumed in other approaches. For example the hidden pattern is a nice loop consisting of grouped strong links.

Havard, if it makes you feel any better, your jellyfish is not really carnivorous. It consists of two finned swordfish (columns 1, 4, and 9 and columns 1, 6, and 9). The first eliminates r5c56; the second, r5c45. The jellyfish, as near as I can determine, then eliminates candidates in the other 16 cells.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Havard » Tue Apr 04, 2006 1:04 pm

In the series of countinually trying to push the definition of fish, I today present a little something I came over the other day...:)

Now I have been trying to find one approach that will cover all the different known fish, and in experimenting with different sets of rules, my solver found this one for me:
Code: Select all
. 5 5 | 5 . 5 | 5 . 5
. . 5 | . . . | 5 . .
. . 5 | . . 5 | 5 . 5
------+-------+------
. . 5 | 5 . . | . . .
. 5 5 | 5 . . | 5 . .
. 5 . | 5 . 5 | 5 . 5
------+-------+------
. . . | . . . | . 5 .
5 . . | . . . | . . .
. . . | . 5 . | . . .

where you have:
Code: Select all
. 5 5 | * . 5 | 5 . 5
. . 5-----------5 . .
. . 5-------5---5---5
------+-------+------
. . 5---5 . . | . . .
. 5 5 | 5 . . | 5 . .
. 5 . | 5 . * | 5 . 5
------+-------+------
. . . | . . . | . 5 .
5 . . | . . . | . . .
. . . | . 5 . | . . .


Now the elimination of R1C3 is known from the frankenfish/ER POV, and then it would not matter if it looked like this:
Code: Select all
. 5 5 | * . 5 | 5 . 5
. . X---# # #---# # #
. . X---# # #---# # #
------+-------+------
. . X---X . . | . . .
. 5 5 | 5 . . | 5 . .
. 5 . | 5 . . | 5 . 5
------+-------+------
. . . | . . . | . 5 .
5 . . | . . . | . . .
. . . | . 5 . | . . .


But this fish allowed another elimination... Then I realized that what is going on is really this:
Code: Select all
. 5 5 | * . 5 | 5 . 5
. . X------(X)--# . .
. . X-------X---#---#
------+-------+------
. . X---X . . | . . .
. 5 5 | 5 . . | 5 . .
. 5 . | 5 . * | 5 . 5
------+-------+------
. . . | . . . | . 5 .
5 . . | . . . | . . .
. . . | . 5 . | . . .


or to put it in a more familiar setting:
Code: Select all
. . . | . . . | # # .
. . . | . . . | # # .
. . . | . . . | # # .
------+-------+-|-|--
. . . | . X . | | | *
. . . | * | * | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .

Now to formalize this I would use the following definition:
Code: Select all
. . . | . . . | # # .
. . . | . H . | # # *
. . . | . | . | # # .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . X . | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .
# - is the fins
X - is the fish
H - is the fishhead
Note: Only 1 X needs to be present in each line, and any number of # will still make the elimination valid.

Code: Select all
. . . | . . . | # # .
. . . | . . . | # # .
. . . | . . . | # # .
------+-------+-|-|--
. . . | . H . | | | .
. . . | * X * | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .
# - is the fins
X - is the fish
H - is the fishhead
Note: Only 1 X needs to be present in each line, and any number of # will still make the elimination valid.

Code: Select all
. . . | . . . | # # .
. . . | . . . | # # .
. . . | . . . | # # .
------+-------+-|-|--
. . . | . . . | | | .
. . . | . X . | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . H . | | | .
. . . | . | . | | | .
. . . | * X * | X X .
# - is the fins
X - is the fish
H - is the fishhead
Note: Only 1 X needs to be present in each line, and any number of # will still make the elimination valid.

and as we all know by now, headless fish is the most hungry... (well of course it is...)
Code: Select all
. . . | . . . | # # *
. . . | . . . | # # *
. . . | . . . | # # *
------+-------+-|-|--
. . . | . . . | | | *
* * * | * X * | X X *
. . . | . | . | | | *
------+---|---+-|-|--
. . . | . | . | | | *
. . . | . | . | | | *
* * * | * X * | X X *


and then the original problem would look like this:
Code: Select all
. 5 5 | . . 5 | 5 . 5
. . X------(X)--# . .
. . X-------X---#---#
------+-------+------
. . X---H . . | . . .
. 5 5 | 5 . . | 5 . .
. 5 . | 5 . * | 5 . 5
------+-------+------
. . . | . . . | . 5 .
5 . . | . . . | . . .
. . . | . 5 . | . . .

and this: (Frankenfish)
Code: Select all
. 5 5 | * . 5 | 5 . 5
. . X--(X)-----(X). .
. . X--(X)--#--(X)--#
------+-------+------
. . X---X------(H). .
. 5 5 | 5 . . | 5 . .
. 5 . | 5 . . | 5 . 5
------+-------+------
. . . | . . . | . 5 .
5 . . | . . . | . . .
. . . | . 5 . | . . .


Havard
Havard
 
Posts: 377
Joined: 25 December 2005

PreviousNext

Return to Advanced solving techniques