Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Understanding Swordfish
Goto page Previous  1, 2, 3
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Miles

Joined: 29 Dec 2005
Posts: 30
:

Items
PostPosted: Mon Feb 13, 2006 9:10 am    Post subject: Reply with quote

Ruud wrote:
Miles wrote:
Depending on the definition, you can replace exactly by at most

Each row involved can have candidates in 2 or 3 columns, but it is essential that the 3 rows together have candidates in exactly 3 columns, because when there are less, you have a serious problem completing the sudoku.
Ruud.

OK, I agree Very Happy
Back to top
View user's profile Send private message Visit poster's website
swizzle

Joined: 08 Mar 2006
Posts: 1
:
Location: UK

Items
PostPosted: Wed Mar 08, 2006 5:50 am    Post subject: Re: Understanding Swordfish Reply with quote

AndyT wrote:
Guys, I'd appreciate some help understanding the Swordfish technique. .... He excludes a 5 at R1C4 but not at R3C4. Why?


The 'penny dropped' for me when I visualised Swordfish as interconnecting 'lines of force' rather than isolated cells (apologies if this method has already been explained better elsewhere).
Using the example given, where a Column-based Swordfish has been identified:

1) Draw vertical lines through the Swordfish Columns (Columns 2, 5 & 8 in the example).

2) Now draw horizontal lines through any Rows which have a candidate cell with a line through them (Rows 1, 4 & 9 in the example).

3) The candidate can be eliminated from any cell which only has one line through it.
(Some candidate cells will have two lines, and some candidate cells may not have any lines (e.g. R3C4 in the example) - these cannot be eliminated.)

Notes:
Because the Swordfish pattern was identified in Columns, there won't be any cells in Columns 2, 5 or 8 to eliminate (otherwise you wouldn't have had a valid Swordfish pattern in the first place).
A Column-based Swordfish only eliminates candidates in Rows.
A Row-based Swordfish only eliminates candidates in Columns.

AndyT also asked "why was column 4 not considered at the start?"
Column 4 is worth considering because it only has three candidate cells in Rows 1, 3 and 7. But it can be discarded because there aren't two other Columns which only have candidates in Rows 1, 3 or 7.

Hope this helps,
Swizzle
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Wed Mar 08, 2006 2:34 pm    Post subject: Reply with quote

It seems the filet-o-fish (including finned swordfish) haven't made their way to this forum yet. Surprised

Ron
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Mar 08, 2006 9:49 pm    Post subject: Reply with quote

rkral wrote:
It seems the filet-o-fish (including finned swordfish) haven't made their way to this forum yet.

Hi Ron,

Maybe we could discuss this in the "programming sudoku" forum. I had a lot of trouble looking for a compact way to program the finned X-Wing into SudoCue. Though it works now, I am not happy with the way it looks. And I haven't even started the finned swordfish yet...

Has anyone got this programmed in a neat generic way, including the Sashimi observation types? And if so, would that person come forward and share some pseudo-code with us?

Ruud.
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Thu Mar 09, 2006 4:18 am    Post subject: Reply with quote

rkral wrote:

Maybe we could discuss this in the "programming sudoku" forum. I had a lot of trouble looking for a compact way to program the finned X-Wing into SudoCue. Though it works now, I am not happy with the way it looks. And I haven't even started the finned swordfish yet...

Has anyone got this programmed in a neat generic way, including the Sashimi observation types? And if so, would that person come forward and share some pseudo-code with us?

Before getting deep in a discussion can we compile a taxonomy of puzzles that illustrate the techniques? The puzzles could be manipulated to exibit the technique on the next move. This would be a boon to those who care less about cute names and more about underlying structure. It might also provide a basis for identifying similar techniques with dissimilar names.

Putting the taxonomy in one place (or topic) would be more convenient than scraping puzzles from the forums one message at a time -- maybe something similar to the sticky technique index.
Back to top
View user's profile Send private message Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Thu Mar 09, 2006 9:20 am    Post subject: Reply with quote

gsf wrote:
rkral wrote:

...
I had a lot of trouble looking for a compact way to program the finned X-Wing into SudoCue.
...

You quoted Ruud, not me.

