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 

What is this technique/pattern called?

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



Joined: 10 Feb 2006
Posts: 15

PostPosted: Thu May 04, 2006 9:31 pm    Post subject: What is this technique/pattern called? Reply with quote

This puzzle appeared at www.onlysudoku.com.

Code:
+------------+-----------+------------+
|  .   .   . | .   1   . |  .   2   . |
|            |           |            |
|  .   3   . | 4   .   . |  5   .   . |
|            |           |            |
|  .   .   6 | 7   .   8 |  .   .   . |
+------------+-----------+------------+
|  .   .   . | 2   .   . |  .   9   . |
|            |           |            |
| 4   .    . | .   .   . |  .   .   1 |
|            |           |            |
|  .   8   . | .   .   5 |  .   .   . |
+------------+-----------+------------+
|  .   .   . | 3   .   2 |  8   .   . |
|            |           |            |
|  .   .   1 | .   .   9 |  .   4   . |
|            |           |            |
|  .   7   . | .   6   . |  .   .   . |
+------------+-----------+------------+



After solving 34 cells, the remaining puzzle appears as follows:


Code:
+--------------+----------------+-----------------+
| 57  45   578 |  9     1    3  |   46    2   468 |
|              |                |                 |
|  1   3    89 |  4     2    6  |    5    7    89 |
|              |                |                 |
|  2  49     6 |  7     5    8  |    1    3    49 |
+--------------+----------------+-----------------+
|  6   1    37 |  2     8    4  |   37    9     5 |
|              |                |                 |
|  4  59  2359 |  6    39    7  |   23    8     1 |
|              |                |                 |
| 79   8  2379 |  1    39    5  | 2347    6    34 |
+--------------+----------------+-----------------+
| 59   6    59 |  3     4    2  |    8    1     7 |
|              |                |                 |
|  8   2     1 |  5     7    9  |   36    4    36 |
|              |                |                 |
|  3   7     4 |  8     6    1  |    9    5     2 |
+--------------+----------------+-----------------+


The 5,7,9 chain at r1c1 (5,7), r1c6 (7,9) and r5c2 (5,9) establishes that either r1c1 or r5c2 must be 5; therefore, since r1c2 can not also be 5, r1c2 must equal 4. When r1c2 is set at 4, the puzzle collapses.

In a similar manner, r4c3 (3,7), r6c1 (7,9) and r6c5 (3,9) form a 3,7,9 chain. Since either r4c3 or r6c1 must equal 7, the 7 in r6c3 can be removed.

Questions: (1) Although I have read about this “pattern” some months ago, I don’t remember where this “pattern” is described (Also, until I was working on this puzzle, I wasn’t able to “get my head around” this technique). Does someone know what this technique is called and/or where it is discussed?; and (2) Can this puzzle be solved using some other solution path?

Once again, I very much appreciate your comments.

Paladin
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Thu May 04, 2006 11:23 pm    Post subject: The first one's an XY-Wing Reply with quote

Hi, Paladin!

The first "chain" you mentioned (r1c1 - r6c1 - r5c2) is called an XY-Wing. It's usually analyzed from the "corner", which lies at r6c1.

A. r6c1 = 7 ==> r1c1 = 5 ==> r1c2 = 4
B. r6c1 = 9 ==> r5c2 = 5 ==> r1c2 = 4

I don't quite follow the logic you used to eliminate "7" at r6c3; what I see here is another XY-Wing which allows us to eliminate the "3" at r6c3:

A. r6c1 = 7 ==> r4c3 = 3 ==> r6c3 <> 3
B. r6c1 = 9 ==> r6c5 = 3 ==> r6c3 <> 3

The XY-Wing is the simplest possible form of the "double-implication chain" technique, which has been extensively analyzed in this forum. This message contains quite a few links to disussions of the XY-Wing technique.

Paladin wrote:
Can this puzzle be solved using some other solution path?

The first XY-Wing pattern you mentioned is probably the most direct route to the solution. But quite a few "forcing chains" are also available here. Here's one of the shorter ones.
Code:
+--------------+----------------+-----------------+
| 57  45   578 |  9     1    3  |   46    2   468 |
|              |                |                 |
|  1   3    89 |  4     2    6  |    5    7    89 |
|              |                |                 |
|  2  49     6 |  7     5    8  |    1    3    49 |
+--------------+----------------+-----------------+
|  6   1    37 |  2     8    4  |   37    9     5 |
|              |                |                 |
|  4  59  2359 |  6    39    7  |   23    8     1 |
|              |                |                 |
| 79   8  2379 |  1    39    5  | 2347    6    34 |
+--------------+----------------+-----------------+
| 59   6    59 |  3     4    2  |    8    1     7 |
|              |                |                 |
|  8   2     1 |  5     7    9  |   36    4    36 |
|              |                |                 |
|  3   7     4 |  8     6    1  |    9    5     2 |
+--------------+----------------+-----------------+

