dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

X-Wing & XY -Wing

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion
View previous topic :: View next topic  
Author Message
Cherylpc



Joined: 17 Jul 2006
Posts: 1

PostPosted: Mon Jul 17, 2006 5:00 pm    Post subject: X-Wing & XY -Wing Reply with quote

Please explain what an X-Wing and an XY-Wing is?
Back to top
View user's profile Send private message Send e-mail
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Mon Jul 17, 2006 9:58 pm    Post subject: Lots of explanations online Reply with quote

Hi, Cheryl! Welcome to the forum.

Please try reading this explanation of the "X-Wing" pattern. Then check out this explanation of the XY-Wing.

If you still have questions after reading that stuff, please feel free to ask again. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
jake3988



Joined: 22 Sep 2006
Posts: 5

PostPosted: Fri Sep 22, 2006 9:41 pm    Post subject: Reply with quote

Like Cheryl (but 2 months removed) am looking for an explaination. However, most explainations have horrible-looking diagrams associated (like on forums and such).

This has that advantage, but the explaination is utterly horrendous. First he says you can use it with rectangles. But, there's at least 3 other rectangles you can form with the 1's, never explaining why you can't use those.

Plus, there's no reasoning on why this method works, either. I won't just 'take his word for it', I have to have a reasoning as to why it works.


If anyone else can clearly explain it, or point me somewhere else, that would be immensely helpful.
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Fri Sep 22, 2006 10:32 pm    Post subject: Which are you asking about? Reply with quote

Hi, Jake!

I'm a little confused by your post. Are you asking abou the "X-Wing" pattern? Or about the "XY-Wing"? Since you mentioned a rectangle, I suppose you're asking about the "X-Wing".

The first thing you might try is to use the search button at the top of this page, and run a search on x-wing in this forum. That should get you 15 or 20 examples, many of them clearly explained.

Here, I'll explain it one more time.

There are two possible kinds of X-Wings: an X-Wing on rows and an X-Wing on columns.

An X-Wing on rows occurs when three conditions are satisfied for a particular candidate digit x.

-- In row a, there are only two spots where digit "x" can occur.
-- In row b, there are only two spots where digit "x" can occur.
-- The pairs of possible spots for "x" in rows a and b fall in the same two columns -- let's call them m and n.

The "X-Wing rule" now says that any other possible "x"s in columns m and n can be eliminated. The logic is simple.

Either there's an "x" at Row a Column m and an "x" at Row b Column n, or else there's an "x" at Row a Column n and an "x" at Row b Column m; no other configurations are possible.

Another way to think of it is as follows. If an "x" occurred in column m and not in row a or row b, it would be impossible to complete rows a and b.

An X-Wing on columns is exactly analagous, but now you have two columns (in each of which "x" can only fit in two spots) and the "candidate cells" in these columns lie in just two rows. You can transform an X-Wing on rows into an X-Wing on columns by turning the puzzle sideways, so these are really the same pattern, just rotated by 90 degrees. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
jake3988



Joined: 22 Sep 2006
Posts: 5

PostPosted: Sat Sep 23, 2006 11:20 pm    Post subject: Reply with quote

Thanks for the reply.. I still don't understand the logic. Nor could I ever pick it out.

Let's say, we have something like:
(This is the exact [recreated] situation from the site refferal. Note, all the '1's are candidates for the one.)
1xx|x1x|xx1
xxx|x1x|xx1
1xx|x11|1xx
----------------
xxx|xxx|xxx
xxx|x11|1x1
xxx|x1x|xx1

Edit: Actually, according to your given definition, it would make the one specified on the website work. So I understand that.

However, on the website, it claims R3C6 is the upper-left corner of 'another' x-wing which don't NOT apply to that definition. Which makes it really confusing.

Although, I'm not the type of guy who writes every single candidate for every single box. That's just sadistically overboard. So I guess this whole thing is moot anyway.
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Sun Sep 24, 2006 2:33 am    Post subject: Reply with quote

The other X-wing is in columns. Columns 6 & 7 both have only two places for the 1 and those places are in rows 3 & 5. Eliminates all other 1 candidates in those two rows.
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Sun Sep 24, 2006 3:19 am    Post subject: Play it again, Sam ... Reply with quote

Hi, Jake! Thanks for writing back. And thanks for the diagram. Specific examples are easier to follow than abstract explanations.
Code:
1xx|x1x|xx1
xxx|x1x|xx1
1xx|x11|1xx
-----------
xxx|xxx|xxx
xxx|x11|1x1
xxx|x1x|xx1

First, let's go through the logic for the X-Wing in rows 2 and 6 one more time.

-- There has to be a "1" in row 2 somewhere. Just for the sake of argument, let's suppose that there's a "1" at r2c5. Then there cannot possibly be a "1" in these cells: r1c5, r3c5, r5c5, & r6c5.

-- Still supposing that r2c5 = 1, we know that there has to be a "1" in row 6 somewhere. The only place it can fit is at r6c9. Therefore, if r2c5 = 1 we know that there cannot be a "1" at r1c9, r2c9, or r5c9.

-- Summarizing, then, we see that if r2c5 = 1 there cannot be a "1" in any of these seven cells: r1c5, r3c5, r5c5, r6c5, r1c9, r2c9, r5c9.

-- The "1" in row 2 does not have to appear at r2c5 ... it might be at r2c9 instead. So what happens if r2c9 = 1? Then there cannot be a "1" in any of these cells: r1c9, r5c9, & r6c9.

-- Again, since there must be a "1" in row 6 somewhere, if r2c9 = 1 we must also have r6c5 = 1. Therefore, if r2c9 = 1 there cannot possibly ba a "1" in any of these cells: r1c5, r2c5, r3c5, & r5c5.