gsf wrote:
Before getting deep in a discussion can we compile a taxonomy of puzzles that illustrate the techniques?...
Putting the taxonomy in one place (or topic) would be more convenient than scraping puzzles from the forums one message at a time -- maybe something similar to the sticky technique index.

Sounds like a good idea to me. Ruud, since you're apparently the only one of the three of us that has programmed this technique, I think you should be the one to author a thread on the 'programming sudoku' forum. I'll definitely attempt to contribute.

Ron
Back to top
View user's profile Send private message
AndyT

Joined: 27 Jan 2006
Posts: 15
:
Location: Hong Kong

Items
PostPosted: Mon Mar 27, 2006 11:45 am    Post subject: Reply with quote

Just when I felt there was a chance that I might be "getting" Swordfish, it seems I don't.

So guys, my logic is flawed here, perhaps you can explain a) why and b) what it should be?



Why does the Swordfish on 9s in the right hand boxes not remove the 9 option from R7C1 and R9C8?

Thanks, Andy
Back to top
View user's profile Send private message
vidarino

Joined: 10 Feb 2006
Posts: 38
:
Location: Haugesund, Norway

Items
PostPosted: Mon Mar 27, 2006 11:49 am    Post subject: Reply with quote

Well, it's not a Swordfish, that's why. Smile

The 9 in R9C8 actually prevents it from being one. If it hadn't been there, you would have three columns (7, 8, 9) that combined had 9s in only three rows (1, 5, 7).

In your example above, the three columns have 9s in a total of *four* rows, row 9 being the showstopper.

For this reason, a Swordfish only has eliminations in one "direction". If it's a column-based fish, like the almost-one above, it will eliminate other 9s in its own rows. If there were any eliminations in the columns - then you wouldn't have a fish in the first place.

Vidar
Back to top
View user's profile Send private message Visit poster's website
AndyT

Joined: 27 Jan 2006
Posts: 15
:
Location: Hong Kong

Items
PostPosted: Mon Mar 27, 2006 11:53 am    Post subject: Reply with quote

So I can have 4 columns but only 3 rows?
Back to top
View user's profile Send private message
vidarino

Joined: 10 Feb 2006
Posts: 38
:
Location: Haugesund, Norway

Items
PostPosted: Mon Mar 27, 2006 12:01 pm    Post subject: Reply with quote

AndyT wrote:
So I can have 4 columns but only 3 rows?


The pattern needs to be confined to either 3 rows or 3 columns. The other direction doesn't matter.

The logic is this; (copied from another posting of mine)

Quote:
Put short; In any NxN sized (N=2 is X-Wing, 3 is Swordfish, 4 is Jellyfish) pattern, there are only so many ways you can arrange the numbers;

Code:
X..  X..  .X.  .X.  ..X  ..X
.X.  ..X  X..  ..X  X..  .X.
..X  .X.  ..X  X..  .X.  X..


In either of these combinations, there exists one X in every vertical column involved, which would eliminate them from the columns outside of the NxN grid, even if we don't know exactly which of the patterns is the correct one.


HTH

Vidar
Back to top
View user's profile Send private message Visit poster's website
LB2064

Joined: 03 Mar 2006
Posts: 3
:

Items
PostPosted: Tue Mar 28, 2006 11:05 pm    Post subject: Reply with quote

AndyT wrote:
So I can have 4 columns but only 3 rows?


Hi Andy. Let's see if another non-technical person’s explanation can help you. You need to decide it you are starting with rows or columns.

Let's say we start with rows. Then the steps are:
For the candidate of interest -

A. Using Rows
a) Pick 3 rows of cells.
b) The cells in these rows must fall nicely into 3 columns.
c) To complete the swordfish, none of the cells from the rows can be alone in a column (see Note 1 at the end of this post).
d) Once we have the swordfish pattern, then any other cell within the columns that have the candidate and are not part of the original cells picked in the rows (part a) can have the candidate eliminated.

B. Using Columns.
Just substitute columns for rows and vice versa in (A).

Your example:
Okay - Let's look at the example you posted on Monday March 27th.
a) You have three rows of cells for candidate 9 in Rows: 1, 5, and 7.
b) The cells fall in 4 columns: Column 1, 7, 8, 9. So this criteria is violated and this pattern is not a swordfish because the cells must fall in 3 columns.
c) There is only one cell in column 1, again violating the swordfish pattern
d) We cannot use your pattern to eliminate candidates because we do not have a swordfish pattern.