A. r2c3 = 9 ==> r3c2 = 4 ==> r1c2 = 5
B. r2c3 = 9 ==> r7c3 = 5 ==> r7c1 = 9 ==> r6c1 = 7 ==> r1c1 = 5

But we can't have two "5"s in row 1, so r2c3 <> 9, and we must have r2c3 = 8. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Marty R.



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

PostPosted: Fri May 05, 2006 5:25 pm    Post subject: Reply with quote

Paladin,

I also don't see how you eliminated that "7" at r6c3.

Quote:
In a similar manner, r4c3 (3,7), r6c1 (7,9) and r6c5 (3,9) form a 3,7,9 chain. Since either r4c3 or r6c1 must equal 7, the 7 in r6c3 can be removed.

The hypothesis that "either r4c3 or r6c1 must equal 7" appears to be invalid since there is a third occurrence of "7" in box 4.
Back to top
View user's profile Send private message
dejsmith



Joined: 23 Oct 2005
Posts: 40

PostPosted: Sat May 06, 2006 11:13 pm    Post subject: Hidden Pair Reply with quote

Guys

I realize you were only addressing Paladin's immediate question; & I am really only writing to let David, Keith, & Someone (when he returns) know I am still alive; but this puzzle should not even get one worrying about such techniques since there is a hidden pair in R1C1&3 (57) that serves to solve the puzzle. I make it a point to always read your comments on this site & the Sudocue/Nightmare site. Thanks for reviewing XY Wing, though, as I have not had the opportunity to use it lately.

Dave
Back to top
View user's profile Send private message
Paladin



Joined: 10 Feb 2006
Posts: 15

PostPosted: Sun May 07, 2006 12:22 am    Post subject: Reply with quote

Dear David and Marty:

Thank you for your responses.

It seems that I may have confused this issue because I did not arrive at my conclusions, in either case, with reference to the “corner” analysis that is apparently applicable to the XY Wing rule. Since I did not understand how to correctly apply the XY Wing rule by using the “corner” concept, I used the following thought processes:

r1c1, r6c1 and r5c2 represent a “chain” where either 5,7 or 9 must appear in these cells. As it relates to the “chain”, the value 5 must appear in either f1c1 or r5c2; therefore, since r1c2 is encapsulated within, or impacted by, this certainty, r1c2 can not equal 5.

Having more fully described my thoughts, it is perhaps easier to see why I excluded 7 from r6c3, as follows:

r4c3 (3,7), r6c1 (7,9) and r6c5 (3,9) are a 3,7, 9 chain. Within that chain, the value 7 can only, and must, appear at either r4c3 or r6c1. Since r6c3 is encapsulated within, or impacted by, this certainty, r6c3 can not equal 7.

Now, having reflected upon your conclusion that an XY wing also excludes 3 from r6c3, the following has occurred to me:

Because of the relative locations of the 3,7,9 chain, (r4c3, r6c1 and r6c5), the value of r6c3 is dependent upon the values of all the cells which form the 3.7,9 chain. In this case, and based upon the positioning of the “chain” cells, 3,7 and 9 can all be removed from r6c3. R6c3 must, and in the final analysis does, equal 2.

I can see that applying this “new” (or at least new to me) chain analysis will be very helpful. I have noticed many chains which involve 3 values where the chains (although linked) are “fractured” into varying blocks, rows and columns.

Your thoughts?

Paladin

For your convenience, the puzzle is as follows:

Code:
+--------------+----------------+-----------------+
| 57  45   578 |  9     1    3  |   46    2   468 |
|              |                |                 |
|  1   3    89 |  4     2    6  |    5    7    89 |
|              |                |                 |
|  2  49     6 |  7     5    8  |    1    3    49 |
+--------------+----------------+-----------------+
|  6   1    37 |  2     8    4  |   37    9     5 |
|              |                |                 |
|  4  59  2359 |  6    39    7  |   23    8     1 |
|              |                |                 |
| 79   8  2379 |  1    39    5  | 2347    6    34 |
+--------------+----------------+-----------------+
| 59   6    59 |  3     4    2  |    8    1     7 |
|              |                |                 |
|  8   2     1 |  5     7    9  |   36    4    36 |
|              |                |                 |
|  3   7     4 |  8     6    1  |    9    5     2 |
+--------------+----------------+-----------------+
Back to top
View user's profile Send private message
TKiel



Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI

