Su Doku puzzle needing x Wing technique, can anyone help?

Advanced methods and approaches for solving Sudoku puzzles

Su Doku puzzle needing x Wing technique, can anyone help?

Postby Kites » Sun Aug 14, 2005 4:12 pm

I posted this query before and lost it, so I am trying again.
It's last Sunday Times magazine's Su Doku which I managed to complete by guessing. I would like to solve it the Logical way. I was recommended to use X Wing which I am totaly unfamiliar with. I looked at SadMan Software which didn't help much.

(239),5,8,/1,(3479),(47),/(49),(346),(2346)
4,7,1,/6,(359),2,/(589),(38),(35)
(239),6,(29),/(59),(3459),8,/1,7,(2345)

7,4,(59),/8,(59),1,/2,(36),(36)
(29),3,(259),/(59),6,(47),/(478),(48),1
1,8,6,/2,(47)3,/(47),5,9

6,1,3,/7,8,9,/(45),2,(45)
5,9,7,/4,2,6,/3,1,8
8,2,4,/3,1,5,/6,9,7
Kites
 
Posts: 48
Joined: 20 May 2005

S Times

Postby bobhc » Sun Aug 14, 2005 4:33 pm

358 174 962
471 692 583
962 538 174

749 851 236
235 967 841
186 243 759

613 789 425
597 426 318
824 315 697
bobhc
 
Posts: 1
Joined: 14 August 2005

Postby simes » Sun Aug 14, 2005 5:04 pm

bobhc... how does that help explain?

OK Kites, SadMan here again... I'll try to explain.

look at where 4s can go in columns 6 and 8. There are only two cells in each column, both in rows 1 and 5. This gives us an XWing. Think how you could place 4s in these columns so that each column has a 4, and both rows only get one each. (Remember all columns, rows and boxes must have each of the digits 1 to 9) There are only two possibilities; either (r1c6 and r5c8) have 4, or (r5c6 and r1c8). Either way, there can be no other 4s in rows 1 or 5, so you can eliminate it from the candidates for cells r1c5, r1c7, r5c7, r1c9.

Any better?

Simes

For any readers, the part-completed puzzle is
Code: Select all
.581.....
4716.2...
.6...817.
74.8.12..
.3..6...1
1862.3.59
613789.2.
597426318
824315697
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby Kites » Sun Aug 14, 2005 6:22 pm

Thank you very much for your reply. I have just written a very long reply to say that I am not out of my misery yet, when I looked at it again and it clicked (or at least I think it did...). The X wing has to have 2 candidates in a unit to eliminate a value from other units. Is that correct? Can I come back if I am stuck again - need to go soon. Thanks again.



[quote="simes"]bobhc... how does that help explain?

OK Kites, SadMan here again... I'll try to explain.

look at where 4s can go in columns 6 and 8. There are only two cells in each column, both in rows 1 and 5. This gives us an XWing. Think how you could place 4s in these columns so that each column has a 4, and both rows only get one each. (Remember all columns, rows and boxes must have each of the digits 1 to 9) There are only two possibilities; either (r1c6 and r5c8) have 4, or (r5c6 and r1c8). Either way, there can be no other 4s in rows 1 or 5, so you can eliminate it from the candidates for cells r1c5, r1c7, r5c7, r1c9.

Any better?

Simes

For any readers, the part-completed puzzle is
[code].581.....
4716.2...
.6...817.
74.8.12..
.3..6...1
1862.3.59
613789.2.
597426318
824315697[/code][/quote]
Kites
 
Posts: 48
Joined: 20 May 2005

Postby simes » Sun Aug 14, 2005 6:36 pm

Kites wrote:The X wing has to have 2 candidates in a unit to eliminate a value from other units. Is that correct?

Kinda. Now that you have an idea, try reading my description again - perhaps it'll make more sense now.

Kites wrote:Can I come back if I am stuck again
I don't see any way of stopping you!:D

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

Postby Kites » Sun Aug 14, 2005 7:11 pm

Yesterday I was recommeded to solve the puzzle from information I had on r3c4, r4c3, r4c5 and r5c4 they all have 5&9. How do I deal with this information?

