Big fish

Advanced methods and approaches for solving Sudoku puzzles

Postby Havard » Wed Mar 15, 2006 1:45 pm

tarek wrote:
Havard wrote:It has probably to do with the fact that when I identify an x-wing or a swordfish, I look to eliminate all candidates that the end-points of the strong links has in common (the ones they both see), and hence the elimination you pointed out I (and my solver) did long before I knew anything about fins.


This is probably sufficient for your self, but for helper programs & giving pointers, it is not.

Classic fishes of a size of N, should have candidates in N rows & N columns & eliminate in Lines, you can't describe your example as an x-wing.


Sorry tarek, but this is just wrong. My own solverprogram have used this approach always, and has been perfectly capable of providing hint/pointers. I checked with the susser as well, and it finds the exact same elimination and calls it a generalized x-wing. I have read about different types of x-wing here on this forum as well. My example is definately an x-wing. Maybe a generalized x-wing, but still an x-wing.

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby Havard » Wed Mar 15, 2006 1:49 pm

tarek wrote:
ronk wrote:BTW there wouldn't be any eliminations in rows 5 and 9 of the first two illustrations.


Absolutely right......I'll edit those.....

Tarek


Absolutley wrong. If the x in box 2 is not there, it will be. edit that back please.

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby Havard » Wed Mar 15, 2006 2:01 pm

Just so there is no confusion.

This is three examples of correct elimination using this technique:
Code: Select all
 
  .  .  .  |  .  .  .  |  #  #  *
  .  .  .  |  .  .  .  |  .  .  *
  .  .  .  |  .  .  .  |  x  x  *
 ----------+-----------+--|--|-----
  .  .  .  |  .  .  .  |  |  |  .
  *  *  *  |  *  X  *  |  X  X  *
  .  .  .  |  .  |  .  |  |  |  .
 ----------+-----|-----+--|--|-----
  .  .  .  |  .  |  .  |  |  |  .
  .  .  .  |  .  |  .  |  |  |  .
  *  *  *  |  *  X  *  |  X  X  *

  .  .  .  |  .  .  .  |  X  X  *
  .  .  .  |  .  .  .  |  .  .  *
  .  .  .  |  .  .  .  |  #  #  *
 ----------+-----------+--|--|-----
  .  .  .  |  .  .  .  |  |  |  .
  *  *  *  |  *  X  *  |  X  X  *
  .  .  .  |  .  |  .  |  |  |  .
 ----------+-----|-----+--|--|-----
  .  .  .  |  .  |  .  |  |  |  .
  .  .  .  |  .  |  .  |  |  |  .
  *  *  *  |  *  X  *  |  X  X  *

  .  .  .  |  .  .  .  |  #  #  *
  .  .  .  |  .  .  .  | [X][X] *
  .  .  .  |  .  .  .  |  #  #  *
 ----------+-----------+--|--|-----
  .  .  .  |  .  .  .  |  |  |  .
  *  *  *  |  *  X  *  |  X  X  *
  .  .  .  |  .  |  .  |  |  |  .
 ----------+-----|-----+--|--|-----
  .  .  .  |  .  |  .  |  |  |  .
  .  .  .  |  .  |  .  |  |  |  .
  *  *  *  |  *  X  *  |  X  X  *


havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby tarek » Wed Mar 15, 2006 2:02 pm

Havard wrote:Absolutley wrong. If the x in box 2 is not there, it will be. edit that back please.


I don't know what's your problem havard, everyone knows that all the patterns are the same, however according to the pattern rules these elikminations can't be performed according to patternt 1 &2.

Furthermore, I don't have a problem in saying Generalised "something" as it gives an indication that it is different in some sort to what the general population is used to as "something", I would keep sticking the word "generalised" to that pattern to avoid confusing people that you attempt to help & share ideas with....

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

Postby Havard » Wed Mar 15, 2006 2:09 pm

tarek wrote:
Havard wrote:Absolutley wrong. If the x in box 2 is not there, it will be. edit that back please.


I don't know what's your problem havard, everyone knows that all the patterns are the same, however according to the pattern rules these elikminations can't be performed according to patternt 1 &2.


What pattern rules are you referring to?

And should I understand it so that when Ron points out (incorrectly) that you can't do those eliminations, you change them right away, but when I point out that you can do them anyway, I have a problem?

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby tarek » Wed Mar 15, 2006 2:19 pm

Havard wrote:And should I understand it so that when Ron points out (incorrectly) that you can't do those eliminations, you change them right away, but when I point out that you can do them anyway, I have a problem?

:D
Well to tell you the truth....
The rules of finned fishes only target candidates in 1 box where they can see the fin & the vertix...

