Algorithm for identification of the XY wing from the Sudoku

If you invented that new way to solve these little puzzles, tell us about it
Post Reply
IUSUT
Rookie
Rookie
Posts: 5
Joined: Sun Feb 11, 2007 12:20 pm
Location: ROMANIA

Algorithm for identification of the XY wing from the Sudoku

Post by IUSUT »

XY wing is a powerful technique of abstract, which has the disadvantage that the third cells of the chain can be laborious identified. Specially the beginners meet with difficulties in finding XY wing model, and insistently solicit help on web sites:
http://www.intosudoku.com/forum/viewtop ... a5950a99c1

In the study
„Algorithm for identification of the XY wing from the Sudoku grid”
attached to the site:
http://www.sudoku.org.uk/discus/message ... 1174859479

I propose a simple method for identification of the XY wing, which I submit to your analysis.
I'm using now almost exclusively the graphic variant with nonagon, in order to identify XY models from grids.

Mihail Iusut, Romania
mhparker
Grandmaster
Grandmaster
Posts: 345
Joined: Sat Jan 20, 2007 10:47 pm
Location: Germany

Post by mhparker »

Mihail,

Thanks very much for sharing your work with us (both this one and the one on Remote Pairs). I particularly like your presentation of the topics in the form of scientific papers.

Although the XY-Wing technique is already relatively well-known, I hadn't read anything about how to identify them in practice before. Both approaches (table and nonagon) appear promising. As far as the table approach is concerned, it took me a few minutes to work out how to use it, which wasn't clear to me from your description. I eventually came up with the following technique (which is perhaps what you meant?):

1) For each column in turn, for each highlighted entry, examine the second digit in the highlighted pair

2) Now run down the column for this second digit. For each highlighted pair, run back along the row to the first column. If this entry is also highlighted, we have found a candidate XY-Wing situation that needs to be examined further.

As to the nonagon approach, that would certainly be a great-looking way of displaying available pairs in a solver, especially if it's implemented as a two-way tool (i.e., being able to click on one of the lines in the diagram in order to highlight the cells containing that pair).

Once again, many thanks, and please keep us posted on any other articles of this nature you write in the future.
Cheers,
Mike
IUSUT
Rookie
Rookie
Posts: 5
Joined: Sun Feb 11, 2007 12:20 pm
Location: ROMANIA

Added information on the essay XY wing

Post by IUSUT »

Dear mhparker
Thank you for your appreciation on my modest study on the identification of XY wing. On all the sites I have observed the tendency to make Sudoku more abstract and everybody seems to forget that Sudoku is, first of all, a game. I, as a beginner, felt the need for a didactical explanation of some fundamental solving techniques, which would allow Sudoku players an initiation.
I think you are right: some ideas in my study (as the one with ranking the bivalue cells with the help of tables) must be more clearly explained. After I have received observations on forums, I think I will re-write the study. You will find below some completions on the use stages for the table, in helping to identify the XY wing model.
MIHAIL
mhparker
Grandmaster
Grandmaster
Posts: 345
Joined: Sat Jan 20, 2007 10:47 pm
Location: Germany

Post by mhparker »

Thank you for your appreciation on my modest study on the identification of XY wing.
No problem - it was a pleasure to read!

Chains, loops, almost locked sets and so on are certainly difficult for beginners to get into, most of whom would be completely out of their depth trying to follow the various forum threads on these topics. So there's definitely a need for simplified treatments of these topics for instructive purposes. Also useful is any form of consolidation of the individual techniques (i.e., documentation of the interrelationships between them), and generalisation of the techniques to cover Sudoku variants such as Jigsaws.

For example, in jigsaws, the geometrical constraints disappear to a large extent, so the only generic way of identifying the pincer cells in an XY-Wing is to look for the 2 cells of the trio that are not peers of each other.

As a second example, have you noticed that nearly all solving guides talk about XY-Wing, XYZ-Wing and WXYZ-Wing, but not WXY-Wing (the logical extension of the XY-Wing with the addidition of one more bivalued pincer cell)? The addition of an optional Z candidate on the pivot (transforming an XY-Wing into an XYZ-Wing and a WXY-Wing into a WXYZ-Wing (type I), respectively) is an independent operation. So a discussion about how the various wing formations relate to each other would be very useful.
Cheers,
Mike
Post Reply