View previous topic :: View next topic 
Author 
Message 
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Posted: Tue Oct 11, 2005 12:33 am Post subject: "XYWing" Example #3 


This is a continuation from "A Very Tough Minimal Sudoku."
Someone_Somewhere wrote:  Hi,
This one is a "Leckerbissen". You will need Xwing and XYwing.
010007030
000005000
062010840
370800000
008060200
000001089
089020350
000400000
050300060
see u, 
This puzzle is actually fairly simple, to start. After 19 more or less routine moves I arrived at this position:
Code: 
8/9 1 4/5 2/6 4/8 7 5/6/9 3 2/5/6
8/9 3/4 3/7 2/6 4/8 5 1/7 2/9 1/2/6
5/7 6 2 9 1 3 8 4 5/7
3 7 4/5/6 8 9 2 4/5/6 1 4/5/6
1 9 8 5 6 4 2 7 3
2/5 2/4 4/5/6 7 3 1 4/5/6 8 9
4/7 8 9 1 2 6 3 5 4/7
6 2/3 3/7 4 5 8/9 1/7 2/9 1/2/8
2/4 5 1 3 7 8/9 4/9 6 2/4/8 
I did use the "XWing" before I reached this spot  it was fairly obvious because of the {5,7} and {4, 7} pairs on the ends of rows 3 & 7, respectively. That allowed me to eliminate some possible "7"s in columns 1 and 9. The "XYWing" was extremely hard to spot, imho.
Anyway, it's in r9c1, r9c7, r8c8, and r9c9. Look at the cell r8c8. If that's a "2" we can't have the possibility "2" in r9c9. If it's a "9" r9c8 must be a "4", and r9c1 must be a "2", so we still can't have a "2" at r9c9. Whichever way we enter the value at r8c8, then, we must have a "2" at r9c1 (only place left for it in that row).
Thanks for a great puzzle! dcb 

Back to top 


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

Posted: Tue Oct 11, 2005 7:38 pm Post subject: "XYWing Example #4 


Someone_Somewhere wrote:  Hi,
Now it should not be a problem to find the XYwing from this one:
900500362
253900810
601203950
069032085
100608039
300490076
530004698
890300741
010809523
see u, 
This one was easy  you gave me so many numbers to start that all I had to do was look for the "XYWing." And I found it!
The critical cell is r8c5, which has the possibilities {2, 5, 6}. We also have r9c5, which might contain {6, 7}; r5c5, which might contain {5, 7}; and r8c6, which might contain {5, 6}.
We see that if r9c5 is a "6", r8c6 must be a "5". And if r9c5 is a "7", then r5c5 must be a "5". Either way, r8c5 cannot be a "5". Eliminating that possibility reveals a naked pair {2, 6} in r8c3 & r8c5, from which we conclude that r8c6 = 5. The rest of the puzzle is simple. dcb 

Back to top 


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

Posted: Tue Oct 11, 2005 8:36 pm Post subject: "XYWing" Example #5 is really #1! 


Someone_Somewhere wrote:  Hi,
From this one:
020000000
000600003
074080000
000003002
080040010
600500000
000010780
500009000
000000040
you can eliminate 5 numbers using XYwing. 
Hey! I already worked this puzzle. It's the same as Example #1.
Code:  Example 1 Example 5
000010780 020000000
500009000 000600003
000000040 074080000
026000000 000003002
000600003 080040010
074080000 600500000
000003002 000010780
080040010 500009000
600500000 000000040 
As you can see from the above sidebyside comparison, these two puzzles are just permutations of the same thing. In fact, if you strip the bottom three rows from "#5" and move them to the top everything matches up exactly except for the "6" in r4c3 on "#1"  but that "6" is an easy deduction, anyway, so these two puzzles are equivalent. dcb 

Back to top 


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

Posted: Wed Oct 12, 2005 4:46 pm Post subject: "XYWing" Example #5 


