terms like x-wing, swordfish, jellyfish

Semo

Hi! I'm new here. I'm pretty interested in sudoku, but I m just newbie. I'd like to understand sudoku, so I found this programmers forum. I found here many terms like x-wing, swordfish, jellyfish, etc.. But I dont understand them at all Sad

I would like you to write here some link where I could find out what it means. Thanx

Ruud · Site Admin

A nice explanation can be found here: http://www.simes.clara.co.uk/programs/sudokutechniques.htm

Semo · Posted: Sun Sep 18, 2005 3:16 pm Post subject:

Oh..thx, I'm gonna spend some time reading and trying to understand that tonight Smile

Lummox JR · Posted: Mon Sep 19, 2005 3:59 pm Post subject:

I learned X-wing and swordfish there, though I thought the swordfish example seemed a little incomplete. Basically it's just a 3-col/row form of X-wing. Jellyfish is a 4-col/row swordfish; I really just prefer to call all the 3+ methods swordfish and leave it at that. These techniques are actually identical in form to finding naked or hidden subsets. The only difference is that instead of using digit and position for a certain house (box/col/row), you're using column and row for a certain digit.

Nishio is described succintly there, but I didn't quite understand it until I read about it here. Basically for each digit, you place it in each candidate position and see if that immediately forces moves for placing the rest of that digit. If it leads to a contradiction, you can eliminate the digit for that cell. If, in a particular house, every placement of the digit will always lead to it appearing in the same place elsewhere on the grid, that confirms the digit must go there. (I.e., if anywhere you put a 5 in c2, it always puts a 5 at (6,8), then there must be a 5 at (6,8).) You do not follow Nishio all the way down from guess to logical conclusion; you only need to follow it for the next digit to place. If you place a 2, you need to look for any places where you can immediately place another 2; if there are none, then Nishio stops and you've learned nothing from this guess.

Coloring, which I don't think that page describes adequately, is basically similar to fishy cycles. If you take the example on that page, to color that you'd start by labeling cells (3,2) and (6,2) with a and A. That's the only row with conjugates. As you find others you'd normally label them b and B, etc. Now searching by column, you have (6,2) and (6,5). Since (6,2) is already labeled, instead of b and B we call these A and a, respectively; (6,2) was already A, so we give (6,5) the conjugate label a. Searching by box, another conjugate is found in b1: (2,1) must be A, to go with the a in (3,2). At this point the coloring we've found means that either the a's or the A's must all have the candidate value. Therefore, since (2,5) must be in the same column as A and the same row as a, it cannot be a 1 because either a or A will rule it out.

There is also method called fishy cycles, very similar to coloring, described elsewhere on this forum. It builds a graph of nodes and finds places where candidates may be eliminated. All X-wings and some swordfish can be found with fishy cycles.

Semo · Posted: Mon Sep 19, 2005 7:07 pm Post subject:

Oh, tahnk you so much for your effort. I didnt think that sudoku can be so difficult and interesting. I colud solve even hardest sudokus at some websites without knowing these tactics. I thought I knew enough but now, I realized that there is so much to learn about sudoku. I started to really admire you, sudoku programmers Smile

)

Lummox JR · Posted: Mon Sep 19, 2005 10:14 pm Post subject:

Heck, until I looked for more info myself I didn't realize there was something beyond mere subsets. I'd used an X-wing once, but chalked it up to being some form of reduction rule I could've done another way. Now I've learned a lot more.

Fishy cycles is one technique I highly recommend picking up. It sounds difficult at first but it isn't, once you properly understand it. MadOverlord's sudoku susser is a great program for showing you how to handle fishy cycles.

Coloring is also fairly easy once you master it, and then you can use the advanced technique mentioned on that example page to turn weakly linked colors into strongly linked ones. This seems to pick up most of the same clues as fishy cycles, but neither one is superior to the other; you need both. (However coloring, I think, is quite a bit faster.)

For the most difficult puzzles, forcing chains, Nishio, and Bowman bingo seem to be the methods of choice. I'm still not clear on how to set up forcing chains properly at a guess, and I'm currently trying to redefine it so it falls within the realm of hard logic instead of guessing. (My solver program, however, is still having troubles with it.) And I've yet to try Bowman bingo, which freaks me out a bit because of its complexity.

While you're honing your techniques, I'll give you a puzzle my solver generated today which can be solved via a combination of techniques. Once you get to a certain point, either fishy cycles, or coloring followed by X-wing, will reduce some possibilities, and then you can use an XY-wing to finish the puzzle. Other methods like remote locked pairs or forcing chains work too, but it's a sufficiently interesting puzzle to teethe on.

DHallman · Posted: Thu Sep 22, 2005 8:22 am Post subject:

Simple techniques (onesies) generates a position where coloring the 3s Eliminates 5 of 9 leaving the solution wide open.

Lummox JR · Posted: Thu Sep 22, 2005 7:43 pm Post subject:

Aye, that puzzle can be cracked in a lot of ways. Remote pairs seems to be the quickest, though, since it's easy to spot a chain of four 37's that eliminate 37 at (5,8), leaving a naked 2. Fishy cycles and coloring do the same for 7 but not 3, leaving an XY-wing able to clear 7 from (1,1) and leaving a 2 there.

Ruud · Site Admin

Leave out the 5 at (2,6) and the puzzle suddenly becomes a lot more challenging...