POM Analysis of the X-Wing: The Filet-O-Fish Rule

Advanced methods and approaches for solving Sudoku puzzles

Postby vidarino » Fri Jan 13, 2006 1:20 pm

I found a slightly shorter grouped X-cycle which eliminates the culprits;

[r12c2]-2-[r3c23]=2=[r3c5]-2-[r456c5]=2=[r5c6]-2-[r5c23]=2=[r46c2] => [r12c2] <> 2

It's my first nice loop notation attempt, but I think it's valid.:)
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Carcul » Fri Jan 13, 2006 1:37 pm

Hi Vidarino.

Your idea is completely correct, but in the chain notation there is something missing. This is the correct one:

[r12c2]-2-[r3c23]=2=[r3c5]-2-[r456c5]=2=[r5c6]-2-[r5c23]=2=[r46c2]-2-[r12c2], => [r12c2] <> 2.

When writing a nice loop of discontinuous type, its the common and correct practice to start and end the loop notation in the cell(s) where the discontinuity arises, as in this case.

BTW, and although not important, your loop is not shorter than the one I have writen: yours have the same number of links (seven) but uses two more cells:D .

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby vidarino » Fri Jan 13, 2006 1:47 pm

Hi!

Carcul wrote:When you write a nice loop of discontinuous type, you must start and end the loop notation in the cell(s) where the discontinuity arises, as in this case.


Oops, you're right. I forgot to add the end-point. Which is why my chain looked shorter. Damn. ;) Thanks for pointing it out.:)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Myth Jellies » Fri Jan 13, 2006 3:12 pm

Carcul & vidarino,

Excellent. Because I just need to see the picture, I note that both are grouped x-cycles of the form A-B=C-D=E-F=G-A. Carcul's grouping looks like...

Code: Select all
+------------+-----------+-----------+
| .   2A  2B | .   2   2E| .   2   2 |
| .   2A  2B | .   2   2E| .   2   2 |
| .   2G  2BG| .   2F  . | .   .   . |
+------------+-----------+-----------+
| .   2   .  | .   2   . | .   2   2 |
| .   2   2C | .   2   2D| .   2   2 |
| .   2   .  | .   2   . | .   2   2 |
+------------+-----------+-----------+
| .   .   .  | .   .   . | 2   .   . |
| .   .   .  | 2   .   . | .   .   . |
| 2   .   .  | .   .   . | .   .   . |
+------------+-----------+-----------+


Whereas, vidarino's looks like...

Code: Select all
+------------+-----------+-----------+
| .   2A  2  | .   2   2 | .   2   2 |
| .   2A  2  | .   2   2 | .   2   2 |
| .   2B  2B | .   2C  . | .   .   . |
+------------+-----------+-----------+
| .   2G  .  | .   2D  . | .   2   2 |
| .   2F  2F | .   2D  2E| .   2   2 |
| .   2G  .  | .   2D  . | .   2   2 |
+------------+-----------+-----------+
| .   .   .  | .   .   . | 2   .   . |
| .   .   .  | 2   .   . | .   .   . |
| 2   .   .  | .   .   . | .   .   . |
+------------+-----------+-----------+


Carcul's grouping, while using fewer cells, does bring up the issue of having a cell be included in more than one group. I am not familiar enough with the rules governing grouping to know if this is a problem.

I like the shorthand way of representing groups [r123c2] instead of [r1c3|r2c3|r3c3]. It's terser and less daunting to look at in my opinion.

Since nishio's logic tends to be akin to A -> C -> E -> G which conflicts with A, I'm wondering if, perhaps, x-cycles with groups covers every nishio reduction. Perhaps a topic for another thread.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Fri Jan 13, 2006 3:32 pm

Jeff,

What's the skinny on the skinny sealife?:D

I've never heard of a skinny swordfish, or any of it's relatives. If you have a pattern or rule for them, then we could apply the same rule which produced the filet-o-fish and perhaps come up with some lean fish fillets.