Someone_Somewhere wrote:  Hi,
In this one I could find also 1 XYwing:
000000021
500040000
000000070
000300600
000020500
010000000
600000203
003107000
000008000
see u, 
This one is actually quite simple for the first 47 moves. Then it gets a bit sticky. I won't give it away entirely, but the "xywing" is in the top left and middle left 3x3 boxes when you get down to just 15 open squares.
I had some trouble spotting this one, and actually found it easier to complete the solution by determining the contents of r9c1 via two very short "forcing chains" in the middle left and bottom left 3x3 boxes. dcb 

Back to top 


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

Posted: Wed Oct 12, 2005 7:19 pm Post subject: "XYWing" Example #6 


Someone_Somewhere wrote:  Hi,
I got stucked after finding 33 numbers with this one:
400000001
080400000
000000000
000700850
001900000
200000000
030006080
600010400
XYwing solved it.
see u, 
What's up with this one? It only has 8 rows. And there are only 16 nonzero digits in those 8 rows.
I'd add an empty row and give it a try, except for one thing: I don't believe it's possible to construct a 16clue Sudoku puzzle with a unique solution. dcb 

Back to top 


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

Posted: Wed Oct 12, 2005 7:52 pm Post subject: "XYWing" Example #7 


Someone_Somewhere wrote:  Ok, one with hidden pair, Xwing and XYwing:
500000000
400070006
908405000
010003090
005209600
040800020
000604503
700020004
000000009
By now, the coffee should be still hot after you have solved it!
see u, 
I didn't spot an XWing or an XYWing. I did solve the puzzle, though, by noticing a very short forcing chain in the early going.
After finding nine numbers I arrived at this position: Code: 
5 . 6/7 . . . . . .
4 2/3 1 . 7 . . 5 6
9 . 8 4 . 5 . 1/3 .
2 1 6/7 5/7 4/5/6 3 . 9 5/7/8
3/8 7/8 5 2 1/4 9 6 . .
3/6 4 9 8 1/5/6 1/6/7 1/3/7 2 1/5/7
1/8 8/9 2 6 1/8/9 4 5 7 3
7 5/9 3 5/9 2 1/8 1/8 6 4
1/6/8 . 4 . . 1/7/8 2 1/8 9 
I was looking for a way to proceed, and was in fact searching for an "XYWing" pattern when I noticed something else. There are only two cells (r4c4 & r6c6) where a "7" can fit in the middle center 3x3 box. And the two pairs {6, 7} and {5, 7} in r4c3 & r4c4 seem fairly important. That's when I saw the forcing chain.
I wanted to demonstrate that r4c3 = 6. So I considered what would happen if I entered either a "5" or a "7" in r4c4. Obviously, if r4c4 = 7 then r4c3 = 6, and that's the end of it.
What happens if r4c4 = 5? Well, then we get a beautiful forcing chain:
r4c4 = 5 ==> r8c4 = 9
This creates a {1, 8} pair in the bottom center 3x3 box, in r7c5 & r8c6, to be precise. But then we must have
r8c4 = 9 ==> r9c6 = 7
and now the "7" cannot possibly fit in the middle center 3x3 box!
I concluded that r4c4 = 7 and that r4c3 = 6, and the rest of the puzzle crumbled like a piece of cheese. dcb 

Back to top 


alanr555
Joined: 01 Aug 2005 Posts: 194 Location: Bideford Devon EX39

Posted: Wed Oct 12, 2005 9:55 pm Post subject: Re: "XYWing" Example #3 


