X-Wing?

Advanced methods and approaches for solving Sudoku puzzles

X-Wing?

Postby QBasicMac » Thu Jul 14, 2005 2:48 pm

I was studying this near-useless description:
http://www.simes.clara.co.uk/programs/sudokutechnique6.htm

Shown are some asterisks in rows 1 and 9 with no explanation of what happened to the possible cells in rows 2 and 8, etc.

But anyway, I presumed they contained other digits and was mollified and decided to try a sample game.

So I tried xwing1.

I give up. I evidently don't even understand a bit.

Could anyone stare at xwing1 and tell me in painful detail exactly how I would apply the x-wing concept there.

Thanks,

Mac

P.S. If you refer to a cell, please use the notation (row,column) so that cell (3,5) means to count down three rows and count over 5 columns. OR if there is some standard notation, use it and explain to me how to convert to row,column.
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Re: X-Wing?

Postby scrose » Thu Jul 14, 2005 3:09 pm

In xwing1.sdk, solve the puzzle until you reach the following point.

Code: Select all
 . . . | 1 3 . | . . 5
 . 4 . | . . 5 | 2 . .
 8 . . | 9 . 2 | . . .
-------+-------+-------
 . . . | . 5 . | 9 . .
 . . 2 | . . . | 4 . .
 . . 3 | . 6 . | . . .
-------+-------+-------
 . . . | . . 3 | . . 6
 . . 5 | . . . | . 1 .
 7 1 . | . 2 8 | . . .

If you haven't already, eliminate the candidate 6's from the cells r1c8, r2c8, and r3c8.

There is now an x-wing in the candidate 6's using the cells r2c3, r2c4, r9c3, and r9c4. This lets you eliminate the candidate 6's from the cells r1c3, r3c3, r4c3, and r8c4.

QBasicMac wrote:...if there is some standard notation...

Wayne has suggested we use these common terms on this forum.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby QBasicMac » Thu Jul 14, 2005 5:00 pm

Hunhh?

Maybe my problem is worse than I thought. How did you solve r2c6=5 and r3c6=2?

I see a lot of other possibilities. How did you narrow it down so that you were sure these were correct?

Next question: What about r2c1-r8c1-r2c4-r8c4? Is that also an x-wing? Please discuss.

Thanks for your notation reference!

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby scrose » Thu Jul 14, 2005 5:08 pm

QBasicMac wrote:How did you solve r2c6=5 and r3c6=2?

There is a hidden pair of candidates 3 and 5 in box 1. That lets you place a 2 at r3c6. Then you can place a 5 at r2c6.

QBasicMac wrote:What about r2c1-r8c1-r2c4-r8c4? Is that also an x-wing?

I don't see one. Which candidate number are you looking at? And at what stage of the grid?
scrose
 
Posts: 322
Joined: 31 May 2005

Postby QBasicMac » Thu Jul 14, 2005 5:59 pm

OK, I finally see that r2c1 could contain 13569 and r3c2 could contain 123567.

Looking at the other cells in that 3x3, I see those are the only two that can contain 35.

Now in the next 3x3, I am looking at
r1c6: 2467
r2c4: 5678
r2c5: 78
r2c6: 567
r3c5: 47
r3c6: 23567

I don't see any clue that r3c6=2.

> I don't see one. Which candidate number are you looking at? And at what stage of the grid?

