dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Quick and efficient xy-wing searches

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Sun Oct 15, 2006 5:55 pm    Post subject: Quick and efficient xy-wing searches Reply with quote

Quick and efficient xy-wing searches

I thought I would port this posting of mine over from the Players Forum. Note that an xy-wing consists of three bivalued cells, two of which see the same middle cell. The content of the cells is something like ab, bc, ac.

I use a staged search for xy-wings.

First search for two cells of an xy-wing in each box. If your two cells do not share a row or column, then this tends to be your most fruitful pairing since it maximizes your opportunities for completing the xy-wing (24 cells) and it has the maximum number of cells where a reduction can take place once the xy-wing is completed (5).

In the grids below, the starred cells in the first grid indicate where you can search for a cell containing (ac) which would complete the xy-wing, and the minus signs in the next grid indicate cells where a reduction caused by the completed xy-wing can take place. If your middle cell is (ab) then you eliminate c's from the reduction cells. Otherwise, your middle cell is (bc) and you eliminate a's from the reduction cells
Code:

+----------+----------+----------+  +----------+----------+----------+
| *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
+----------+----------+----------+  +----------+----------+----------+
| ab .  .  | *  *  *  | *  *  *  |  | ab -  -  | .  ac .  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| .  bc .  | *  *  *  | *  *  *  |  | .  bc .  | -  -  -  | .  .  .  |
+----------+----------+----------+  +----------+----------+----------+
| *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| *  *  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
+----------+----------+----------+  +----------+----------+----------+


If the first two xy-wing cells in a box share a row or column, then you only have the 12 cells perpendicular to your pair to complete the xy-wing, but you still retain 5 cells where a reduction could take place
Code:

+----------+----------+----------+  +----------+----------+----------+
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
+----------+----------+----------+  +----------+----------+----------+
| ab .  .  | *  *  *  | *  *  *  |  | ab .  .  | -  -  -  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| bc .  .  | *  *  *  | *  *  *  |  | bc -  -  | .  .  ac | .  .  .  |
+----------+----------+----------+  +----------+----------+----------+
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
+----------+----------+----------+  +----------+----------+----------+


The least fruitful three-box xy-wings should be scanned for last. These xy-wings start with one bivalue cell in a box. Assuming you have already scanned for the above two types, there are 12 cells where you can find the second leg of the xy-wing, and, from there, 12 more cells where you can find the completion. From the completed xy-wing of this type there is only a single cell where a deduction might be made.
Code:

+----------+----------+----------+  +----------+----------+----------+
| ab .  .  | *  *  *  | *  *  *  |  | ab .  .  | .  .  -  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
+----------+----------+----------+  +----------+----------+----------+
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| bc .  .  | *  *  *  | *  *  *  |  | bc .  .  | .  .  ac | .  .  .  |
+----------+----------+----------+  +----------+----------+----------+
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
| .  .  .  | .  .  .  | .  .  .  |  | .  .  .  | .  .  .  | .  .  .  |
+----------+----------+----------+  +----------+----------+----------+

Note that the three-box xy-wing must have at least one cell in boxes 1, 3, 5, 7, or 9. Thus you can restrict your initial cell searches for this final case to those five boxes (or five similarly oriented ones such as 1, 2, 4, 5, 9). You can use this limiting feature to minimize the number of starting cells you have to consider.

In all cases, as you are scanning for the completion of your xy-wing, it doesn't hurt to keep an eye open for an extra bivalue cell or an ALS which can also result in a deduction.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5128
Location: Rochester, NY, USA

PostPosted: Sun Oct 15, 2006 9:14 pm    Post subject: Reply with quote

Thanks. Good info.
Back to top
View user's profile Send private message
TexCat



Joined: 07 Jul 2006
Posts: 31

PostPosted: Mon Oct 16, 2006 7:53 pm    Post subject: Reply with quote

Thank you! It seems so easy on a grid with only *'s and -'s. I wonder why I have so much trouble spotting them in a real grid. Embarassed
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles 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