> After 19 more or less routine moves I arrived at this position:
(rows 7,8,9 only shewn here)
> 4/7 8 9 1 2 6 3 5 4/7
> 6 2/3 3/7 4 5 8/9 1/7 2/9 1/2/8
> 2/4 5 1 3 7 8/9 4/9 6 2/4/8
> The "XYWing" was extremely hard to spot, imho.
No need to be so humble about it, it WAS extremely hard!!
It calls for revision of the definition.
We are concerned with four cells  the relationship between three of them
leading to a conclusion about the fourth. What are the constraints on
the three? Is it sufficient that they are all linked so that any pair are in
fact linked by row, column or region?
Here we have r8c8, r9c1, r9c7.
They spread over two rows. Two of the cells are linked by row but the
other two are linked by region, not column. In other words the Yaxis
is a bit skewed (c8 not being column 7!)
So: xaxis is r9c1 to r9c7  fine
and yaxis is r9c7 to r8c8  not so obvious!
> Anyway, it's in r9c1, r9c7, r8c8, and r9c9. Look at the cell r8c8. If that's > a "2" we can't have the possibility "2" in r9c9. If it's a "9" r9c8 must be > a "4", and r9c1 must be a "2", so we still can't have a "2" at r9c9.
> Whichever way we enter the value at r8c8, then, we must have a "2"
> at r9c1 (only place left for it in that row).
Undoubtedly the logic works IN THIS CASE.
However, what is the GENERAL rule?
What features of this case confirm that it is eligible for the general rule?
Row 8 has more than two occurences of digit 2.
Would the result be the same if row nine had more than two digits 2?
In this case three of the four cells involved are in one line and I suspect
that a further '2' candidate in line 9 would invalidate the conclusion here;
but when there is a RECTANGLE formed by the four cells, the presence
of further cells with the same candidate numbers is irrelevant.
Can anyone please refine the specification?
Alan Rayner BS23 2QT 

Back to top 


someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich

Posted: Thu Oct 13, 2005 7:35 am Post subject: 


Hi,
Sorry David for cut & pastle only 8 rows.
You are good, could do it even so ... ;)
Here the entire one:
400000001
080400000
000000000
000700850
001900000
200000000
030006080
600010400
000020000
see u, 

Back to top 


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

Posted: Thu Oct 13, 2005 9:57 pm Post subject: "XYWing" Example #6 


Someone_Somewhere wrote:  Hi,
I got stucked after finding 33 numbers with this one:
400000001
080400000
000000000
000700850
001900000
200000000
030006080
600010400
000020000
XYwing solved it.
see u, 
Thanks for the extra row  that makes it simpler!
This is a fascinating puzzle. It's very simple to start out  one can place all the "1"s in the puzzle without much trouble. But it gets harder as one goes along  I'll bet I wound up in the same spot you did after 33 moves, someone.
Here's what I got to. I haven't given up on this yet  I see a couple of promising patterns at this point, but haven't got them all figured out yet. Besides, somebody else (Alan? Katie?) might want to take a crack at it.
Code: 
4 6 . 2 7/9 8 . . 1
1 8 . 4 . 3/5 2 . .
3/5 2 7/9 1 . 3/5 6/7 4 8
9 4 6 7 3 1 8 5 2
3/8 5/7 1 9 5/8 2 . . 4
2 5/7 3/8 6 5/8 4 9 1 3/7
7 3 2 5 4 6 1 8 9
6 9 5/8 3/8 1 7 4 2 3/5
5/8 1 4 3/8 2 9 . . . 
What I notice here is that there are several rows, columns, and 3x3 boxes where the number "5" can only appear in two places. These don't quite line up in rows and columns like a nice "swordfish" pattern, but they do carry the same import, I think. dcb 

Back to top 


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

Posted: Thu Oct 13, 2005 10:36 pm Post subject: Re: "XYWing" Example #3 


AlanR555 wrote:  ...
In this case three of the four cells involved are in one line and I suspect
that a further '2' candidate in line 9 would invalidate the conclusion here;
but when there is a RECTANGLE formed by the four cells, the presence
of further cells with the same candidate numbers is irrelevant.
Can anyone please refine the specification? 
The rule is that you need a quadruplet that lies in the logical equivalent of a straight line and can be separated into a "naked triplet" and the fourth value, which must stand alone.
Here's an example of an "XYWing":
Now, what would you call this pattern?
I guess most of us would call the second pattern a "naked triplet" and immediately resolve the fourth cell to an "8". But the logic involved is really the same as the logic in the "XYWing"  in either case the values {3, 5, 7} must all appear in three of the cells, leaving the "8" as the only possibility for the fourth cell.
As to what the "logical equivalent of a straight line" is, I think I'll leave the verbose definition up to someone else. Oh, here, I'll take a stab at it  the four cells must form a closed loop of some sort, so that they're the ONLY candidates for the quadruplet of values in question. dcb :)
PS You might think of the case where the four cells all lie within a single 3x3 box. These might even form a rectangle, but most of us would still see it as a triplet plus a fourth value. The "XYWing" terminology came into use, I think, because the pattern seems different, somehow, when the four cells don't all lie in the same row or column or 3x3 box. But it's fundamentally the same pattern no matter how twisted or grotesque it appears to be when mapped onto the twodimensional grid. 