The same as you: 6 and in the same puzzle you drew above, with the 2 and 5 inserted (even thought I still don't see why).

Mac

P.S. LOL! My forum is The QBasic Forum. We often get newbies that don't have a clue. I am one of the team that patiently walks them through the simplest and self-evident stuff (over and over) so I really appreciate your taking the time here. I am a n00b!
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Re: X-Wing?

Postby simes » Thu Jul 14, 2005 6:00 pm

QBasicMac wrote:I was studying this near-useless description:

Gee thanks!

QBasicMac wrote:Shown are some asterisks in rows 1 and 9 with no explanation of what happened to the possible cells in rows 2 and 8, etc.

The XWing is on row 1 and 9 for the digit 9. The contents of the other rows don't matter - except as far as they prevent a 9 from occupying certain cells in rows 1 and 9 - and they're blank to show that.

S
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby scrose » Thu Jul 14, 2005 6:04 pm

QBasicMac wrote:I don't see any clue that r3c6=2.

After finding the hidden pair in box 1 and making eliminations, there is only one candidate 2 remaining in row 3.

QBasicMac wrote:What about r2c1-r8c1-r2c4-r8c4? ... The same as you: 6 and in the same puzzle you drew above, with the 2 and 5 inserted (even thought I still don't see why).

Similarily, after finding the hidden pair in box 1 and making eliminations, there is no longer a candidate 6 at r2c1.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby QBasicMac » Thu Jul 14, 2005 11:53 pm

Hi, simes.

Sorry, I should have said "this description which is nearly useless to a newbie". I hate to say this, but your additional information is also useless.

"The XWing is on row 1 and 9 for the digit 9."

That was already clear.

"The contents of the other rows don't matter - except as far as they prevent a 9 from occupying certain cells in rows 1 and 9 - and they're blank to show that."

This is meaningless. How do they prevent a 9. Does blank mean the cell has a number? I would think blank meant that the cell was empty or that it was unknown whether it had a number or not.

If there are numbers, never mind the "don't matter" concept, show some typical values to make things clear.

Similarly, I am having trouble with scrose's attempts to explain by blurting out nonsense (to me - no offense please) such as "making eliminations". What eliminations??

DETAILS PLEASE!

But thanks anyway - I will try to figure it out myself or ask on some other forum. You guys remind me of my physics professor - a genius who wrote stuff other geniuses praised. But he couldn't explain to sophomores how to swat a fly. And if you asked for clarification, he just babbled. We had to find out about physics from other sources.

I guess teaching is a talent, like violin-playing.

Congratulation to all you jargon-spouting gurus. You are no doubt the greatest SuDoku solvers in the world!

Mac

P.S. Want to see my SuDoku Tutorial (for newbies)
www.SuDoku.funURL.com
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby scrose » Fri Jul 15, 2005 12:45 am

My apologies for not explaining the details. Because I noticed that you have written three sudoku programs, I had (incorrectly) assumed that you were quite familiar with sudoku puzzles. I will attempt to clearly explain each step.
  1. There is a hidden pair of candidates 3 and 5 in box 1. Therefore the candidate 1's, 2, 6's, 7, and 9 can be eliminated from the cells r2c1 and r3c2.
  2. The candidate 2 in cell r3c6 is now the only candidate 2 remaining in row 3. Therefore you can place a 2 in the cell r3c6.
  3. The candidate 5 in cell r2c6 is now the only candidate 5 remaining in column 6. Therefore you can place a 5 in the cell r2c6.
  4. All of the candidate 1's in box 1 are located in column 3. Therefore all other candidate 1's in column 3 (r4c3, r7c3, and r9c3) can be eliminated.
  5. The candidate 1 in cell r9c2 is now the only candidate 1 remaining in row 9. Therefore you can place a 1 in the cell r9c2.
  6. All of the candidate 6's in box 6 are located in column 8. Therefore all other candidate 6's in column 8 (r1c8, r2c8, and r3c8) can be eliminated.
  7. An x-wing is present in the candidate 6's in the cells r2c3, r2c4, r9c3, and r9c4. Therefore the candidate 6's can be eliminated from the cells r1c3, r3c3, r4c3, and r8c4.
Here is the ongoing state of the puzzle.

Code: Select all
Before step 1:

 {269}    {2679}   {679}    | 1        3        {2467}   | {678}    {46789}  5
 {13569}  4        {1679}   | {5678}   {78}     {567}    | 2        {36789}  {13789}
 8        {123567} {167}    | 9        {47}     {24567}  | {1367}   {3467}   {1347}
----------------------------+----------------------------+----------------------------
 {146}    {1678}   {14678}  | {23478}  5        {1247}   | 9        {23678}  {12378}
 {1569}   {156789} 2        | {378}    {1789}   {179}    | 4        {35678}  {1378}
 {1459}   {15789}  3        | {2478}   6        {12479}  | {1578}   {2578}   {1278}
----------------------------+----------------------------+----------------------------
 {1249}   {1289}   {1489}   | {457}    {1479}   3        | {578}    {245789} 6
 {23469}  {23689}  5        | {467}    {479}    {4679}   | {378}    1        {234789}
 7        {1369}   {1469}   | {456}    2        8        | {35}     {3459}   {349}

After step 1:

 {269}    {2679}   {679}    | 1        3        {2467}   | {678}    {46789}  5 
 {35}     4        {1679}   | {5678}   {78}     {567}    | 2        {36789}  {13789}
 8        {35}     {167}    | 9        {47}     {24567}  | {1367}   {3467}   {1347}
----------------------------+----------------------------+----------------------------
 {146}    {1678}   {14678}  | {23478}  5        {1247}   | 9        {23678}  {12378}
 {1569}   {156789} 2        | {378}    {1789}   {179}    | 4        {35678}  {1378}
 {1459}   {15789}  3        | {2478}   6        {12479}  | {1578}   {2578}   {1278}
----------------------------+----------------------------+----------------------------
 {1249}   {1289}   {1489}   | {457}    {1479}   3        | {578}    {245789} 6 
 {23469}  {23689}  5        | {467}    {479}    {4679}   | {378}    1        {234789}
 7        {1369}   {1469}   | {456}    2        8        | {35}     {3459}   {349}

After step 2:

 {269}    {2679}   {679}    | 1        3        {467}    | {678}    {46789}  5 
 {35}     4        {1679}   | {5678}   {78}     {567}    | 2        {36789}  {13789}
 8        {35}     {167}    | 9        {47}     2        | {1367}   {3467}   {1347}
----------------------------+----------------------------+----------------------------
 {146}    {1678}   {14678}  | {23478}  5        {147}    | 9        {23678}  {12378}
 {1569}   {156789} 2        | {378}    {1789}   {179}    | 4        {35678}  {1378}
 {1459}   {15789}  3        | {2478}   6        {1479}   | {1578}   {2578}   {1278}
----------------------------+----------------------------+----------------------------
 {1249}   {1289}   {1489}   | {457}    {1479}   3        | {578}    {245789} 6 
 {23469}  {23689}  5        | {467}    {479}    {4679}   | {378}    1        {234789}
 7        {1369}   {1469}   | {456}    2        8        | {35}     {3459}   {349}

After step 3:

 {269}    {2679}   {679}    | 1        3        {467}    | {678}    {46789}  5 
 {3}      4        {1679}   | {678}    {78}     5        | 2        {36789}  {13789}
 8        {35}     {167}    | 9        {47}     2        | {1367}   {3467}   {1347}
----------------------------+----------------------------+----------------------------
 {146}    {1678}   {14678}  | {23478}  5        {147}    | 9        {23678}  {12378}
 {1569}   {156789} 2        | {378}    {1789}   {179}    | 4        {35678}  {1378}
 {1459}   {15789}  3        | {2478}   6        {1479}   | {1578}   {2578}   {1278}
----------------------------+----------------------------+----------------------------
 {1249}   {1289}   {1489}   | {457}    {1479}   3        | {578}    {245789} 6 
 {23469}  {23689}  5        | {467}    {479}    {4679}   | {378}    1        {234789}
 7        {1369}   {1469}   | {456}    2        8        | {35}     {3459}   {349}

After step 4:

 {269}    {2679}   {679}    | 1        3        {467}    | {678}    {46789}  5 
 {3}      4        {1679}   | {678}    {78}     5        | 2        {36789}  {13789}
 8        {35}     {167}    | 9        {47}     2        | {1367}   {3467}   {1347}
----------------------------+----------------------------+----------------------------
 {146}    {1678}   {4678}   | {23478}  5        {147}    | 9        {23678}  {12378}
 {1569}   {156789} 2        | {378}    {1789}   {179}    | 4        {35678}  {1378}
 {1459}   {15789}  3        | {2478}   6        {1479}   | {1578}   {2578}   {1278}
----------------------------+----------------------------+----------------------------
 {1249}   {1289}   {489}    | {457}    {1479}   3        | {578}    {245789} 6 
 {23469}  {23689}  5        | {467}    {479}    {4679}   | {378}    1        {234789}
 7        {1369}   {469}    | {456}    2        8        | {35}     {3459}   {349}

After step 5:

 {269}    {2679}   {679}    | 1        3        {467}    | {678}    {46789}  5 
 {3}      4        {1679}   | {678}    {78}     5        | 2        {36789}  {13789}
 8        {35}     {167}    | 9        {47}     2        | {1367}   {3467}   {1347}
----------------------------+----------------------------+----------------------------
 {146}    {678}    {4678}   | {23478}  5        {147}    | 9        {23678}  {12378}
 {1569}   {56789}  2        | {378}    {1789}   {179}    | 4        {35678}  {1378}
 {1459}   {5789}   3        | {2478}   6        {1479}   | {1578}   {2578}   {1278}
----------------------------+----------------------------+----------------------------
 {249}    {289}    {489}    | {457}    {1479}   3        | {578}    {245789} 6 
 {23469}  {23689}  5        | {467}    {479}    {4679}   | {378}    1        {234789}
 7        1        {469}    | {456}    2        8        | {35}     {3459}   {349}

After step 6:

 {269}    {2679}   {679}    | 1        3        {467}    | {678}    {4789}   5 
 {3}      4        {1679}   | {678}    {78}     5        | 2        {3789}   {13789}
 8        {35}     {167}    | 9        {47}     2        | {1367}   {347}    {1347}
----------------------------+----------------------------+----------------------------
 {146}    {678}    {4678}   | {23478}  5        {147}    | 9        {23678}  {12378}
 {1569}   {56789}  2        | {378}    {1789}   {179}    | 4        {35678}  {1378}
 {1459}   {5789}   3        | {2478}   6        {1479}   | {1578}   {2578}   {1278}
----------------------------+----------------------------+----------------------------
 {249}    {289}    {489}    | {457}    {1479}   3        | {578}    {245789} 6 
 {23469}  {23689}  5        | {467}    {479}    {4679}   | {378}    1        {234789}
 7        1        {469}    | {456}    2        8        | {35}     {3459}   {349}

Candidate 6's after step 6:

 6 6 6 | . . 6 | 6 . .
 . . 6 | 6 . . | . . .
 . . 6 | . . . | 6 . .
-------+-------+-------
 6 6 6 | . . . | . 6 .
 6 6 . | . . . | . 6 .
 . . . | . . . | . . .
-------+-------+-------
 . . . | . . . | . . .
 6 6 . | 6 . 6 | . . .
 . . 6 | 6 . . | . . .

After step 7:

 {269}    {2679}   {79}     | 1        3        {467}    | {678}    {4789}   5 
 {3}      4        {1679}   | {678}    {78}     5        | 2        {3789}   {13789}
 8        {35}     {17}     | 9        {47}     2        | {1367}   {347}    {1347}
----------------------------+----------------------------+----------------------------
 {146}    {678}    {478}    | {23478}  5        {147}    | 9        {23678}  {12378}
 {1569}   {56789}  2        | {378}    {1789}   {179}    | 4        {35678}  {1378}
 {1459}   {5789}   3        | {2478}   6        {1479}   | {1578}   {2578}   {1278}
----------------------------+----------------------------+----------------------------
 {249}    {289}    {489}    | {457}    {1479}   3        | {578}    {245789} 6 
 {23469}  {23689}  5        | {47}     {479}    {4679}   | {378}    1        {234789}
 7        1        {469}    | {456}    2        8        | {35}     {3459}   {349}

You should note that this is not necessarily the easiest way to solve this puzzle. However, it is likely the fastest way to reach the x-wing in the candidate 6's, which is what you had stated interest in.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby QBasicMac » Fri Jul 15, 2005 3:15 am

Now we're getting somewhere. Thanks for the more detail! A heroic effort.

"assumed that you were quite familiar with SuDoku puzzles"

No. I am somewhat familiar, but know nothing of puzzle-solver jargon and advanced techniques to avoid guessing. I can always solve The Daily SuDoku puzzles in about 20 minutes, even the hard ones, but my techniques are primitive and I think of them differently.

Here is my understanding of what you said in newbie-speak:

1) If you examine row 3, you will see that a 2 can only be placed in r3c2 or r3c6. It can't be in r3c3 because the column has a 2 at r5c3. Similarly, it can't be in r3c5. And r3c7, 8 and 9 are in a 3x3 that has a 2 (at r2c7).

2) But if you examine all the empty cells in the first 3x3, you see that only cells r2c1 and r3c2 can contain a 3 or a 5. Consequently r3c2 must be either a 3 or a 5, Thus r3c6 must be a 2.