Of course, it is one thing to apply the fillet concept to something people are already looking for ("Darn! If only I didn't have that candidate in that cell, I'd have an X-wing...oh, wait, that's a filet-o-fish!) It won't be nearly as useful applying it to something that few people have even heard of. Still, it would be interesting to see if it works.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Fri Jan 13, 2006 3:48 pm

Myth Jellies wrote:Carcul's grouping, while using fewer cells, does bring up the issue of having a cell be included in more than one group. I am not familiar enough with the rules governing grouping to know if this is a problem.

Since nishio's logic tends to be akin to A -> C -> E -> G which conflicts with A, I'm wondering if, perhaps, x-cycles with groups covers every nishio reduction. Perhaps a topic for another thread.

Firstly, congratulations to Carcul & vidarino.:D

During my analysis of triple implication chains, it was quite common for a nice loop to cross over a node twice. Since for a triple chain, 3 nice loops can be obtained but only 2 of them are needed to validate the deduction. This is because 2 implications are available in each nice loop and only 3 implications are needed for a triple chain. I know these overlaps were OK when they happened in the third nice loop. So, I guess Carcul's loop is OK too. However, it will be nicer if this can be proven, perhaps by POM.

As to whether x-cycles with groups would cover every nishio reduction, I feel quite positive about that too. However, it will be nicer if this can be proven also.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby vidarino » Fri Jan 13, 2006 8:12 pm

A little comment about Carcul's loop:
Code: Select all
+------------+-----------+-----------+
| .   2A  2B | .   2   2E| .   2   2 |
| .   2A  2B | .   2   2E| .   2   2 |
| .   2G  2BG| .   2F  . | .   .   . |
+------------+-----------+-----------+
| .   2   .  | .   2   . | .   2   2 |
| .   2   2C | .   2   2D| .   2   2 |
| .   2   .  | .   2   . | .   2   2 |
+------------+-----------+-----------+
| .   .   .  | .   .   . | 2   .   . |
| .   .   .  | 2   .   . | .   .   . |
| 2   .   .  | .   .   . | .   .   . |
+------------+-----------+-----------+


I have no idea how to express this in loop notation (it probably isn't possible?), but this particular "hypothesis" can actually be ended at step E already: Consider the groups A and E compared to the 2s in the third box. If 2 is one of A, then (as proved by Carcul's chain) it's also in one of E => instant conflict, as there are no more room for a 2 in box 3.

I don't have any conclusion, sorry, it was just an observation. ;)

(Post-writing epiphany; It seems this contradiction can be reached by using two separate chains for each of R1C2 and R2C2, disproving them one at a time... Oh well, I'll just post it anyway. ;)
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Jeff » Fri Jan 13, 2006 9:43 pm

Myth Jellies wrote:What's the skinny on the skinny sealife?:D

Hi MJ, This is all I know. A "skinny" swordfish is 2 row by 3 column, with strong rows and weak columns.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Thu Jan 19, 2006 7:01 am

Michael Mepham's "unsolvable" #9 is a nice puzzle for solving using Filet-O-Fish.

Code: Select all
 *-----------*
 |..6|..2|..9|
 |1..|5..|.2.|
 |.47|3.6|..1|
 |---+---+---|
 |...|..8|.4.|
 |.3.|...|.7.|
 |.1.|6..|...|
 |---+---+---|
 |4..|8.3|21.|
 |.6.|..1|..4|
 |3..|4..|9..|
 *-----------*


Using simple techniques (no colors) gets you to this grid.

Code: Select all
{58}   {58}   {6}    {17}   {147}  {2}    {47}   {3}    {9}   
{1}    {9}    {3}    {5}    {8}    {47}   {47}   {2}    {6}   
{2}    {4}    {7}    {3}    {9}    {6}    {58}   {58}   {1}   
{9}    {257}  {25}   {17}   {1357} {8}    {6}    {4}    {23}   
{6}    {3}    *458*  {2}    {45}   {9}    {1}    {7}    *58*   
{578}  {1}    {2458} {6}    {3457} {457}  {58}   {9}    {23}   
{4}    {57}   {9}    {8}    {6}    {3}    {2}    {1}    {57}   
{578}  {6}    -258-  {9}    {257}  {1}    {3}    {58}   {4}   
{3}    #2578# *1*    {4}    {257}  {57}   {9}    {6}    *578* 


A sashimi x-wing for the 8's in r59c39 (fin in r9c2) kills the 8 in r8c3. You can make quite a few simple reductions after that to get to...

Code: Select all
{58}   {58}   {6}    {17}   {147}  {2}    {47}   {3}    {9}   
{1}    {9}    {3}    {5}    {8}    {47}   {47}   {2}    {6}   
{2}    {4}    {7}    {3}    {9}    *6*    *58*   *58*   {1}   
{9}    {257}  {25}   {17}   {157}  {8}    {6}    {4}    {3}   
{6}    {3}    {48}   {2}    {45}   {9}    {1}    {7}    {58}   
{57}   {1}    {48}   {6}    {3}    *457*  *58*   *9*    {2}   
{4}    {57}   {9}    {8}    {6}    {3}    {2}    {1}    {57}   
{578}  {6}    {25}   {9}    -257-  *1*    *3*    *58*   {4}   
{3}    {2578} {1}    {4}    {257}  #57#   {9}    {6}    {578} 


Here, the 5's have a sashimi swordfish in r368c678 (fin in r9c6) which eliminates the 5 in r8c5. This kills a couple more 5's in row 9 leading to...

Code: Select all
{58}  {58}  {6}   {17}  {147} {2}   {47}  {3}   {9}   
{1}   {9}   {3}   {5}   {8}   {47}  {47}  {2}   {6}   
{2}   {4}   *7*   {3}   {9}   {6}   *58*  *58*  {1}   
{9}   {257} #25#  {17}  {157} {8}   {6}   {4}   {3}   
{6}   {3}   {48}  {2}   {45}  {9}   {1}   {7}   {58} 
-57-  {1}   *48*  {6}   {3}   {457} *58*  *9*   {2}   
{4}   {57}  {9}   {8}   {6}   {3}   {2}   {1}   {57} 
{578} {6}   *25*  {9}   {27}  {1}   *3*   *58*  {4}   
{3}   {278} {1}   {4}   {257} {57}  {9}   {6}   {78} 


...another sashimi swordfish for 5's in r368c378 (fin in r4c3) eliminating the 5 in r6c1 and breaking open the puzzle.

Of course this could have been solved using multiple colors or x-cycles, but it's nice to have a varied diet.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Thu Jan 19, 2006 12:56 pm

Myth Jellies wrote:... found a whole bunch of sashimi/filet-o-fish swordfish similar to this...

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   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+

Sorry for arriving late, but if you (anyone) still know(s) the puzzle from which this came, would you please post it?

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

Postby ronk » Thu Jan 19, 2006 5:33 pm

Carcul wrote:In that case, I have analized your grid with the "2s" and have found that the eliminations are easy to understand in light of the following grouped X-cycle:

[r1c2|r2c2]-2-[r1c3|r2c3|r3c3]=2=[r5c3]-2-[r5c6]=2=[r1c6|r2c6]-2-
[r3c5]=2=[r3c2|r3c3]-2-[r1c2|r2c2], => r1c2,r2c2<>2.

When an overlap in a nice loop is valid, it seems logical that the overlap can be used to prove a placement as well as an elimination, particularly when it's at the discontinuity of a nice loop. IOW I think we can write:

[r1c3|r2c3|r3c3]=2=[r5c3]-2-[r5c6]=2=[r1c6|r2c6]-2-[r3c5]=2=[r3c2|r3c3] implying r3c3=2

... because r3c3=2 is the only common implication at the intersection of the nice loop discontinuity ... primarily since r3c3 is the only cell at the intersection of row 3 and col 3.

[edit: CORRECTION: The deduction r3c3=2 is invalid because the implication chains for the above are:
  1. r5c6<>2 => (r1c6=2 or r2c6=2) => r3c5<>2 => (r3c2=2 or r3c3=2)
  2. r5c6=2 => r5c3<>2 => (r1c3=2 or r2c3=2 or r3c3=2)
... and either chain 1 OR or chain 2 will be true for the solved puzzle. IOW, all we know now is either r1c2=2 or r3c3=2 or r3c2=2 or r3c1=2.

OR implies a union, not an intersection.
OR implies a union, not an intersection.
OR implies ....... (98 more times)]:(:(

While it seems logical, I'm a bit skeptical as I don't even have the original puzzle with which to test the deduction.:(
[edit: Obviously, I wasn't skeptical enough.]

Regards, Ron
Last edited by ronk on Fri Jan 20, 2006 8:53 am, edited 8 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Carcul » Thu Jan 19, 2006 6:51 pm

Hi Ronk.

Ronk wrote:If a nice loop with an overlap is valid,


That depends on the overlap.

Ronk wrote:IOW I think we can write:

[r1c3|r2c3|r3c3]=2=[r5c3]-2-[r5c6]=2=[r1c6|r2c6]-2-[r3c5]=2=[r3c2|r3c3] implying r3c3=2


But, what is the contradiction that arises by making r3c3<>2?

Ronk wrote:While it seems logical, I'm a bit skeptical as I don't even have the original puzzle with which to test the deduction.


I would like also to take a look at the puzzle. Perhaps Myth Jellies can provide it.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Thu Jan 19, 2006 7:05 pm

Carcul wrote:
Ronk wrote:If a nice loop with an overlap is valid,

That depends on the overlap.

Correct, I should have said "When use of an overlap in a nice loop is valid .... "

Ronk wrote:But, what is the contradiction that arises by making r3c3<>2?

I'm not aware a contradiction is req'd ... as I believe I've seen placements proven elsewhere with nice loops having a strong link on each end ... for the same node and candidate, of course.

[edit: I then saw my logic error, "unsaw" it, and saw it again. My original post edited and edited.]

Ron
Last edited by ronk on Fri Jan 20, 2006 8:56 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Fri Jan 20, 2006 6:04 am

There is no specific puzzle, per se. If you have the same digit solved for in just three boxes that all share a single row or column then you have a generic situation that looks something like this...

Code: Select all
+-----------+-----------+-----------+
| .   N   N | .   N   N | .   N   N |
| .   N   N | .   N   N | .   N   N |
| .   N   N | .   N   N | .   N   N |
+-----------+-----------+-----------+
| .   N   N | .   N   N | .   N   N |
| .   N   N | .   N   N | .   N   N |
| .   N   N | .   N   N | .   N   N |
+-----------+-----------+-----------+
| .   .   . | .   .   . | N   .   . |
| .   .   . | N   .   . | .   .   . |
| N   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+


From there, it will largely be luck based on the other digits provided by the puzzle, the other digits you have solved, and the candidate N's that you have removed via other means, such as naked pairs etc. that will determine which N's are available to you for placement of the remaining candidates. (You hope some of them will be removed from consideration, because as it stands there are 216 potential solution patterns for N in this grid.) If you blow out 9 of those N's in the shape of a 3-3-3 swordfish (making an elimination in all six top boxes just to be safe), then you will be left with a grid of N's where you can find a 3-3-3 swordfish.

Code: Select all
+-----------+-----------+-----------+
| .   N   x | .   x   N | .   N   x |
| .   N   N | .   N   N | .   N   N |
| .   N   x | .   x   N | .   N   x |
+-----------+-----------+-----------+
| .   N   N | .   N   N | .   N   N |
| .   N   N | .   N   N | .   N   N |
| .   N   x | .   x   N | .   N   x |
+-----------+-----------+-----------+
| .   .   . | .   .   . | N   .   . |
| .   .   . | N   .   . | .   .   . |
| N   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+
blowing out the N's with any random swordfish pattern of x's leaves...
+-----------+-----------+-----------+
| .   N   . | .   .   N | .   N   . |
| .   N  *N | .  *N   N | .   N  *N |
| .   N   . | .   .   N | .   N   . |
+-----------+-----------+-----------+
| .   N  *N | .  *N   N | .   N  *N |
| .   N  *N | .  *N   N | .   N  *N |
| .   N   . | .   .   N | .   N   . |
+-----------+-----------+-----------+
| .   .   . | .   .   . | N   .   . |
| .   .   . | N   .   . | .   .   . |
| N   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+
...a grid containing a 3-3-3 swordfish.


If you only blow out 8 (or in some cases 7) of those N's instead of all 9, then you will be left with a filet-o-fish swordfish.
Code: Select all
8 of 9 filet-o-fish case
+-----------+-----------+-----------+
| .   N   . | .   .   N | .   N   . |
| .   N  *N | .  *N   N | .  -N- *N |
| .   N   . | .   .   N | .   N  #N |
+-----------+-----------+-----------+
| .   N  *N | .  *N   N | .   N  *N |
| .   N  *N | .  *N   N | .   N  *N |
| .   N   . | .   .   N | .   N   . |
+-----------+-----------+-----------+
| .   .   . | .   .   . | N   .   . |
| .   .   . | N   .   . | .   .   . |
| N   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+
7 of 9 filet-o-fish case
+-----------+-----------+-----------+
| .   N   . | .  #N   N | .   N   . |
| .   N  *N | .  *N  -N-| .   N  *N |
| .   N   . | .  #N   N | .   N   . |
+-----------+-----------+-----------+
| .   N  *N | .  *N   N | .   N  *N |
| .   N  *N | .  *N   N | .   N  *N |
| .   N   . | .   .   N | .   N   . |
+-----------+-----------+-----------+
| .   .   . | .   .   . | N   .   . |
| .   .   . | N   .   . | .   .   . |
| N   .   . | .   .   . | .   .   . |
+-----------+-----------+-----------+


Of course, a puzzle may end up blowing out more than the required candidates, which explains why most swordfish are not 3-3-3 and they don't usually delete the full slate of possible candidates.

Ron, the upshot is, I don't have a specific puzzle to point to, but it probably would not be too difficult to design or find one...especially if you were not too picky about when in the solving process you applied your swordfish or filet-o-fish search.

edited to fix grids
Last edited by Myth Jellies on Sun Apr 16, 2006 5:24 am, edited 2 times in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Fri Jan 20, 2006 1:16 pm

Myth Jellies wrote:If you only blow out 8 (or in some cases 7) of those N's instead of all 9, then you will be left with a filet-o-fish swordfish.

Are you using the "swordfish" part of "filet-o-fish swordfish" generically ... to represent all the fishes (x-wing, swordfish, jellyfish, squirmbag)?
Ron, the upshot is, I don't have a specific puzzle to point to, but it probably would not be too difficult to design or find one...especially if you were not too picky about when in the solving process you applied your swordfish or filet-o-fish search.

I'm not that picky, so I'll search for some examples. Taking "swordfish" literally here, I think it's just a matter of searching for degenerate jellyfish, which should be easy.

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

PreviousNext

Return to Advanced solving techniques