Back to top 


someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich

Posted: Fri Oct 14, 2005 6:16 am Post subject: 


Hi,
Very nice remark, David.
Now it should be clear.
The only thing left is to detect it, which is not so difficult after a little bit of training.
see u, 

Back to top 


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

Posted: Fri Oct 14, 2005 3:24 pm Post subject: Re: "XYWing" Example #6 


Here's where I left this puzzle. I've filled in a bit more detail this time.
Code: 
4 6 . 2 7/9 8 ?5? . 1
1 8 . 4 . 3/5 2 . ?5?
3/5 2 7/9 1 . 3/5 6/7 4 8
9 4 6 7 3 1 8 5 2
3/8 5/7 1 9 5/8 2 . . 4
2 5/7 3/8 6 5/8 4 9 1 3/7
7 3 2 5 4 6 1 8 9
6 9 5/8 3/8 1 7 4 2 3/5
5/8 1 4 3/8 2 9 . . . 
The "XYWing" is fairly easy to spot  it's the set {3, 5, 8, 7} lying in r6c3, r8c3, r8c9, and r6c9. Since "7" is the odd man out, we can place a "7" at r6c9, and the rest of the puzzle is simple.
Interestingly, there's another way to make progress from this spot in the puzzle. Notice that there are only 2 ways the number "5" can fit in the top center 3x3 box. There are also just 2 ways to fit "5" in row 3 (at r3c1 and r1c6), in column 1 (at r3c1 & r9c1), in the bottom left 3x3 box (at r9c1 & r8c3), and in row 8 (at r8c3 & r8c9). Since there are only two alternatives at each step and these cells form a forcing chain, we can see that either there's a "5" at r2c6, at r3c1, & at r8c3, or else there's a "5" at r3c6, at r9c1, and at r8c9. Either way, then, there cannot be a "5" at r2c9 because there _must_ be a "5" either at r2c6 or at r8c9. So the "5" in the top right 3x3 box must appear at r1c7.
This "5" doesn't help as much as the "7" resulting from the "XYWing", but it does eventually allow one to solve the puzzle without reliance on the "XYWing" pattern. To do that, though, one must notice another twisted "swordfish" (like the thing with "5"), and this second one involves the possibilities for placing "3" in the puzzle. dcb 

Back to top 


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

Posted: Mon Oct 17, 2005 12:28 am Post subject: Re: "XYWing" Example #3 


David Bryant wrote:  The rule is that you need a quadruplet that lies in the logical equivalent of a straight line and can be separated into a "naked triplet" and the fourth value, which must stand alone. 
I've been thinking this over, and it's incomplete. This definition works for the case of an "XYWing" that involves four distinct values. But the "XYWing" can exist with only three values, as in the following example:
In this example the "3" has to go in the lower right corner. But there are only three distinct values involved in this formation ... my earlier description only works in the more common case, where four values appear in the "XYWing." dcb 

Back to top 


alanr555
Joined: 01 Aug 2005 Posts: 194 Location: Bideford Devon EX39

Posted: Mon Oct 17, 2005 9:49 pm Post subject: Re: "XYWing" Example #3 