3) r8c6 cannot be a 5 because of the 5 at r8c3. r8c1 cannot because of the 5 at r1c8. Hence r2c6 must be a 5 since the 3x3 below already has a 5.

4) In the first 3x3 we know that r2c1 and r3c2 are either a 3 or 5. We also know r1c1, 2, and 3 cannot be a 1 because of the 1 at r1c4. So there must be a 1 in either r2c3 or r3c3. That means there cannot be one at r9c3.

5) But r9c4 cannot be a 1 either because of r1c4. And the 1 at r8c8 rules out a 1 in r9c7, 8, and 9. That leaves only r9c2. It must be a 1.

6) There must be a 6 in r4c8 or r5c8. The other cells are prohibited because of r6c5 and r7c9. Therefore there can be no 6 in the other cells in column 8.

7) Since r2c8 cannot be a 6 due to the analysis above and r2c9 cannot be because of r7c9 and r2c5 cannot because of r6c5 and r2c1 because of the first analysis, we are left with two cells where a 6 can go: r2c3 and r2c4.

Similarly, there are only two cells where a 6 can go on row 9: r9c3 and r9c4 (r9c7, 8, and 9 are prohibited because of r7c9)

Such a pattern: r2c3 r2c4 r9c3 r9c4 forms the corners of an X and serious puzzle solvers have given this the name "X-wing". In this case, if a 6 is in r2c3, then there must be also be one at r9c4! If there is not a 6 in r2c3 then there must be one in r3c4 AND r9c3.

