SudoCue Users Forum Index SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net
 
 FAQFAQ   SearchSearch   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Algorithm for identification of the XY wing from the Sudoku

 
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips
View previous topic :: View next topic  
Author Message
IUSUT
Rookie
Rookie


Joined: 11 Feb 2007
Posts: 5
Location: ROMANIA

PostPosted: Sun Mar 25, 2007 10:19 pm    Post subject: Algorithm for identification of the XY wing from the Sudoku Reply with quote

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/viewtopic.php?t=99&sid=da2df1dee2df9a7518ec5da5950a99c1

In the study
„Algorithm for identification of the XY wing from the Sudoku grid”
attached to the site:
http://www.sudoku.org.uk/discus/messages/2/3787.html?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
Back to top
View user's profile Send private message
mhparker
Grandmaster
Grandmaster


Joined: 20 Jan 2007
Posts: 345
Location: Germany

PostPosted: Mon Mar 26, 2007 2:08 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
IUSUT
Rookie
Rookie


Joined: 11 Feb 2007
Posts: 5
Location: ROMANIA

PostPosted: Fri Mar 30, 2007 5:03 pm    Post subject: Added information on the essay XY wing Reply with quote

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
Back to top
View user's profile Send private message
mhparker
Grandmaster
Grandmaster


Joined: 20 Jan 2007
Posts: 345
Location: Germany

PostPosted: Sun Apr 01, 2007 11:22 pm    Post subject: Reply with quote

Quote:
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
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips 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