
View previous topic :: View next topic 
Author 
Message 
 MadOverlord
 Joined: 01 Jun 2005  Posts: 80  :  Location: Wilmington, NC, USA  Items 

Posted: Sat Sep 17, 2005 10:49 pm Post subject: Precise definition for xwing, swordfish, jellyfish, etc..? 


From another thread on this forum:
AMcK wrote:  Look for N columns (2 for Xwing, 3 for the Swordfish, 4 for a Jellyfish, 5 for a Squirmbag) with only two candidate cells for ONE given digit. If these fall on exactly N common rows, and each of those rows has at least 2 candidate cells, then all N rows can be cleared of that digit (except in the defining cells!). 
I'm playing around with implementing a deducer for these kind of patterns in the Susser, and there seems to be two definitions for them that I've run into.
AFAICT, the more general definition seems to be:
Look for N columns (2 for Xwing, 3 for the Swordfish, 4 for a Jellyfish, 5 for a Squirmbag) with 2 to N candidate cells for ONE given digit. If these fall on exactly N common rows, then all N rows can be cleared of that digit (except in the defining cells!). The test can also be done swapping rows for columns.
It seems to me that you could actually look for columns with 1N candidate cells (ie: includes solved cells), but if you find, say, a swordfish with such a cell, it degenerates to an xwing.
Note also that the requirement "and each of those rows has at least 2 candidate cells" seems to be extraneous. Consider the swordfish:
Code: 
A..C.....
.........
B..D..E..
.........
......F..

The only possibilities are ADF or BCF. In practice, of course, most players would find the ABCD Xwing first, and F would be pinned.
Comments? Once I get this nailed down I'll be able to implement not only a nice deducer for these patterns but also a nifty visualizer. 

Back to top 


 Lummox JR
 Joined: 07 Sep 2005  Posts: 202  :   Items 

Posted: Sun Sep 18, 2005 12:05 am Post subject: 


The requirement for 2+ candidate cells is only there because if you have just 1 candidate, you have a hidden single. Assuming you've solved for all singles, any subset operation will always be based on 2+ candidates. This is why the swordfish situation never comes up in a case like you described, because the F is pinned before an Xwing on ABCD would ever be tried.
If squirmbag is just a 5col/row swordfish, then it doesn't exist in a 9x9 sudoku grid. Because Xwing, swordfish, and these other forms are all just a positional form of naked/hidden subsets, a 5column squirmbag is equivalent to a 4row jellyfish, or perhaps a lesser number of rows like 2 or 3 which is more common. This is by the same logic that equates a naked triple in 5 candidates to a hidden pair. If you have only have two of a particular digit locked down, leaving you 7 candidate columns and rows, and a 5column squirmbag exists in those 7, then you can just as easily (actually more easily) find an Xwing in the 2 rows left out of the squirmbag.
This is what I mean when I say this is a positional form of the subset rule: Naked and hidden subsets both operate on a binary graph of candiate digits and positions within a house. Observe the following:
Code:  digit
p 1 2 5 6 7 9
o
s 2 X X X
i 4 X X X
t 5 X X X
i 7 X X X X
o 8 X X
n 9 X X X 
What we have here is a hidden subset, where 2, 6, and 7 appear only in positions 2, 4, and 7. If you take only those 3 columns, you get only 3 active rows. However you can use this same graph with different values to find naked subsets. All you have to do is look for rows instead of columns.
Xwing and swordfish are the same thing because you can change the labels on the graph. Skipping over any cols/rows where the target digit is accounted for, label the graph with any columns and rows where you aren't sure of the digit's position, and put an X in where any candidates may occur.
If the code you use to solve for pairs, triples, etc. is robust enough, it should be easy to modify to use in this way. If not, I posted an algorithm that should handle the subset solving for you as long as you give it a table of bitwise values to work with. 

Back to top 


 Nick67
 Joined: 08 Sep 2005  Posts: 5  :  Location: Sacramento, CA  Items 

Posted: Sun Sep 18, 2005 12:29 am Post subject: 


Quote: 
AFAICT, the more general definition seems to be:
Look for N columns (2 for Xwing, 3 for the Swordfish, 4 for a Jellyfish, 5 for a Squirmbag) with 2 to N candidate cells for ONE given digit. If these fall on exactly N common rows, then all N rows can be cleared of that digit (except in the defining cells!). The test can also be done swapping rows for columns.