Although you might not be able to immediately place any digit based on this information, it helps.

----------

I am still studying it, but your detail really helped.

I hope you try my 3 utilities and comment on my forum there. I already learned from you that I need a technique to "eliminate candidates" as you say. I show candidates that are legal, but have no way of eliminating them (yet) except in my mind.

I'm thinking of allowing the user to go to an empty cell with candidates 358 and enter "-5". Thereafter, the list will be "38". That would be a great help.

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby scrose » Fri Jul 15, 2005 3:40 am

QBasicMac wrote:Here is my understanding of what you said...

Your interpretation is correct.

QBasicMac wrote:In this case, if a 6 is in r2c3, then there must be also be one at r9c4! If there is not a 6 in r2c3 then there must be one in r3c4 AND r9c3.

Once you have found an x-wing, the next step is to eliminate candidates based on the cells that the x-wing occupies. We have determined that in column 3, the 6 will either be at r2c3 or r9c3. Therefore the other candidate 6's in column 3 (r1c3, r3c3, and r4c3) can be eliminated. We have determined that in column 4, the 6 will either be at r2c4 or r9c4. Therefore the other candidate 6 in column 4 (r8c4) can be eliminated.

QBasicMac wrote:Although you might not be able to immediately place any digit based on this information, it helps.

After making the eliminations as a result of the x-wing, the only candidate 6 remaining in row 3 is at r3c7.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby simes » Fri Jul 15, 2005 7:51 am

