Big fish

Advanced methods and approaches for solving Sudoku puzzles

Postby ravel » Tue Mar 14, 2006 6:19 pm

Tarek, starting from a "full" finned fish, you will be able to make the same eliminations after dropping any of the fish candidates, because the argument will ever hold, that a candidate that could be eliminated before, would kill both all candidates of a row (or column resp.) and the finns, so that you are left with too less rows (columns) that contain candidates for the fishes columns (rows).
As a sample here is a full finned swordfish;
Code: Select all
. . . | . . . | # # .
. . . | . X . | X X *
. . . | . | . | # # .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . X . | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .

A candidate in * will kill all candidates in row 2 and the finns in columns 7 and 8. So there only remain rows 5 and 9 that can contain candidates in cols 578. It does not matter, if candidates X were missing before.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby tarek » Tue Mar 14, 2006 6:52 pm

ravel wrote:make the same eliminations after dropping any of the fish candidates, because the argument will ever hold, that a candidate that could be eliminated before, would kill both all candidates of a row (or column resp.) and the finns, so that you are left with too less rows (columns) that contain candidates for the fishes columns (rows).
As a sample here is a full finned swordfish


Very good news, I'm happy:D

This definitely makes the finned fish a very powerful tool, it was powerful before, but we know now that it has more horse power.

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

Postby Myth Jellies » Wed Mar 15, 2006 3:12 am

This thread continues to suprise me. Excellent work by everybody. While I knew that the sashimi version of the filets could result in some otherwise untenable seafood setups, I missed the fact that a zero candidate row or group for swordfish and jellyfish was possible.

Let me show my version of the underlying goings on with regard to filets and sashimi...
Code: Select all
. . . | . . . | ? ? ?
? ? ? | ? ? ? | ? ? *
. . . | . | . | ? ? ?
------+---|---+-|-|--
. . . | . | . | | | ?
. . . | . X . | X X ?
. . . | . | . | | | ?
------+---|---+-|-|--
. . . | . | . | | | ?
. . . | . | . | | | ?
. . . | . X . | X X ?

When considering the starred candidate, it turns out the total number of potential solution patterns that place that candidate in that cell is unaffected by whether or not any of the cells marked with a question mark contain that candidate. What this means is that you are free to fill in that candidate or leave it out of any of the cells marked with a question mark any way you see fit. 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.

In this case, we can imagine putting in the following candidates and blanks...
Code: Select all
. . . | . . . | . . .
. . . | . X . | X X *
. . . | . | . | . . .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . X . | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .

...giving us sashimi swordfish that allows us to remove the starred candidate.

This might be a reasonable way of coding up a more thorough search for sashimi seafood. You can kind of do it by hand as well by laying a couple of pencils on the grid and looking for potential patterns.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby tarek » Wed Mar 15, 2006 9:49 am

This bizarre pattern, I think has more to offer...........

As we have no true vetices in one of the lines then:

1. you can achieve classsic swordfish elimination through the true vertices (Havard brushed on this fact earlier)

2. As by proof of contradiction that ravel showed..... we need that extra candidate.............That extra candidate HAS to be the fin, so in this pattern One of the fins is always Positive (a quantum cell)........

In simple words, True vertices retain the classic swordfish power, All non-fin cell in the fins' box cannot have that candidate.

some interesting examples would be:
Code: Select all
 . . . | . . . | * . . 
 * * * | * * * | * X X 
 . . . | . . . | * . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 * * * | X * * | * X * 
-------+-------+------
 . . . | . . . | . . . 
 * * * | X * * | * * X 
 . . . | . . . | . . .


& the more intersting one
Code: Select all
 . . . | . . . | * . . 
 . . . | . . . | * X X 
 . . . | . . . | * X X 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 * * * | X * * | * X * 
-------+-------+------
 . . . | . . . | . . . 
 * * * | X * * | * * X 
 . . . | . . . | . . .


Tarek
Last edited by tarek on Wed Mar 15, 2006 5:59 am, edited 2 times in total.
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby Havard » Wed Mar 15, 2006 9:59 am

Myth Jellies wrote:Let me show my version of the underlying goings on with regard to filets and sashimi...
Code: Select all
. . . | . . . | ? ? ?
? ? ? | ? ? ? | ? ? *
. . . | . | . | ? ? ?
------+---|---+-|-|--
. . . | . | . | | | ?
. . . | . X . | X X ?
. . . | . | . | | | ?
------+---|---+-|-|--
. . . | . | . | | | ?
. . . | . | . | | | ?
. . . | . X . | X X ?

