Xwings, Swordfish, Jellyfish, Squirmbags


If nothing else, Sudoku solvers have imagination when they name techniques!

This idea is completely analogous, logically, to pairs, triplets, etc.  Forbidding matrices expose this analogy.

Here is the idea as an X wing:

  • Consider any one candidate
  • Consider any two distinct rows
  • Let the candidate be limited to no more than two cells in each of these two rows
  • Let this group of no more than 4 cells share exactly two columns
  • The candidate is forbidden from all the cells in those two columns outside of those 4 cells
Because of symmetry, one can exchange columns for rows in this rule.

Xwing example


Xwing on 3's

Note the following:

  • All possible locations for 3's in row 9 are f9,h9.
  • All possible locations for 3's in row 5 are f5,h5.
  • Forbids 3 from f4,f8,h4,h6.
This step could be presented in a puzzle proof as follows:
  • xwing on 3's at fh59 forbids f48,h46=3.
It should be clear that, for example, f4=3 is impossible. If f4=3, then in order for rows 5,9 to have any threes, both h5=3 and h9=3. Since h5,h9 are both in column h, one concludes f4=3 is forbidden by the rules.

This idea extends easily:

  • Consider any one candidate
  • Consider any N distinct rows, N>0.
  • Let the candidate be limited to no more than N cells in each of these N rows
  • Let this group of no more than N^2 cells share exactly N columns
  • The candidate is forbidden from all the cells in those N columns outside of those N^2 cells
Because of symmetry, one can exchange columns for rows in this theorem.

With N=1, we have the trivial case of a Unique Possibility. With N=2, we have a standard X wing. With N=3, we have a swordfish. With N=4, we have a jellyfish. with N=5, the creative name squirmbag is used. To prove this technique, I prefer to use induction.

This technique merely crosses the possible locations of a candidate in N rows with N columns. It is analogous to an Ntuple, which crosses the possible locations within a large container of N candidates with N cells.

The analogy can be extended further. For example:

  • If an Xwing in exists for candidate N with respect to columns
  • Let M be the number of locations for candidate N that are not yet fixed.
  • There exists a fish of size (M-2) with respect to rows
This compares with: If you find a hidden pair in a large container, there exists a naked (M-2) tuple in that large container.

Swordfish Example


Swordfish on 5's

In this example, the possible locations for 5's are highlighted in green. The darker green cells form the swordfish. In this example, the swordfish is missing 5's at c6,d4. This is common with swordfish, and does not effect the possible eliminations. In the example, we have:

  • 5's in row 6 limited to d6,i6
  • 5's in row 4 limited to c4,i4
  • 5's in row 3 limited to c3,d3,i3
  • Forbids 5 from: c8,d1,d2,d5,d7,d8
The following table proves the validity of these eliminations:

 d6=5i6=5
c4=5 i4=5
c3=5d3=5i3=5
In this table,
  • Each row has at least one item that must be true, by examination of the puzzle grid
  • Each column has no more than one item that can be true, by the rules of the game (no need to consult the grid)
Conclusion:
  • The table has at least three truths (at each row)
  • The table has no more than three truths (at each column)
  • Thus, the table has exactly three truths
  • Further, each table column has exactly one truth
One can now clearly see that, for example, c8=5 is forbidden. In fact, c125789,d125789,i125789=5 are all forbidden.

The table above could also be called a forbidding matrix. There is more than one type of such a matrix. Credit for the matrix idea belongs to Andrei Zelevinsky and Bruno Greco (gb). It should be noted, however, that my presentation of the idea of forbidding matrices lacks their strict mathematical precision.




16 Comments
Indicate which comments you would like to be able to see

Thanks for presenting the techniques in easy to understand format and language
 |  |
Thanks for explaining this! I think I have used the Xwing rule sometimes, just didn't know what the community calls it. The generalization is nice. Wish I could spot these easily on actual puzzles :)

A simpler but similar rule makes an appearance on 16x16 sudokus very frequently. Say, I More...
 |  |
Thanks for a good Christmas present. I will enjoy working on this after the holidays when everything and everyone is quiet.
 |  |
