The password is... Swordfish!

Finally the time has come to explain the Sudoku Swordfish rule!  I've noticed this is one of the most popular search terms leading to this blog, so I'm happy to be able to help out.

Consider this board:

Following elimination, we reach the position below.  I've highlighted some areas in red.  In row 5, there are two places where we can place a 9, in columns 4 and 6.  In row 7, 9 can appear in columns 4 and 9 only, and in row 9 it can appear in columns 6 and 9 only.

The curved red lines show how the cells involved in the swordfish form a kind of loop.  Placing a value in one of the cells implies its positions in the rest of the loop. Suppose the 9 in row 5 appears in column 4, that is, in cell (4, 5).  Then cell (6, 5) can't contain a 9, so cell (6, 9) must (because it's the only other place in column 6 than can).  That implies that (9, 9) can't contain a 9, so (9, 7) must.  Alternatively, if the 9 in row 5 appears in cell (6, 5), following things around the loop we see that 9's must also appear in cells (9, 9) and (4, 7).  Either way, we've placed a 9 in each of the three columns 4, 6, and 9.  We can eliminate any other possible 9's in those columns, namely the ones highlighted in blue.

Another way to see things is to notice is that there are three 9's to be placed in three rows (5, 7, and 9), and exactly three columns (4, 6, and 9) intersecting those rows where they can be placed.  Each column must receive a 9 in one of the three rows.

The swordfish can also appear in a vertical orientation.  In this case, we notice three columns that each can take a given number only in two places.  Between the three columns, the places that can hold that number fall into exactly three rows.  The board below provides an example:

I've highlighted the vertical swordfish (on the number 3) in the grid following eliminations:

The 3's can be removed from rows 4, 6, and 7 (outside of columns 1, 4, and 9 that make up the swordfish).

A swordfish could also involve three rows (or columns) that each have the same three possible places for a number.  Say the value is placed in the upper-leftmost cell of the pattern; then the lower-left cell (which lies in the same column) can no longer hold the value.  The remaining cells form an X-Wing pattern.  The same X-Wing appears if the value belongs in the lower-leftmost cell.  I'll try to come up with an example of this type of swordfish in the near future.

So, to summarize, the pattern consists of three rows, and a total of three columns within those rows where a given value can be placed.  The value can be removed from the remainder of those columns.  The same rule applies if the words "row" and "column" are switched.

I hope this helps to clarify the Swordfish rule!

Technorati Tags:Su Doku Sudoku

Comments

[Matt]

The coordinates you use in the example of the swordfish do not seem to make sense. I'm trying to learn how to apply the swordfish technique to a su doku puzzle. You say that column 4 row 5 is (4,5) and if that cell contains a nine then (4,6) can't contain a 9 and cell (4,9) must. However, cell(4,6) and (4,9) both cannot contain 9's not just because there is a 3 located in (4,6) based on your coordinates and a 1 in (4,9) but also because you can't have two 9's in column 4. I'm fairly sure its just a labeling/typing error you made unless there's something i'm overlooking. Anyway, thanks for the help on the x-wings and the grids. Hopefully you can fix this soon to make it easier to understand.

Matt

[Dan Rice]

Thanks, Matt, I have made some changes and hopefully things should be fixed now. -Dan

[Patrick Forsberg]

The first swordfish starts off after elimination. But it seems to me that the elimination missed that box 7 (lower left) can only hold a 9 in (2,8) and therefor we can elmininate the blue 9's in (4,8) and (9,8) and thus making the whole swordfish moot.

/Patrick

[Daniel Rice]

Hi Patrick -

You are quite right -- the 9 can be placed in box 7 using the "eyeball" rule, so the first Swordfish is not necessary. The rules that are used in a given puzzle will always depend on the order in which they are applied. Arguably, a complex rule like Swordfish should be saved until all other options have been exhausted, since it can take a lot of work to find one.

My program missed this because it applied only the rule of elimination to cross out numbers. Strictly speaking, it is the rule of uniqueness that would allow the 9 to be placed, by observing that there is no other place for it in box 7.

Thanks for your comment!

[Larry]

I don't understand in your second example (with the swordfish in columns 1, 4, 9) why column 7 can't be part of the swordfish since it has 3's in the same 3 rows?

Thanks

[tom]

I didnt understand your explanation of the vertical and horizontal swordfishes or why they worked. Could you describe them in detail?

[chris]

To Larry from 9/28/05: If I understand correctly, I believe you have to start with columns that have only (exactly) 2 occurrences of the number.

[Ernesto]

maybe a good example for the last point

3-1 958 -6-
*-8 *-4 5*1
*-4 2-- 3*8
*4- *-9 8*6
61- 8-5 -39
8-9 6-- -1-
--- --6 9--
296 4-- 1--
-8- -9- 6-7 * = swordfish(7)

[Monica]

Dear Dan, Just out of curiosity, how long did u take to solve the above Sudoku ? Monica

[Gunter]

"Alternatively, if the 9 in row 5 appears in cell (6, 5), following things around the loop we see that 9's must also appear in cells (9, 9) and (4, 7). "

Why? (6,5) -> (9,9) But (4,7) and (4,8) are both valid, looking only at the 9s.

[martine]

Your X Wing and the Swordfish example
both contain candidates that appear more than twice , making these candidates invalid and removable !

Your explanation of X-Wing, SwordFish is very clear, and your examples that include invalid candidates are the best I have seen so far.
++++++++++++++++++++++++
On another subject: Now that I can understand sudoko...I am curious:

1. Is the level of diffculty programmed into a puzzle

OR

must huge nymbers of computer programmed puzzles be solved in order to locate
the most difficult puzzles
that require X Wing and Swordish ?

2. Are there computer programs that can solve
sudoko without human intervention ?

martine