When considering the starred candidate, it turns out the total number of potential solution patterns that place that candidate in that cell is unaffected by whether or not any of the cells marked with a question mark contain that candidate. What this means is that you are free to fill in that candidate or leave it out of any of the cells marked with a question mark any way you see fit.


This is almost right, but not quite. The questionmarks that are not part of any of three three lines are irrelevant anyway, but if you leave out all the questionsmarks in the box as well as the top X of the line not in the box, then the elimination is no longer valid...
EDIT: While this is right in theory, it would make an invalid puzzle, so it is not right...
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . *
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . X . | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .
no elimination can be done at *


EDIT: As pointed out by ravel, this is not a valid puzzle, so I retract this statement... sorry MJ.

This might be stating obvious, but this just shows that you can't eliminate ALL those questionsmarks safely...
EDIT: of course you can't, because there won't exist a valid puzzle where all the questionmarks does not exist...

A definition that should hold water is this one:
Code: Select all
. . . | . . . | x x .
. . . | . X . | x x *
. . . | . | . | x x .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . X . | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .
For actual puzzles, you can have one less X per line, and any number of x's and the elimination will still be valid!

EDIT: changed wording to make it correct

Testing it:
Code: Select all
. . . | . . . | x . .
. . . | . . . | | . *
. . . | . . . | | . .
------+-------+-|----
. . . | . . . | | . .
. . . | . X . | | X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .


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


seems good!:)

havard
Last edited by Havard on Wed Mar 15, 2006 6:41 am, edited 1 time in total.
Havard
 
Posts: 378
Joined: 25 December 2005

Postby Havard » Wed Mar 15, 2006 10:08 am

tarek wrote:This bizarre pattern, I think has more to offer...........

As we have no true vetices in one of the lines then:

1. you can achieve classsic swordfish elimination through the true vertices (Havard brushed on this fact earlier)

2. As by proof of contradiction that ravel showed..... we need that extra candidate.............That extra candidate HAS to be the fin, so in this pattern One of the fins is always Positive (a quantum cell)........

In simple words, True vertices retain the classic swordfish power, All non-fin cell in the fins' box cannot have that candidate.

some interesting examples would be:
Code: Select all
 . . . | . . . | * . . 
 * * * | * * * | * X X 
 . . . | . . . | * . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 * * * | X * * | * X * 
-------+-------+------
 . . . | . . . | . . . 
 * * * | X * * | * * X 
 . . . | . . . | . . .


& the more intersting one
Code: Select all
 . . . | . . . | * . . 
 . . . | . . . | * X X 
 . . . | . . . | * X X 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 * * * | X * * | * X * 
-------+-------+------
 . . . | . . . | . . . 
 * * * | X * * | * * X 
 . . . | . . . | . . .


Tarek


Your first example is just a old, plain 2x2x2 swordfish.

As for your other example, how is this any of this different to what I already pointed out here:
http://forum.enjoysudoku.com/viewtopic.php?p=23272#p23272

and again here:
http://forum.enjoysudoku.com/viewtopic.php?p=23286#p23286

:)
havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby ravel » Wed Mar 15, 2006 10:25 am

Havard wrote:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . *
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . X . | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .
no elimination can be done at *


This would be an invalid puzzle, because you cannot find a candidate for all columns 578.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Havard » Wed Mar 15, 2006 10:37 am

ravel wrote:
Havard wrote:
Code: Select all
. . . | . . . | . . .
. . . | . . . | . . *
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . X . | X X .
. . . | . | . | | | .
------+---|---+-|-|--
. . . | . | . | | | .
. . . | . | . | | | .
. . . | . X . | X X .
no elimination can be done at *


This would be an invalid puzzle, because you cannot find a candidate for all columns 578.


You are absolutly right! Did not think far enough... Well, back to edit the post... thanks!:)

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby tarek » Wed Mar 15, 2006 11:37 am

Havard wrote:Your first example is just a old, plain 2x2x2 swordfish.

As for your other example, how is this any of this different to what I already pointed out here:
http://forum.enjoysudoku.com/viewtopic.php?p=23272#p23272

and again here:
http://forum.enjoysudoku.com/viewtopic.php?p=23286#p23286

If you look closely at my post, you would find your name there, but you're right, I did not provide the links.

The first example is a true swordfish, but if you think of it as a finned fish, you would achieve the eliminations of r1c7 & r3c7 in the same step....These were examples of this pattern, did I say it wasn't a swordfish ?

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

Postby Havard » Wed Mar 15, 2006 11:55 am

tarek wrote:The first example is a true swordfish, but if you think of it as a finned fish, you would achieve the eliminations of r1c7 & r3c7 in the same step....


I don't quite get this. 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. To illustrate this, just take this x-wing example:
Code: Select all
. . . | . * X | . . .
. . . | . * | | . . .
. . . | X * | | . . .
------+-|---|-+------
. . . | | . | | . . .
. . . | | . | | . . .
. . . | | . | | . . .
------+-|---|-+------
. . . | | * | | . . .
* * * | X * X | * * *
. . . | . * . | . . .


Now by following the simple "eliminate all candidates that the two end-points has in common (both can see)"-rule, you can do these eliminations, and I think "everyone" has been doing this long before the fin came into existence.

That is why I commented, because I did not think the proposal of a "fin" was neccessary to do those eliminations in your first example.

I guess all this confusion comes from the fact that none of these terms have been really defined in a way that makes everybody relate to them in the same way. anyone want to take on that job?:D

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby ronk » Wed Mar 15, 2006 12:29 pm

I thought the most recent pattern of interest was ...
Code: Select all
  .  .  .  |  .  .  .  |  x  x  *
  .  .  .  |  . [X] .  | [X][X] *
  .  .  .  |  .  |  .  |  x  x  *
 ----------+-----|-----+--|--|-----
  .  .  .  |  .  |  .  |  |  |  .
  *  *  *  |  *  X  *  |  X  X  *
  .  .  .  |  .  |  .  |  |  |  .
 ----------+-----|-----+--|--|-----
  .  .  .  |  .  |  .  |  |  |  .
  .  .  .  |  .  |  .  |  |  |  .
  *  *  *  |  *  X  *  |  X  X  *

With no candidates in row 2 of the "swordfish", exactly one 'x' in box 3 must be true to avoid the contradiction of three candidates for two rows. This is clearly a swordfish pattern IMO, albeit a grouped one.

But have we reached a consensus as to whether or not it's also a finned fish?

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

Postby tarek » Wed Mar 15, 2006 12:57 pm

ronk wrote:But have we reached a consensus as to whether or not it's also a finned fish?

Yes ron, if we subdivide them it becomes clearer..........
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  *
  .  .  .  |  .  |  .  |  |  |  .
 ----------+-----|-----+--|--|-----
  .  .  .  |  .  |  .  |  |  |  .
  .  .  .  |  .  |  .  |  |  |  .
  *  *  *  |  *  X  *  |  X  X  *
Last edited by tarek on Wed Mar 15, 2006 9:35 am, edited 3 times in total.
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby tarek » Wed Mar 15, 2006 1:10 pm

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.

Nobody is inventing the wheel, we are trying to get hold of what this technique is capable of.

At this moment for manual solver & programmer IMO it stands as follows.
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...then
true vertices retain classic fish-style elimination, & a quantum cell of the candidate is created from ALL fin cells.

I consider that an advanced technique, but with practice it should be easy to construct & has proved to be very powerful.

The above is true for finned x-wings & swordfishes, & it holds even IF simpler elimination techniques are present.

I haven't tested it on finned Jellyfishes yet.

Tarek
Last edited by tarek on Wed Mar 15, 2006 9:49 am, edited 8 times in total.
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby ronk » Wed Mar 15, 2006 1:24 pm

tarek wrote:if we subdivide them it becomes clearer...

I don't have an issue with applying superposition to sudoku, but because your 3rd illustration is virtually identical to the question, it seems like a circular definition. And I don't see how you can get the exclusions in rows 5 and 9 without also getting the exclusions in r123c9 (of the 3rd ill.).

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

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

Postby tarek » Wed Mar 15, 2006 1:28 pm

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.....
[EDIT:
changes have been made, at this stage., but further ammendments down in this thread causes revision of the above statements]

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

PreviousNext

Return to Advanced solving techniques