Sudoku Players' Forum (clone)

by **kleinman** » Sat Apr 16, 2005 5:33 pm

sorry to be so dumb. can someone tell me what an x wing is please

by **causbrite** » Sat Apr 16, 2005 8:39 pm

As far as Sudoku goes, I have no idea. Only x wings I know of are the type that Luke and Wedge drive!

by **Sue De Coq** » Sat Apr 16, 2005 9:55 pm

The characteristic feature of the X-Wings pattern is the existence of two rows (or columns) - each of which has exactly two candidate positions for a given value such that, critically, the two candidate positions lie on the same columns (or rows). The pattern allows us to eliminate other candidate positions for the given value on the shared columns (or rows). Wayne coined the term 'X-Wings' because the pattern comprises two straight lines linked by a central 'X' - somewhat like the Starwars fighter (if you have a good enough imagination!).

The following example has been lifted (slightly edited) from the Sudoku Programmers forum.

Consider the following puzzle, which is a partial-solution of the 'Very
Hard' puzzle from The Times:
Code: Select all
. 4 3 * 9 8 . * 2 5 . 6 . . * 4 2 5 * . . . 2 . . * . . 1 * . 9 4 ********************** 9 . . * . . 4 * . 7 . 3 . . * 6 . 8 * . . . 4 1 . * 2 . 9 * . . 3 ********************** 8 2 . * 5 . . * . . . . . . * . 4 . * . . 5 5 3 4 * 8 9 . * 7 1 .

After we've made a few straightforward eliminations :

The value 3 in Box [1,3] must lie in Row 2.
The value 3 in Box [3,2] must lie in Column 6.
The value 7 in Column 5 must lie in Box [2,2].

we achieve a position where it's possible to apply a rule called X-Wings. Note that there are two possible positions for the value 6 in each of Row 1 and Row 9 and that, critically, the candidate positions lie on the same columns. Consider the rectangle formed from the cells (1,6), (1,9), (9,6) and (9,9). Clearly, 6s must occupy two of those four cells - the pair (1,6) and (9,9) or the pair (1,9) and (9,6) - but we don't know which at this stage. However, regardless of which pair is occupied, we are able to eliminate the value 6 as a possibility from each cell in Columns 6 and 9 apart from the vertices of our rectangle. In particular, we eliminate 6 as a possibility for the cell (7,9), which leaves 9 as the only possibility. The remainder of the problem is now solved easily.

by **Pappocom** » Sun Apr 17, 2005 4:13 pm

Hello kleinman.

Fair enough that you should ask what an X-wing is, but if you confine yourself to Times puzzles (and we are in The Times forum, here) you will never need to bother about X-wings.

That is because X-wings are a feature of the Sudoku program's Very Hard puzzles - and puzzles of that grade (think of them as "Super-Fiendish"

do not normally appear in The Times.

Actually, there was one Very Hard puzzle published in The Times on November 12, 2004, when Su Doku was first launched, but that puzzle was by way of example only - just to demonstrate the range of difficulty that is possible.

- Wayne

by **kleinman** » Sun Apr 17, 2005 7:04 pm

Thank you everyone. I have printed your comments off and will inwardly digest them. I think I use x wings without knowing what it is called

by **lunababy_moonchild** » Wed Apr 27, 2005 8:32 pm

Maybe it's me but I can't see how the puzzle in the example can "now be solved easily". Then again it does take me a matter of days to solve the Fiendish puzzles so maybe I'm not destined for the Very Hard, but would someone please explain the moves to me, just in case I do have a small hope of understanding it?

I do understand the theory of the x-wings technique and how the solver got there, I just don't see how it's a puzzle solving technique, really.

Thanks

Luna :?:

by **Animator** » Wed Apr 27, 2005 8:55 pm

Ok, here we go:

If you take the puzzle and write down where 6 can go then you get this: (the question mark is used to indicate the possibility, if the 6 is already fixed/placed then there is no question mark):

Code: Select all: * 4 3 | 9 8 6? | 2 5 6? | 6 * * | 4 2 5 | * * * | 2 * * | * 6? 1 | 6? 9 4 | ----------------------- 9 6? 6? | * * 4 | 6? 7 6? | 3 * * | 6 * 8 | * * * | 4 1 6? | 2 * 9 | 6? 6? 3 | ----------------------- 8 2 6? | 5 6? 6? | 6? 6? 6? | * 6? 6? | * 4 6? | 6? 6? 5 | 5 3 4 | 8 9 6? | 7 1 6? |

Now, when you look at row 1 and row 9 you will see that 6 can go in the same columns in both rows:
Row1: 6 only possible in column 6 and column 9
Row9: 6 only possible in column 6 and column 9

Assume the following things:
a) r1c6 = 6, then r9c6 can't be 6, so r9c9 has to be 6,
b) r1c9 = 6, then r9c9 can't be 6, so r9c6 has to be 6,
c) r9c6 = 6, then r1c6 can't be 6, so r1c9 has to be 6,
d) r9c9 = 6, then r1c9 can't be 6, so r1c6 has to be 6,

those are the only possiblities...

Now if you would fill in 6 in r8c6 (for example), then either row1 or row9 is missing a 6...

This means that you now know that there is no 6 in r2c6 until r8c6, and in r2c9 until r8c9

(And this is particular intresting for r7c9, since that cell can only have 6 or 9, but we just said is impossible..., so you can fill it in)

Does this make any sense to you?

by **Guest** » Wed Apr 27, 2005 10:20 pm

So far, so good. But the magnificent x-wings has only enabled me to put a 9 in r7c9 and subsequently, a 9 in r5c7...I'm still stuck!

by **Sue De Coq** » Wed Apr 27, 2005 10:58 pm

Here are the next five moves, which will hopefully be enough to set you on your way:

The cell r5c8 is the only candidate for the value 4 in Row 5.
The cell r8c8 is the only candidate for the value 2 in Column 8.
The value 6 is the only candidate for the cell r9c9.
The value 3 is the only candidate for the cell r7c8.
The value 8 is the only candidate for the cell r2c8.

by **lunababy_moonchild** » Thu Apr 28, 2005 9:22 pm

Animator,

Yes it makes sense, mostly, except for "This means that you now know that there is no 6 in r2c6 until r8c6, and in r2c9 until r8c9 ", if you wouldn't mind clarifying that for me I'd be grateful.

Thanks for the help though, I'd gotten to the same place as Charlotte but the subsequent moves from Sue helped me out enormously - aren't they obvious once they're pointed out? *slaps forehead, gently*

Thanks

Luna

by **Animator** » Fri Apr 29, 2005 7:08 am

Well,

think about column 6: and look at the number 6 .

The only valid place to put it is row 1 or row 9, if you put it at any other row, then there will be a row left without a 6:

Example,

Assume you put 6 in r8c6: ==> r1c6 can't have 6, ==> r1c9 has a 6
but if we look at row9 now, you see that it can't have a 6 at alll: it needs a 6 in column 6 or column 9, but both columns already have it...

You can eliminate all other 6'"s from column and oclumn 9 by this (except the ones in row1 and row9):

Which means you can remove the 6 from the possibility list in the following cells: ro7c6 , r8c6, r4c9 and r7c9,

by **lunababy_moonchild** » Fri Apr 29, 2005 8:43 am

Animator,

Thanks for explaining, I just didn't understand what you were getting at by that phrase - but I do now!

Luna

Sudoku Players' Forum (clone)

x wings

x wings

x wings

Who is online