-- Summarizing the case where r2c9 = 1 we see that "1" cannot appear in any of these seven cells: r1c5, r2c5, r3c5, r5c5, r1c9, r5c9, r6c9.

-- Now, since one of these two cases must be true we can gain real insight into the situation by comparing the two lists derived in the third and sixth steps detailed above. We see that the following five cells appear in both lists: r1c5, r3c5, r5c5, r1c9, r5c9.

-- The conclusion is inescapable -- no matter where the "1" is placed in row 2 there cannot possibly be a "1" in any of these five cells: r1c5, r3c5, r5c5, r1c9, r5c9.

OK, that covers the "X-Wing on Rows" in the example you posted. As Tracy has pointed out, the second X-Wing in thie diagram is an "X-Wing on Columns". There are only two ways to fit a "1" in Column 6 -- at r3c6, or at r5c6. Similarly, there are only two ways to fit a "1" in Column 7 -- at r3c7, or at r5c7. This time the X-Wing pattern falls in columns 6 & 7, and the digits we can eliminate lie in rows 3 & 5. There cannot possibly be a "1" in any of these cells: r3c1, r3c5, r5c5, r5c9. The logic is entirely analagous to the argument I have explained in excruciating detail above.
Jake3988 wrote:
... I'm not the type of guy who writes every single candidate for every single box. That's just sadistically overboard.

I agree with you. About writing down the candidates, I mean. I generally work these puzzles without writing down any candidates in any of the boxes. I can usually spot the "X-Wing" pattern with ease. If I can do it, you can too. It's just a question of how hard you're willing to concentrate. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
jake3988



Joined: 22 Sep 2006
Posts: 5

PostPosted: Sun Sep 24, 2006 2:56 pm    Post subject: Reply with quote

thanks again. I still don't understand the logic, but I guess if I spot more examples I'll try and deduce why it actually works in my head. It'll come with practice.

That is, try and place ones in the other cells in that column and see why its impossible. I just don't see it from the example.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5061
Location: Rochester, NY, USA

PostPosted: Sun Sep 24, 2006 3:50 pm    Post subject: Reply with quote

Quote:
Although, I'm not the type of guy who writes every single candidate for every single box. That's just sadistically overboard.


I write 'em all in. But since this is a solo activity, wouldn't I be "masochistically overboard"? Question Laughing
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Sun Sep 24, 2006 4:47 pm    Post subject: Reply with quote

jake3988,

Do you understand the concept of 'strong links' (also known as conjugate links)? It's pretty much essential to understanding X-wings.

Here is the link to an excellent post that explains the general concepts of 'strong links' and specifically explains the logic behind an X-wing:

http://www.sudoku.com/forums/viewtopic.php?t=3326
Back to top
View user's profile Send private message
jake3988



Joined: 22 Sep 2006
Posts: 5

PostPosted: Sun Sep 24, 2006 10:37 pm    Post subject: Reply with quote

kinda. If he made his post about half as long and stayed with the quasi-reallife situation instead of making it confusing as heck with green letters and code, I would likely have it really understood.

He does a good job explaining the logic though in a very simple way.

But anyway, I found a real life situation in today's puzzle (the logic is completely different, and it wouldn't really qualify as a x-wing, but basically the same logic applied.

That is, I had:
Code:

5xx|55x|x5x
5xx|---|x5x
xxx|xxx|xxx


(the dashes mean that row was completely filled already)

in my truncated example tje x-wing box would be R1C1, R1C8, R2C1, an R2C8

It basically means, because that row is already filled in the middle, and ONE of the 5s HAS to be true in the top row of the side boxes so it eliminates 5 from the top row of the middle box.

I don't think its the same thing as an x-wing at all, but I can sort of see how it works now.
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Sun Sep 24, 2006 11:36 pm    Post subject: Reply with quote

Here is the position to which you refer:
Code:
 
 *--------------------------------------------------------------------*
 | 7      5      28     | 4      289    28     | 6      1      3      |
 | 248    3      1      | 25     7      6      | 25     9      48     |
 | 2489   48     6      | 3      12589  258    | 25     7      48     |
 |----------------------+----------------------+----------------------|
 | 6      7      9      | 8      4      3      | 1      2      5      |
 | 48     1      48     | 7      25     25     | 9      3      6      |
 | 3      2      5      | 9      6      1      | 4      8      7      |
 |----------------------+----------------------+----------------------|
 | 258X   9      3      | 256-   258-   4      | 7      56X    1      |
 | 245X   46     24     | 1      3      7      | 8      56X    9      |
 | 1      68     7      | 56     58     9      | 3      4      2      |
 *--------------------------------------------------------------------*


And it is an X-wing on columns, which means that the exclusions take place in the rows for the reasons you've stated, but your statement didn't go far enough. One of the top most cells in the outside boxes (in this example r7c1 or r7c8) must be 5 AND one of the middle cells in the outside boxes (r8c1 or r8c8) must also be 5. So, if there were unsolved cells in the middle row that contained candidate 5's, they could be excluded also. (I realize there are locked candidate exclusions that do the same thing but thought it best not to discuss them in this post).
Back to top
View user's profile Send private message
jake3988



Joined: 22 Sep 2006
Posts: 5

PostPosted: Mon Sep 25, 2006 2:41 am    Post subject: Reply with quote

Right. Thanks. And yes, that's pretty much the exact point in the puzzle I saw it.

Solved it completely shortly thereafter too. (This hard was immensely easier than the previous day's very hard. It was indeed much harder than the medium and easy, but the very hard I only got about 2 numbers of the whole puzzle.)
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> General discussion All times are GMT
Page 1 of 1

 
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


Powered by phpBB © 2001, 2005 phpBB Group