QBasicMac wrote:"The contents of the other rows don't matter - except as far as they prevent a 9 from occupying certain cells in rows 1 and 9 - and they're blank to show that."

This is meaningless. How do they prevent a 9. Does blank mean the cell has a number? I would think blank meant that the cell was empty or that it was unknown whether it had a number or not.


Well, from the numbers that you can see, and following the rules of Sudoku, work out which cells in rows 1 and 9 can contain a 9.

First of all, it can only be the empty cells. Secondly, there must not be a 9 in the same column. You'll see that only the marked cells can contain a 9.

Perhaps I'll just wait until scrose has explained it to you, then crib from the explanation on your site!

S
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby scrose » Fri Jul 15, 2005 12:40 pm

QBasicMac wrote:I am somewhat familiar [with sudoku puzzles], but know nothing of puzzle-solver jargon and advanced techniques to avoid guessing. ...my techniques are primitive and I think of them differently.

To avoid further frustration, I suggest learning and mastering the simpler techniques (such as candidate restrictions, pairs, triples) before trying to tackle puzzles that require advanced techniques (such as x-wing, swordfish, colouring, forcing chains).

The first x-wing I encountered left me flummoxed. At the time, I had to study simes' description very closely to understand how to apply the x-wing technique. I returned to solving easier puzzles until I was ready for the challenge that x-wings provide.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby QBasicMac » Sat Jul 16, 2005 3:09 am