PostPosted: Sun May 07, 2006 12:26 pm    Post subject: Reply with quote

Paladin,

What you are saying is that any cell that 'sees' all three cells of an XY-wing can't contain any of the digits that make up the XY-wing.

It definitely works for this puzzle but I'm not sure that should be taken as proof that it will always work. I'd post it at
Sudoku.com to see if somebody there can yea or nay it, which somebody will definitely do.
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Sun May 07, 2006 12:53 pm    Post subject: Reply with quote

dejsmith wrote:
... there is a hidden pair in R1C1&3 (57)

No, because r1c2 also contains a 5.

Paladin wrote:

r4c3 (3,7), r6c1 (7,9) and r6c5 (3,9) are a 3,7, 9 chain. Within that chain, the value 7 can only, and must, appear at either r4c3 or r6c1.

No, it also could appear in r4c7 and r6c3.
Code:
+--------------+----------------+-----------------+
|  6   1    3  |  2     8    4  |    7    9     5 |
|              |                |                 |
|  4   5    2  |  6     9    7  |    3    8     1 |
|              |                |                 |
|  9   8    7  |  1     3    5  |    2    6     4 |
+--------------+----------------+-----------------+
Quote:

Because of the relative locations of the 3,7,9 chain, (r4c3, r6c1 and r6c5), the value of r6c3 is dependent upon the values of all the cells which form the 3.7,9 chain.

Since r4c3 and r6c5 dont share a unit, the 3 cells do not work like a triple: Both of the 2 cells can contain a 3, so 7 and 9 are still possible in r6c3:
Code:
+--------------+----------------+-----------------+
|  6   1     3 |  2     8    4  |    7    9     5 |
|              |                |                 |
|  4   5     2 |  6     9    7  |    3    8     1 |
|              |                |                 |
|  7   8     9 |  1     3    5  |    2    6     4 |
+--------------+----------------+-----------------+
Back to top
View user's profile Send private message
Paladin



Joined: 10 Feb 2006
Posts: 15

PostPosted: Mon May 08, 2006 9:46 pm    Post subject: Reply with quote

ravel,

Thank you very much for taking the time to share your Sudoku knowledge and expertise with us. I understand that you have indicated that a three value, three cell “chain” (configured as: xy, xz, yz) does not act as a “triple” unless all three cells share the same “unit” (i.e., the same row/column/box).

I guess my question, however, is: “Why do these non-unitary cells (r4c3, r6c1 and r6c5), apparently at least in this particular case, function as a “triple”?

Comments, anyone?

Paladin

PS- Although I do not know if this is relevant to this discussion, I do notice that this grid contains a non-productive swordfish of 7s at r1c13, r4c37 and r6c137. The grid in question appears as follows:

Code:
+--------------+----------------+-----------------+
| 57  45   578 |  9     1    3  |   46    2   468 |
|              |                |                 |
|  1   3    89 |  4     2    6  |    5    7    89 |
|              |                |                 |
|  2  49     6 |  7     5    8  |    1    3    49 |
+--------------+----------------+-----------------+
|  6   1    37 |  2     8    4  |   37    9     5 |
|              |                |                 |
|  4  59  2359 |  6    39    7  |   23    8     1 |
|              |                |                 |
| 79   8  2379 |  1    39    5  | 2347    6    34 |
+--------------+----------------+-----------------+
| 59   6    59 |  3     4    2  |    8    1     7 |
|              |                |                 |
|  8   2     1 |  5     7    9  |   36    4    36 |
|              |                |                 |
|  3   7     4 |  8     6    1  |    9    5     2 |
+--------------+----------------+-----------------+


Last edited by Paladin on Mon May 08, 2006 11:04 pm; edited 1 time in total
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Mon May 08, 2006 10:53 pm    Post subject: Reply with quote

Paladin wrote:

I guess my question, however, is: “Why do these non-unitary cells, apparently at least in this particular case, function as a “triple”?

i would say, accidently, just like a lucky guess.
Quote:

I do notice that this grid contains a non-productive swordfish of 7s at r1c13, r4c37 and r6c137.

Nice swordfish, but it does not help you.
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