Steve, thanks so much for explaining this. I used an xwing by myself, no help, for the first time today! I am looking forward to getting better at these tough puzzles. Thank you, thank you, thank you.
 |  |
Feel free to ask any questions that you may have about a technique, even if it is not the one being discussed. I will generally check for questions periodically.
 |  |
after solving tough sudoku 22 dec,the position obtained is(figures betwen commas are possibilities)-pl advise how to proceed further without guessig or hit/trial:
8,17,3,56,169,59,67,2,4
5,47,9,2,46,8,3,67,1
1 4,2,6,7,14,3,5,89,89
13469,14569,7,1346,8,249,246,456,356
More...
 |  |
can i treat the 7's at b8,h8 &f4,h4 as X-wing?
 |  |
Hi ang!
I will later look at the exact puzzle position that you have listed. But, for now I can tell you:
7's at b8,h8 and f4,h4 will never form an X wing.

In order to have a true X wing (as opposed to a finned X wing) - one must have alignment in both rows and columns. Therefor, More...
 |  |
Hi ang!
I have now looked at the puzzle condition that you posted. The proof I presented on that date works from the situation you described. Here are the relevant proof portions:

6b) b3=4 == b3=5 -- bc2=5 == d2=5 -- d9=5 == d9=6 -- e8=6 == e8=4 forbids b8=4 UP 51
7) Pair 24 at cf4 More...
 |  |
Now, to explain what the terminology means:
Eventually, the blog will detail the ideas above with precision. On a temporary basis, consider the following:
6b) b3=45; 5's in row 2 are limited to bc2,d2; d9=56; e8=46. If b3=4, then b8<>4. If b3<>4, then b3=5 => bc2<>5 More...
 |  |
Hi Steve,

Thanks for you blog. I've puzzled away trying to work things out myself... I do like that challenge.

gb's explanations assisted me to understand the board positions and a FC but I guess I've never fully understood an Xwing or Swordfish... (still have to put in some More...
 |  |
Hi Fi!
Great to hear from you! I remember well some of the solutions that you posted.

Eventually, I will get around to explaining the more efficient and in most ways, better - language of forbidding chains. For better or worse, I have modified gb's usage of this language to one that is More...
 |  |
Hi Steve,

Did I miss a definition for squirmbags?
 |  |
Hi Steve,
Thank you so much for the detailed explanation.I will keenly look forward to further posts on the blog page.
Meanwhile,wishing you a merry christmas and a happy 2007 !
 |  |
Thanks Josh!
I did omit the definition for that wonderful named entity. I have modified the page to correct that mistake.
 |  |
Can someone please tell me why D1 and D2 cannot be '5's' in the example above?
22/Jan/12 9:33 AM
 |  |
Please Log in to post a comment.

Not a member? Joining is quick and free.
As a member you get heaps of benefits.
Click Here to join.
You can also try the Chatroom (No one chatting right now - why not start something? )
Check out the Sudoku Blog     Subscribe
Members Get Goodies!
Become a member and get heaps of stuff, including: stand-alone sudoku game, online solving tools, save your times, smilies and more!
Previous Entries

07/Jan/07 Ywing Styles
06/Jan/07 Definitions
31/Dec/06 Y wings
27/Dec/06 Coloring
11/Dec/06 Beginner Tips
Check out all the Daily Horoscopes
Welcome our latest Members
PeeBee from Perth WA
Adit2111 from Cluj
Grandmavickie from NJ
Member's Birthdays Today
None Today.
Friends currently online
Want to see when your friends are online? Become a member for free.

Network Sites

Melbourne Bars Find the Hidden Bars of Melbourne
Free Crossword Puzzles Play online or print them out. 2 new crosswords daily.
Jigsaw Puzzles Play online jigsaw puzzles for free, with new pictures everyday
Sliding Puzzle Play online with your own photos
Flickr Sudoku Play sudoku with pictures from Flickr
Kakuro Play Kakuro online!
Wordoku Free Wordoku puzzles everyday.
Purely Facts Test your General Knowledge.
Pumpkin Carving Pattern Free halloween pumpkin carving patterns.