There is no mentioning of fish-style elimination....This thread is attempting to get to terms with what this technique can do

Now, my simple attempt was to add something to include the 0 true vertices line....... & applied them to 3 patterns...., so there is no WRONG in what ron said......

What you are saying is interesting because the classic fish-style activation should be extended to include a line of vertices contained in the fin box, not just the 0 vertices line....

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

Postby ronk » Wed Mar 15, 2006 2:22 pm

Havard wrote:
tarek wrote:Absolutely right......I'll edit those.....

Tarek

Absolutley (sic) wrong. If the x in box 2 is not there, it will be. edit that back please.

Sorry, tarek. I didn't notice the "[x]" in your first two illustrations. Havard, you seem a bit testy today.:)

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

Postby Havard » Wed Mar 15, 2006 2:24 pm

ronk wrote:
Havard wrote:
tarek wrote:Absolutely right......I'll edit those.....

Tarek

Absolutley (sic) wrong. If the x in box 2 is not there, it will be. edit that back please.

Sorry, tarek. I didn't notice the "[x]" in your first two illustrations. Havard, you seem a bit testy today.:)

Ron


yeah, sorry. It has been a rough week... I promise I'll snap back to my old friendly self any moment now...:D

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby tarek » Wed Mar 15, 2006 2:25 pm

Well to make everybode on the CORRECT side of things, I'll add here, the latest version of rules governing finned fish:
Code: Select all
1. Attempt to construct the framework of an N*N fish using any combination of true & virtual vertices. (a number of true vertices is needed of course...a minimum of N candidates to cover N non-elimination lines & N-1 elimination lines [to be verified])

2. If there exists a number of candidates (fins) preventing this formation which are all sharing 1 box with A vertix (true or virtual) then...

Eliminate any candidate in that box which is in the line of elimination of A vertix (true or virtual).

3. if a line of elimination in finned fish is constructed from virtual vertices only OR all True vertices in a line are sharing a box with the fin(s)...then
non finned true vertices retain classic fish-style elimination, & a quantum cell of the candidate is created from ALL fin cells & All TRUE vertices sharing their box.

:D

Any comments, point 3 is an attempt to tackle the 0 true vertices line & the (All-true-vetices-in-fin-box) line

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

Postby ronk » Wed Mar 15, 2006 6:05 pm

Myth Jellies wrote:
Code: Select all
 . . . | . . . | ? ? ?
 ? ? ? | ? ? ? | ? ? *
 . . . | . | . | ? ? ?
 ------+---|---+-|-|--
 . . . | . | . | | | ?
 . . . | . X . | X X ?
 . . . | . | . | | | ?
 ------+---|---+-|-|--
 . . . | . | . | | | ?
 . . . | . | . | | | ?
 . . . | . X . | X X ?

If you can come up with a way of filling them in which gives you a recognizable pattern that would allow you to delete the starred candidate, then the number of potential solution patterns that place the candidate in the starred cell must have been zero all along, and you can go ahead and delete that starred candidate.

That's exactly what vidarino's POM solver reports for his puzzle that started this "zero-vertex line" discussion AFAIK. Tagging the swordfish as Havard noted, instead of the complementary squirmbag, we have ...
Code: Select all
 567    2456   247    | *1      8      467    | -4567  *9     *3
 1678   468    3      |  5      2479   4679   |  1468  #267   #478
 15678  9      147    |  3      247    467    |  14568 #267   #4578
----------------------+-----------------------+-----------------------
 138    238    12     |  6      47     38     |  47     5      9
 4      7      5      |  89     39     2      |  68     36     1
 368    368    9      | *47     1      5      |  2     *37    *48
----------------------+-----------------------+-----------------------
 39     34     8      |  2      4579   479    |  57     1      6
 2      1      6      | *78     35     38     |  9     *4     *57
 579    45     47     |  49     6      1      |  3      8      2

Click here and you'll see vidarino's solver report ... "No pattern for 7 in R1C7." Then check the grid and note candidate 7 has been eliminated from R1C7.

Vidar, thanks for not giving up looking for that biiiiig fish. Without your persistence in that, this discovery would not yet have occurred. To all, good work.

Ron

P.S. In case it's not obvious, I now think it's OK to describe patterns with a "zero-vertex line" (similar to the illustration above) as a finned-fish -- not necessarily the simplest interpretation of a pattern, but not incorrect either.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Wed Mar 15, 2006 6:14 pm

I agree! A most productive thread!:)