Code: 
> The rule is that you need a quadruplet that lies in the logical equivalent
> of a straight line and can be separated into a "naked triplet" and the
> fourth value, which must stand alone.
Thank you for this. It makes sense  although I had never considered
the "naked triplet" aspect. They were just three corners of a rectangle!
> Here's an example of an "XYWing":
3/5 3/7
5/7 7/8
> Now, what would you call this pattern?
3/5 3/7 5/7 7/8
> I guess most of us would call the second pattern a "naked triplet" and
> immediately resolve the fourth cell to an "8". But the logic involved is
> really the same as the logic in the "XYWing"  in either case the
> values {3, 5, 7} must all appear in three of the cells, leaving the "8" as > the only possibility for the fourth cell.
Admirably (!) clear!
> As to what the "logical equivalent of a straight line" is, I think I'll leave > the verbose definition up to someone else. Oh, here, I'll take a stab at > it  the four cells must form a closed loop of some sort, so that they're > the ONLY candidates for the quadruplet of values in question. dcb :)
This is the key point.
Knowing what to do with the pattern is one thing,
Spotting its occurrence is another!
The definition would seem to allow the cells to appear in any order but
if a rectangle is the "logical equivalent of a straight line " (logequiv)
then what distinguishes it and why cannot ANY line joining four cells
be regarded as a logequiv?
In the example above.
If the {3/5 3/7 5/7} triplet is in a row or column say, what are the
constraints on the placement of the 7/8? Clearly it is OK if the 7/8 is
in the same row/column but what if it is a chessknight's move away?
Using the rectangle version, it would appear that the fourth cell is
connected to TWO of the other three cells by means of being in the
same row,column or region. Is this clue? Is it required that of the four
cells EVERY one of them MUST be connected to at least TWO of the others
by being in the same row, column or region as such other cell?
> PS You might think of the case where the four cells all lie within a single
> 3x3 box. These might even form a rectangle, but most of us would still > see it as a triplet plus a fourth value.
I always saw it as a "congruent group" and "stragglers" or "outsiders"
such that those outsiders could be eliminated. In fact, I never gave them
much thought  I just eliminated them!
> The "XYWing" terminology came into use, I think, because the pattern
> seems different, somehow, when the four cells don't all lie in the same
> row or column or 3x3 box.
> It's fundamentally the same pattern no matter how twisted or grotesque > it appears to be when mapped onto the twodimensional grid.
Yes  that is why we need to define the constraints. A set of four cells
in r1c2, r5c3, r6c8, r3c7 form a set of four cells. It is possible to join a
closed line between them and create a "grotesque" shape but I doubt
that XYwing would apply to them  or would it????
A little earlier, I suggested that any one cell of the four might need to be
"connected" to at least two of the others. Is this both a necessary and a
sufficient condition? If not what is the condition that is?



Back to top 


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

Posted: Mon Oct 17, 2005 10:43 pm Post subject: Re: "XYWing" Example #3 


AlanR555 wrote:  The definition would seem to allow the cells to appear in any order but if a rectangle is the "logical equivalent of a straight line " (logequiv) then what distinguishes it and why cannot ANY line joining four cells be regarded as a logequiv? 
OK, I'll try to clarify the notion "the logical equivalent of a straight line."
The rules of Sudoku state that each digit must appear once and only once in each column, row, and 3x3 box. So the rows, columns, and boxes are "straight lines" in the sense I want to use that term. Think of the columns, rows, and 3x3 boxes as "complete" straight lines.
Now within the context of a particular puzzle we may find groups of cells that are linked to each other logically even though they don't fall on the same "complete straight line." This usually happens with cells that can contain one of two possible values. These cells can form a "chain" that snakes through the puzzle, maybe like this:
Code: 
1/2 5/7 7/9
x x x
x x x
1/6 3/5 x
x x x
2/3 x 9/6 
Notice that in this example the cells marked as pairs are not all in the same column, or row, or 3x3 box. Nevertheless they are connected as if they did lie in a straight line  the whole structure can exist in one of two different states, either (1, 6, 9, 7, 5, 3, 2) or (2, 3, 5, 7, 9, 6, 1), starting in the upper left corner and following the natural order of the chain in each case.
The interesting case  the one that I want to call "the logical equivalent of a straight line"  is the one that doubles back on itself to form a closed loop, as in this example. It's not necessarily a "complete" straight line, because it may not contain all of the digits 1  9. But it's set up in such a way that once it's resolved each cell in the chain will contain a different value from every other cell in the chain.
That's the idea. I don't know if I can clarify it any better than that. dcb 