OK, and thanks again

Mac

P.S. Hoping to see a post from you regarding my tutorial at www.Sudoku.funURL.com

Also, the SuDoku Scratch Pat (SSP).
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby goldie5218 » Sat Jul 16, 2005 12:14 pm

hi guys, have been following this forum very closely regarding the identification of x-wings - my personal bugbear! and yes i am still confused! wow if clever guys like you cant understand each other no wonder us newbies are floundering ! (just kidding) no offense intended! but everyone seems to sort of gloss over the really important aspect that dumb people like me are grasping for! just how to find/identify an x-wing?? my original concept/understanding after reading up on all the tutorials was that the x-wing candidates will - one - form the "corners" of the x-wing - two - can be based on either the rows or the columns but not both at the same time - three - on identification will allow the elimination of the candidates falling on the row/column in which the x-wing candidates appear - four - only two x-wing candidates can appear in the row /column forming the sides of the rectangle ie vertical for the 'column' x-wing and horizontal for the 'row' x-wing - five - can be positioned anywhere in the entire 36 cell grid. --- now comes the bad news for me !on the reply to query / as opposed to the tutorial notes, i am given an example of an x-wing that appears to be formed on a column yet has more than two of that particular candidate in the column? so yes we are floundering again! now pleeeeeease can someone explain, in idiot lanquage, just how to find an x-wing ??? do i look along every row/column and identify those holding only two of a particular candidate? (as per the tutorial) and then cross check to see these same candidates coincide on an identical row column to form the magic rectangle?? or am i again not on the same page as the example of the "6" xwing given seems to follow a diff identification strategy?? any assistance gladly and greatfully accepted! oh by the way im ok with sudukos up to the x-wing level but then im drowning. cheers
"
goldie5218
 
Posts: 37
Joined: 27 May 2005

Next

Return to Advanced solving techniques