Now, how about reprogramming those solvers to start to fish for these cases, and start posting some puzzles where this technique is required! It would be funny to see if anyone could find a puzzle where you could get close to the 15 possible eliminations!:)

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby tarek » Wed Mar 15, 2006 6:43 pm

Agreed......

Now just to complete things, although probably trivial & may come later anyway, this should be added so that we would not miss anything I've added a 4th point to include the genaralised x-wing:) that Havard illustrated

Code: Select all
1. Attempt to construct the framework of an N*N fish using any combination of true & virtual vertices. (a number of true vertices is needed of course...a minimum of N candidates to cover N non-elimination lines & N-1 elimination lines [to be verified])

2. If there exists a number of candidates (fins) preventing this formation which are all sharing 1 box with A vertix (true or virtual) ...then...

Eliminate any candidate in that box which is in the line of elimination of A vertix (true or virtual).

3. if a line of elimination in finned fish is constructed from virtual vertices only OR all True vertices in a line are sharing a box with the fin(s)...then..

non finned true vertices retain classic fish-style elimination, & a quantum cell of the candidate is created from ALL fin cells & All TRUE vertices sharing their box

4. if a line of elimination in a finned fish is constructed from only TRUE vertices & point 3 is true... then....

The vertices of this line form a quantum cell of the candidtae


Point 4 application would only be the the finned x-wing in the 9*9 grid, but should hold for larger fish in larger grids.

Comments, modifications, testings are appreciated.......

Tarek
Last edited by tarek on Wed Mar 15, 2006 2:52 pm, edited 1 time in total.
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby Myth Jellies » Wed Mar 15, 2006 6:49 pm

I wonder if this is that lost "skinny swordfish" that Jeff alluded to in the main filet-o-fish thread? The description is pretty close to what we have here.:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Havard » Wed Mar 15, 2006 7:54 pm

ok, I think I am going crazy with fish at the moment, but concider this ugly deep-sea one for a moment:
Code: Select all
. . . | . . . | x x .
. . . | . X . | x x *
. . . | . | . | x x .
------+---|---+-|-|--
. . . | . | . | x x .
. . . | . | . | x x .
. . . | . | . | x x .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . X . | X X .
. . . | . . . | . . .

where any of the small x's can be a candidate or not...

it can also look like this:
Code: Select all
. . . | . . . | x x .
. . . | . X . | x x *
. . . | . | . | x x .
------+---|---+-|-|--
. . . | . | . | x x .
. . . | . | . | x x .
. . . | . | . | x x .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . X . |[X]X .
. . . | . . . | . . .

or this:
Code: Select all
. . . | . . . | x x .
. . . | . . . | x x .
. . . | . . . | x x .
------+-------+-|-|--
. . . | . . . | x x .
. . . | . X . | x x *
. . . | . | . | x x .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . X . | X[X].
. . . | . . . | . . .

my best attempt to make it look like a proper fish (and not some monster from the deep) would be this:
Code: Select all
. . . | . . . | #  # .
. . . | .[X]. |(X)(X).
. . . | . | . | #  # .
------+---|---+-|--|--
. . . | . | . | #  # .
. . . | . X . |(X)(X)*
. . . | . | . | #  # .
------+---|---+-|--|--
. . . | . | . | |  | .
. . . | . X . | X  X .
. . . | . . . | .  . .
(X) is optional
[X] can NOT be present!


8 fins, no head... Frankenfish?:D

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby Havard » Wed Mar 15, 2006 8:17 pm

funny, I even found a sample Frankenfish puzzle...:)

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


after standard elimination and a bit of als-xz, looking at the 7's you get:
Code: Select all
7 . 7 | 7 7 . | . 7 .
7 7 . | . 7 7 | . . 7
. 7 . | 7 7 7 | . . 7
------+-------+------
7 . . | 7 7 . | . . 7
. 7 7 | 7 . . | . 7 .
7 . . | . 7 7 | . . 7
------+-------+------
. . . | . . . | 7 . .
7 . 7 | 7 7 . | . . .
. 7 7 | . 7 7 | . . .


now frankenfish hides here:
Code: Select all
*(X)X | 7 7 . | . X .
7 # | | . 7 7 | . | 7
. # | | 7 7 7 | . | 7
--|-|-+-------+---|--
7 | | | 7 7 . | . | 7
. X X | 7 . . | . X .
7 | | | . 7 7 | . . 7
--|-|-+-------+------
. | | | . . . | 7 . .
7 | # | 7 7 . | . . .
. # # | . 7 7 | . . .
eliminating *


what do you think? does Frankenfish have the right of life, or should we send him back to the deep?:)

havard
Havard
 
Posts: 378
Joined: 25 December 2005

PreviousNext

Return to Advanced solving techniques