I like your revised definition.
For what it's worth, here is an informal proof:
Code: 
* Let's call the selected candidate value "X".
* In the puzzle solution, X must
appear in exactly 1 cell in each of the
N columns in the pattern.
So, these cells form a group (let's call it "G") of exactly N cells
within the pattern.
* All pattern cells are located
inside a set of N rows. Let's call this set "S".
* Each of the cells in G must be on a different row in S.
* So there must be exactly 1 cell from group G
in each row in S.
* Therefore, we can eliminate X as a candidate
for all cells outside the pattern in each row in S.

Quote: 
It seems to me that you could actually look for columns with 1N candidate cells (ie: includes solved cells), but if you find, say, a swordfish with such a cell, it degenerates to an xwing.
 .
I agree with "1 to N" instead of "2 to N".
Then, your patternfinder could recognize patterns
containing singles. I would guess that most solvers
recognize singles before looking for such patterns,
but that doesn't seem to be necessary.
Quote: 
Note also that the requirement "and each of those rows has at least 2 candidate cells" seems to be extraneous.

I agree. There seems to be no reason to make this additional check.
(For example, the proof above does not depend on this condition). 

Back to top 


 MadOverlord
 Joined: 01 Jun 2005  Posts: 80  :  Location: Wilmington, NC, USA  Items 

Posted: Sun Sep 18, 2005 12:37 am Post subject: 


Lummox JR wrote:  The requirement for 2+ candidate cells is only there because if you have just 1 candidate, you have a hidden single. Assuming you've solved for all singles, any subset operation will always be based on 2+ candidates. This is why the swordfish situation never comes up in a case like you described, because the F is pinned before an Xwing on ABCD would ever be tried. 
OK, that means it's safe for me to use the more generalized code (as in the example above). The reason I need to do so (apart from it making the code simpler) is that in the Sudoku Susser, it's possible for people to turn rules on and off, so someone might run the rule before the simpler reductions have been done.
Quote:  If squirmbag is just a 5col/row swordfish, then it doesn't exist in a 9x9 sudoku grid. 
Right, you'll never see it during an allrules deduction. But I've added it for completeness. I've got a generalized find_wing routine that takes a parameter N=2 (xwing), 3 (swordfish), etc., so it's no trouble to mention squirmbags. Are there names for N=6,7,8 patterns?
Quote:  If the code you use to solve for pairs, triples, etc. is robust enough, it should be easy to modify to use in this way. If not, I posted an algorithm that should handle the subset solving for you as long as you give it a table of bitwise values to work with. 
Right, it immediately became clear to me that I could crib my "comprehensive locked set" code to find these patterns. Instead of having a 9square row of possibility bitmaps, you have, for each possibility, a set of bitmaps that show what squares in the row have that possibility. Then it's just find a union of N rows that has N bits set (or viceversa for columns)
One other sideeffect was that I was able to add code to the FishyCycles routine to identify the simpler subpatterns and mention what they were. If you have a 2edge fishy cycle where all the edges are rows and all the vertexes are columns (or viceversa), that's a simple Xwing. A 3edger with the same constraints is a swordfish. And a 2edger that fails the constraints is a generalized Xwing as per http://users.pandora.be/vandenberghe.jef/sudoku/index.html?how2solve 

Back to top 


 xyzzy
 Joined: 24 Aug 2005  Posts: 80  :   Items 

Posted: Sun Sep 18, 2005 2:32 am Post subject: 


Quote:  I agree. There seems to be no reason to make this additional check.
(For example, the proof above does not depend on this condition). 
The two or more is just an optimization of the algorithm's implimentation. Most human and computer solvers will search and find singles (N=1) before they search for pairs/xwings (N=2). In this case, every row in an Xwing/swordfish/etc. will have at least two candidate cells. It's not that the rows need to have at least two, just that they will, and so rows with one candidate can be excluded from the search.
It's easy to optimize the searcha bit more. If you're searching for a group of N rows, then you know that each row will have between 1 and N candidate cells. e.g. if you're searching for Xwings you don't need to consider rows with 3 cells, they can't be in an Xwing. 

Back to top 


 MadOverlord
 Joined: 01 Jun 2005  Posts: 80  :  Location: Wilmington, NC, USA  Items 

Posted: Mon Sep 19, 2005 5:53 am Post subject: 


BTW, are there any defined names for higherorder patterns (ie: 6x6, 7x7, 8x8, 9x9) or are they even possible?
If a 9x9 is possible, I reckon we should call it a Cthulu... 

Back to top 


 xyzzy
 Joined: 24 Aug 2005  Posts: 80  :   Items 

Posted: Mon Sep 19, 2005 9:45 am Post subject: 


MadOverlord wrote:  BTW, are there any defined names for higherorder patterns (ie: 6x6, 7x7, 8x8, 9x9) or are they even possible?
If a 9x9 is possible, I reckon we should call it a Cthulu... 
N=9 isn't possible unless your grid is completely empty with no known cells at all. And even then, once you find the pattern you remove the possibilities from every row (or column) not in the pattern. If the pattern has nine rows, then there aren't any rows not in it, and so you remove nothing.
Patterns with N>4 rows exist of course, but aren't necessary, as a corresponding pattern of size 9N exists in columns.
For example, in this grid X, +, and * are places a certain digit can go, while . represents places it can't.
Code: 
a b c d e f g h i
1 X . X . . . . . .
2 X . . . X . . . .
3 . . . + . . . + +
4 X . X . X . . . .
5 . . * . . . . . +
6 . + . . . . . + .
7 . . . . * + + . .
8 . + * + . + . . .
9 . . . . * . + . .

There is a N=3 locked set with rows 1, 2, and 4 (the X's). Row 1 can be in columns {ac}, row 2 in {ae} and row 4 in {ace}. The union of these sets is {ace} which has three columns in it for three rows. So we can remove as a possibility the columns {ace} from all the rows other than {124}, which are the cells with *'s.
There is also a locked set with size N=6 with the columns b, d, f, g, h, and i (all the +'s). These are the columns that weren't used in the previous locked set. Column b can has rows {68}, column d has {38}, and so on. The union is the rows {356789}, which are all the rows that weren't in the N=3 locked set. This means we can remove the rows {356789} from the columns that aren't {bdefgi}. Which is, again, all the *'s.
So there's really no point in naming N=5 or more, because there always exists a corresponding pattern with N<5 that does the exact same thing. 

Back to top 


 DHallman
 Joined: 09 Aug 2005  Posts: 24  :  Location: Inglewood, CA 90302 USA  Items 

Posted: Tue Oct 11, 2005 2:00 am Post subject: Why cant I use a sword 3fish 


Angus,
After many steps Simple Sudoku gives me the following filter on 4s:
Code: 
... ... ...
... bxb .b.
... .4. .b.
... b.b 4..
... .4. 4..
... ... ...
... bxb .B.
... ... ...
... ... ...

where b is my column bbb bbb
and B is the extension of bb
and x to be excluded
Why do you allow 7,5 to be excluded but not 2,5?
BTW how can I copy your image.png into here? I see others doing it.
The saved file is:
Code: 
**
654.9....
..1...9.5
.8....6..
++
....6..31
...2.5...
46..8....
++
..9....6.
7.8...1..
....3.594
**
I746
I702
I713
I644
I675
E75001
E77011
E77002
E57007
E59017
E57008
E59018
E58007
I553
I545
I189
E53002
E44007
E53017
I539
I446
I525
I063
I379
I215
I295
E43004
E47003
I361
I731
I278
I093
I233
I483
I383
I722
I501



Back to top 


 angusj Site Admin
 Joined: 18 Jun 2005  Posts: 406  :   Items 

Posted: Tue Oct 11, 2005 9:42 am Post subject: Re: Why cant I use a sword 3fish 


DHallman wrote:  After many steps Simple Sudoku gives me the following filter on 4s 
I certainly don't understand your b's an B's.
Anyhow this is what I get when filtering on 4's (and it certainly isn't the way forward so I don't see why you might be interested in them):
DHallman wrote:  BTW how can I copy your image.png into here? I see others doing it. 
1. Save the image to file (File  Save Image As) in SS.
2. Upload the image here  http://www.imageshack.us/
3. Copy the "direct link" given by imageshack into your post enclosed in IMG tags.
nb: Don't paste images here unless you think it'll help illustrate your problem (or solution) as it's much easier to copy and paste the text representation of the puzzle into SS than manually copying each given from an image. 

Back to top 


 DHallman
 Joined: 09 Aug 2005  Posts: 24  :  Location: Inglewood, CA 90302 USA  Items 

Posted: Tue Oct 11, 2005 7:09 pm Post subject: Re: Why cant I use a sword 3fish 


Angus,
I normally highlight (mark) in blue the rows or columns of fish so I can better see them. b indicated actuak 4s and B the extension in c
I had eliminated the 4 at r5c8 and somehow at r3c4 & r3c6. Thus arriving at a swordfish using c4,c6 & c8. Which should have allowed me to eliminate r2c5 & r7c5. What did I do wrong? 

Back to top 


 Nick67
 Joined: 08 Sep 2005  Posts: 5  :  Location: Sacramento, CA  Items 

Posted: Wed Oct 12, 2005 6:56 am Post subject: 


I think you may have an offbyone error here:
Code: 
... ... ...
... bxb .b.
... .4. .b.
... b.b 4..
... .4. 4..
... ... ...
... bxb .B.
... ... ...
... ... ...

Consider the b in r3c8 ... it does not share a row
with other b's. So the group of b cells is not quite
a swordfish (... but it would be if that same b was
in r4c8 instead). 

Back to top 


 DHallman
 Joined: 09 Aug 2005  Posts: 24  :  Location: Inglewood, CA 90302 USA  Items 

Posted: Wed Oct 12, 2005 6:25 pm Post subject: Re: Why cant I use a sword 3fish 


Nick67,
Thank you. I did not realise that a fish had to have all rows AND
columns occupied when present. Ie no stragglers except for extensions for shorter rows (or columns). 

Back to top 


 DHallman
 Joined: 09 Aug 2005  Posts: 24  :  Location: Inglewood, CA 90302 USA  Items 

Posted: Wed Oct 12, 2005 6:55 pm Post subject: 


Nick67 wrote:  Quote: 
AFAICT, the more general definition seems to be:
Look for N columns (2 for Xwing, 3 for the Swordfish, 4 for a Jellyfish, 5 for a Squirmbag) with 2 to N candidate cells for ONE given digit. If these fall on exactly N common rows, then all N rows can be cleared of that digit (except in the defining cells!). The test can also be done swapping rows for columns.

I like your revised definition.
Quote: 
It seems to me that you could actually look for columns with 1N candidate cells (ie: includes solved cells), but if you find, say, a swordfish with such a cell, it degenerates to an xwing.
 .
I agree with "1 to N" instead of "2 to N".
Then, your patternfinder could recognize patterns
containing singles. I would guess that most solvers
recognize singles before looking for such patterns,
but that doesn't seem to be necessary.
Quote: 
Note also that the requirement "and each of those rows has at least 2 candidate cells" seems to be extraneous.

I agree. There seems to be no reason to make this additional check.
(For example, the proof above does not depend on this condition). 
Nick,
Your last statement above does not seem to agree with your last post re my problem.
Quote: 
Code:
Code: 
... ... ...
... bxb .b.
... .4. .b.
... b.b 4..
... .4. 4..
... ... ...
... bxb .B.
... ... ...
... ... ...

I had eliminated the 4 at r5c8 and somehow at r3c4 & r3c6. Thus arriving at a swordfish using c4,c6 & c8. Which should have allowed me to eliminate r2c5 & r7c5. What did I do wrong? 
I am now confused. 

Back to top 


 angusj Site Admin
 Joined: 18 Jun 2005  Posts: 406  :   Items 

Posted: Wed Oct 12, 2005 10:35 pm Post subject: 


DHallman wrote:  I am now confused. 
Nick67 is correct, your b's don't line up to make a swordfish.
You appear to have missed an important condition of swordfish. Here's my definition here: http://www.angusj.com/sudoku/hints.php#swordfish .
Looking at your grid, it satisfied only half the conditions required  ie three columns each contain three 4s, but the candidates in these columns are in more than three rows (rows 2,3,4 & 7). 

Back to top 


 DHallman
 Joined: 09 Aug 2005  Posts: 24  :  Location: Inglewood, CA 90302 USA  Items 

Posted: Wed Oct 12, 2005 11:05 pm Post subject: Re: Why cant I use a sword 3fish 


Nick & Angus,
Thank you for the definitions.
I did not notice that all marked candidates had to be in the same rows.
I'll hope to do better and not get any more invalid moves. 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