Back to top 


alanr555
Joined: 01 Aug 2005 Posts: 194 Location: Bideford Devon EX39

Posted: Tue Nov 15, 2005 12:18 pm Post subject: 


Code: 
> The rule is that you need a quadruplet that lies in the logical equivalent
> of a straight line and can be separated into a "naked triplet" and the
> fourth value, which must stand alone.
> I've been thinking this over, and it's incomplete. This definition works
> for the case of an "XYWing" that involves four distinct values. But
> the "XYWing" can exist with only three values, as in the following
> example:
3/5 5/7
3/7 3/7
> In this example the "3" has to go in the lower right corner. But there
> are only three distinct values involved in this formation ... my earlier
> description only works in the more common case, where four values
> appear in the "XYWing." dcb
The definition would seem to allow the cells to appear in any order but if a rectangle is the "logical equivalent of a straight line " (logequiv) then what distinguishes it and why cannot ANY line joining four cells be regarded as a logequiv?
> OK, I'll try to clarify the notion "the logical equivalent of a straight line."
> Now within the context of a particular puzzle we may find groups of
> cells that are linked to each other logically even though they don't fall
> on the same "complete straight line." This usually happens with cells
> that can contain one of two possible values. These cells can form
> a "chain" that snakes through the puzzle
Yes. That sort of chain is an essential ingredient in the consideration
of the socalled "colouring" technique.
> The interesting case  the one that I want to call "the logical
> equivalent of a straight line"  is the one that doubles back on
> itself to form a closed loop.
Yes, closed loops enjoy atributes that open chains do not.
> Once it's resolved each cell in the chain will contain a different value
> from every other cell in the chain.
++++++++++++
This last contention seems open to challenge. It is not necessary for
a closed loop to have distinct values following resolution. Certainly
the chains used in colouring (which may be closed loops) do not have
this feature. In a chain of length 7 or 8, it is quite likely that the third
or fourth value has no DIRECT relationship with the first or seventh
and so may easily have the same value. Indeed the example quoted of
an XYwing with only three distinct digits MAY be regarded as a closed
loop.
The other aspect of closed loops is that the route from start to finish
may be different according to the initial value.
(2,3)  (3,4)  (4,5)  (5,6)  (6,2)  (2,3)
may have the same end points as
(2,3)  (2,7)  (7,8)  (8,9)  (9,3)  (2,3)
but get there by a completely different route.
(NB  the 2/3 cells at start/end are the SAME cell.)
Thus, we may need to refine the definitions a bit more so that we
include or exclude various patterns.
Alan Rayner BS23 2QT



Back to top 


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

Posted: Tue Nov 15, 2005 5:20 pm Post subject: The Logical Equivalent of a Straight Line 


AlanR555 wrote:  David Bryant wrote:  Once it's resolved each cell in the chain will contain a different value from every other cell in the chain. 
++++++++++++
This last contention seems open to challenge. 
No, it isn't. You simply forgot what we were talking about.
You asked me to define the "logical equivalent of a straight line." I did so. Then you asked for clarification, which I provided. I will reiterate.
The logical equivalent of a straight line is a forcing chain that forms a closed loop within a puzzle such that, when the cells in the chain have been resolved, each cell in the chain contains a different value. If the chain contains nine cells, it is a "complete" straight line. If it contains fewer than nine cells, it is "incomplete."
It's my concept, and that's how it's defined.
In particular, the rows and columns and 3x3 boxes are "complete" straight lines. The really interesting special cases are "incomplete" straight lines, of which the "XYWing" is an example when it involves exactly four different values.
I'm not denying that other sorts of chains exist within Sudoku puzzles. But those other kinds of chains are not the logical equivalents of straight lines. dcb 

Back to top 




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