[quote="simes"][quote="Kites"]The X wing has to have 2 candidates in a unit to eliminate a value from other units. Is that correct?[/quote]
Kinda. Now that you have an idea, try reading [url=http://www.simes.clara.co.uk/programs/sudokutechnique6.htm]my description[/url] again - perhaps it'll make more sense now.

[quote="Kites"]Can I come back if I am stuck again[/quote]I don't see any way of stopping you!:D

Simes[/quote]
Kites
 
Posts: 48
Joined: 20 May 2005

Postby simes » Sun Aug 14, 2005 9:19 pm

Kites wrote:Yesterday I was recommeded to solve the puzzle from information I had on r3c4, r4c3, r4c5 and r5c4 they all have 5&9. How do I deal with this information?
Beats me. I can't see anything useful about those cells, and certainly not the XWing you were asking about.

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

Postby Kites » Sun Aug 14, 2005 10:40 pm

OK, and thanks. Am going to look into 'colouring' and 'forcing chains' now, hope it's not too comlicated to understand...


[quote="simes"][quote="Kites"]Yesterday I was recommeded to solve the puzzle from information I had on r3c4, r4c3, r4c5 and r5c4 they all have 5&9. How do I deal with this information?[/quote]Beats me. I can't see anything useful about those cells, and certainly not the XWing you were asking about.

S[/quote]
Kites
 
Posts: 48
Joined: 20 May 2005

X-Wing Technique & Example

Postby MathWizard » Mon Aug 15, 2005 10:41 pm

simes, I read through your description of X-Wing several times and was eventually able to understand the concept (sort of) but I had a lot of trouble figuring out how to use it in the examples on the X-Wing page. Working through the example Kites gave, however, and your explanation of what cells were affected really helped.

The Key, as I see it, is that there has to be a "box" of four cells that are the corners of a rectangle. The X is how the opposite corners need to be paired together one way or the other in order to solve the puzzle. If there are any other options, then the X-Wing is not in effect.

Once an X-Wing is in effect, then any other cells that are NOT part of the box can have their numbers eliminated. These will fall either on the rows or the columns that represent the sides of the box. Only one type of side will be possible, as the Box requires that the corner cells are the only available locations of the number in either the two rows or the two columns.

In Kites example, all potential 4s form the following pattern:


Code: Select all

++++4X4X4
F++++++++
++++4...4
+F+++++++
++++.X4X.
++++4.4..
++++..4.4
+++F+++++
++F++++++

F - A Fixed 4
+ - The 4 for this row or column has been fixed
. - A 4 cannot occupy this space
4 - A 4 can potentially occupy this space
X - This is a potential 4 that is part of the X-Wing move


X-Wing move causes the following:

++++n4n4n
F++++++++
++++4...4
+F+++++++
++++.4n4.
++++4.4..
++++..4.4
+++F+++++
++F++++++

n - An eliminated 4

Since the X-Wing pattern exists on the Columns (Columns 6 and 8) the eliminated 4's are on the Rows (Rows 1 and 5).



What I am finding tricky is finding places where an X-Wing move is possible. Looking at the collection of available 4's did not help me at all until you pointed out exactly where the X-Wing occurred. Now that I see them, I completely understand how they work.

Any tips on how to recognize where an X-Wing appears, or is this just something you develop over time? I am new to Sudoku, so perhaps it is just something that comes with experience.

Many thanks.
MathWizard
 
Posts: 1
Joined: 15 August 2005

Postby simes » Tue Aug 16, 2005 6:53 am

You need to look for two rows/columns, with only two candidate cells for certain numbers... and they have to occur in the same columns/rows. (But even if you spot an XWing, it may not do you any good - you need to be able to make some eliminations or else it's useless.)

I confess that I use the "highlight" feature of my program as it can highlight both numbers and candidates, making it easier to spot where there are only two occurrences. I suspect many purists spot them the hard way, and I guess this must become easier with practice.

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

Postby stuartn » Tue Aug 16, 2005 9:11 am

If you use Excel, there's a free one here that will show you doubles / triples as you progress through the puzzle. It also allows access to the macros so you can work out the logic for yourself.

http://www.brightonandhove.org/Sudolinks.htm

I think the important thing to stress with inexperienced solvers is that the nodes of the x-wing can have MORE than two candidates - as long as the candidate you are focussing on has only TWO occurences in the row (or column). I for one missunderstood at the beginning and looked for nodes that contained only a PAIR of candidates.
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby Doyle » Tue Aug 16, 2005 3:17 pm

I'm new to this, solve with paper and pencil, but here is how I've been finding X-Wings, with some success: After I've gone as far as I can with simpler techniques, I make pencilmarks for all remaining candidates in all remaining vacant cells (you solvers using computers do this easily). Then I visually scan, one column at a time, for a value with two and only two available cells in that column. Once I find such a two-cell value, I just quickly scan across the other columns looking for another column that completes the "magic rectangle", very easy to do, either you bingo or you don't. When you find a possibly valid rectangle, just make sure there are only two possible cells for that value in the new column, also. At this point you can make the exclusions, if any, across the two intersecting rows. Finished with columns, do the same with rows (I find it easier on my eye/brain coordination to start with columns). It all goes rather quickly actually, it's doing the pencilmarks that is slow.
Doyle
 
Posts: 61
Joined: 11 July 2005


Return to Advanced solving techniques