Another Example:
Below is a swordfish pattern based on rows for Candidate 8.



Let’s go through the criteria I mentioned above to see why it is a sword fish.

a) Three rows of cells have been selected: Rows 4, 6, and 9.
b) All the cells within these three rows fall nicely into 3 columns: Columns 1, 5, and 7
c) None of the columns formed by the cells from the rows have only one cell in the column so we have completed the swordfish pattern.
d) Since the above three criteria (a, b, and c) have been met, we can now proceed to eliminate candidate 8 from any cells that are not part of the original row cells but that lie in the path formed by the three columns. So we can eliminate the yellow highlighted cells in the diagram.

I hope this helps.

LB

[Note 1: I am adding this clarifying note based on an interesting comment by sgerrard in a follow-up post as to whether a sword fish pattern can have a single candidate in a line. In my part (c) - what I have described here is how I find a swordfish "after solving for things like naked & hidden candidates and x-wing patterns." As to the technicalities of whether a swordfish pattern can contain only one candidate cell in a line; I would have to defer to the pundits on this site, but I have not seen it defined that way in any of the references I have read. An interesting discussion on this topic can be found elsewhere on the forum:
http://www.setbb.com/sudoku/viewtopic.php?t=240&mforum=sudoku ]


Last edited by LB2064 on Thu Mar 30, 2006 4:57 pm; edited 1 time in total
Back to top
View user's profile Send private message
sgerrard

Joined: 29 Mar 2006
Posts: 4
:
Location: Oregon USA

Items
PostPosted: Wed Mar 29, 2006 6:54 am    Post subject: Reply with quote

LB2064 wrote:

A. Using Rows
a) Pick 3 rows of cells.
b) The cells in these rows must fall nicely into 3 columns.
c) To complete the swordfish, none of the cells from the rows can be alone in a column.


I'm not sure I agree with c.
In your example, suppose r6c5 was not a candidate 8, leaving only one 8 in column 5.
If you don't call it a swordfish, then you call it an x-wing in rows 6 and 9. This would eliminate other candidates in columns 1 and 7, leaving a hidden single in r4c5. That in turn would eliminate other candidates in column 5.
The result is identical to what you would get if you had called it a swordfish. You would probably identify the x-wing and the single before finding the swordfish, but I don't see anything wrong with a swordfish where one of the cells from the rows is alone in the column.
Back to top
View user's profile Send private message
LB2064

Joined: 03 Mar 2006
Posts: 3
:

Items
PostPosted: Wed Mar 29, 2006 9:42 pm    Post subject: Reply with quote

sgerrard wrote:
.....In your example, suppose r6c5 was not a candidate 8, leaving only one 8 in column 5. If you don't call it a swordfish, then you call it an x-wing in rows 6 and 9........


Hi sgerrard – an interesting scenario. However, if you remove candidate 8 from r6c5, then you have redefined the puzzle which now yields a hidden single in r4c5 which when solved also reduces the modified puzzle to the x-wing pattern. Essentially, you have a different puzzle from what I posted, and for me, I would not have come across a swordfish pattern in that instance because I would have found the hidden single first - at least I hope I would have. Smile

What I have described in my post is how I find a swordfish (after solving for things like naked & hidden candidates and x-wing patterns.). As to the technicalities of whether a swordfish can contain only one candidate cell in a line; I would have to defer to the pundits on the site, but I have not seen it defined that way in any of the references I have read.

There is actually an interesting discussion on this topic elsewhere on the forum:

http://www.setbb.com/sudoku/viewtopic.php?t=240&mforum=sudoku

Thanks.
_________________
LB
Back to top
View user's profile Send private message
rantinori

Joined: 29 Jan 2006
Posts: 3
:
Location: US

Items
PostPosted: Wed Sep 27, 2006 3:12 pm    Post subject: Reply with quote

I would like to make an observation:

A Swordfish, as defined above, must have more than one of the Swordfish candidate in each of the shared rows (or columns). Otherwise the Swordfish pattern dissolves to an X-Wing. And that X-Wing would eliminate one or more of the candidates in the other two shared rows leaving the candiate in the row with the single candidate as the value for that cell.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page Previous  1, 2, 3
Page 3 of 3

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron