Two definitions of W-Wing, terminology question

Advanced methods and approaches for solving Sudoku puzzles

Two definitions of W-Wing, terminology question

Postby JasonLion » Sun Nov 09, 2008 3:44 pm

I have seen two definitions of W-Wing. The common definition appears in a couple of places, including Sudopedia, and involves a four cell chain. However, in:

http://www.dailysudoku.com/sudoku/forums/viewtopic.php?p=6357#6375

TexCat offered another definition:

Code: Select all
.    .    .  |  NotG NotG NotG | .   .  . 
GW   .    .  |   .    .      . | .   .  .
.    .    .  |    .   .      . | .   . GW

leading to:

Code: Select all
.     .    .  |  NotG NotG NotG | .    .    . 
GW    .    .  |   .    .      . |NotW NotW NotW 
NotW NotW NotW|   .    .      . | .    .    GW


My question is: Does TexCat's technique have a name? Is it a W-Wing? A subset/special case of W-Wing? Something else? It does not appear to be one to one equivalent to the accepted chain definition.
User avatar
JasonLion
2017 Supporter
 
Posts: 624
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Two definitions of W-Wing, terminology question

Postby re'born » Sun Nov 09, 2008 4:35 pm

JasonLion wrote:I have seen two definitions of W-Wing. The common definition appears in a couple of places, including Sudopedia, and involves a four cell chain. However, in:

http://www.dailysudoku.com/sudoku/forums/viewtopic.php?p=6357#6375

TexCat offered another definition:

Code: Select all
.    .    .  |  NotG NotG NotG | .   .  . 
GW   .    .  |   .    .      . | .   .  .
.    .    .  |    .   .      . | .   . GW

leading to:

Code: Select all
.     .    .  |  NotG NotG NotG | .    .    . 
GW    .    .  |   .    .      . |NotW NotW NotW 
NotW NotW NotW|   .    .      . | .    .    GW


My question is: Does TexCat's technique have a name? Is it a W-Wing? A subset/special case of W-Wing? Something else? It does not appear to be one to one equivalent to the accepted chain definition.

I would call it a W-wing (well, actually, I call it a semi-remote naked pair), but you might call it a grouped W-wing to be more specific.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Glyn » Sun Nov 09, 2008 4:45 pm

JasonLion Welcome to the forum
Keith's W-wing example from Sudopedia is
Code: Select all
+---------------------+-------------------+-------------------+
| 8      257    2579  | 1     4     37    | 235   6     2359  |
| 12     6      3     | 5     8     9     | 7     4     12    |
| 179    157    4     | 37    6     2     | 1358  189   1358  |
+---------------------+-------------------+-------------------+
| 6      157    579   | 4     3     78    | 158   2     1589  |
| 12479  12357  257   | 2789  2A7a  6     | 1458  17A89 1358  |
| 34     8      2a7A  | 279   5     1     | 34    7a9   6     |
+---------------------+-------------------+-------------------+
| 237    237    8     | 6     1     34    | 9     5     24    |
| 5      9      1     | 278   27    478   | 6     3     248   |
| 23     4      6     | 238   9     5     | 128   18    7     |
+---------------------+-------------------+-------------------+

As an AIC (2=7)r6c3-(7)r6c8=(7)r5c8-(7=2)r5c5 => r5c123,r6c4<>2

Restatement in the form of TexCat
Code: Select all
.     .     .     |            |  Not 7  Not 7  Not 7|
.     .     .     |  .  27  .  |  .      .      .    |
.     .     27    |  .  .   .  |  .      .      .    |
implies this
Code: Select all
.     .     .     |  .      .     .       |  Not 7  Not 7  Not 7|
Not 2 Not 2 Not 2 |  .      27    .       |  .      .      .    |
.     .     27    |  Not 2  Not 2  Not 2  |  .      .      .    |

I hope you can see that the pattern is the same. TexCat's is slightly more general in that it allows a grouped strong link between the 7's in box 6 as opposed to a simple cell to cell link. I see that re'born has mention the group possibility in his post. To me knowing how it works is more important than the name.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby JasonLion » Mon Nov 10, 2008 4:54 am

The two definitions overlap, but each catches cases the other doesn't. TexCat's definition catches cases where there is a grouped link, rather than a plain strong link, and the chain definition catches cases where the semi-remote naked pair is not in a single chute.

I think that TexCat's definition ought to be called W-Wing and the chain definition should get another name. Back in http://www.dailysudoku.com/sudoku/forums/viewtopic.php?p=6357#6375 TexCat offered the first clear definition, a clearly stated chain explanation came later, and that thread appears to be the first use of the name W-Wing.

Another reason that TexCat's definition deserves the simpler name is that his technique is something that can be learned easily by an intermediate player and spotted fairly easily. Anything involving chains is advanced players only in my book.
User avatar
JasonLion
2017 Supporter
 
Posts: 624
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Postby ronk » Mon Nov 10, 2008 6:49 am

Excluding permutations, I think there are five different patterns for w-wings, arbitrarily labeled Type A through Type E below. For a history of the w-wing see http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=2008.

Other than being labels for possible discussion, I'm not suggesting the Type numbers be used as part of a naming system. Indeed, I'm happy with just the two names: 1) w-wing, and 2) grouped w-wing.
Code: Select all
 .  .  . |  .  .  . |  .  /  .        .  .  a |  .  .  . |  .  .  .
 . ab  . |  . -b  . |  .  a  .        . ab  a |  . -b  . |  .  .  .
 .  .  . |  .  .  . |  .  /  .        .  .  a |  .  .  . |  .  .  .
---------+----------+----------      ---------+----------+----------
 .  .  . |  .  .  . |  .  /  .        .  .  / |  .  .  . |  .  .  .
 . -b  . |  . ab  . |  .  a  .        . -b  a |  . ab  . |  .  .  .
 .  .  . |  .  .  . |  .  /  .        .  .  / |  .  .  . |  .  .  .
---------+----------+----------      ---------+----------+----------
 .  .  . |  .  .  . |  .  /  .        .  .  / |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  /  .        .  .  / |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  /  .        .  .  / |  .  .  . |  .  .  .
 Type A:                              Type B:


 .  . -b |  .  .  . |  .  /  .
 . ab -b |  .  .  . |  .  a  .
 .  . -b |  .  .  . |  .  /  .
---------+----------+----------
 . -b  . |  .  .  . |  .  /  .
 . -b ab |  .  .  . |  .  a  .
 . -b  . |  .  .  . |  .  /  .
---------+----------+----------
 .  .  . |  .  .  . |  .  /  .
 .  .  . |  .  .  . |  .  /  .
 .  .  . |  .  .  . |  .  /  .
 Type C:


Based on empirical tests, Types D1 and D2 below are equivalent:

-b  .  a |  .  .  . |  .  .  .       -b  .  . |  .  .  . |  .  .  .
-b ab  a |  .  .  . |  .  .  .       -b ab  . |  .  .  . |  .  .  .
-b  .  a |  .  .  . |  .  .  .       -b  .  . |  .  .  . |  .  .  .
---------+----------+----------      ---------+----------+----------
 . -b  a |  .  .  . |  .  .  .        . -b  . |  .  .  . |  .  .  .
ab -b  a |  .  .  . |  .  .  .       ab -b  . |  .  .  . |  .  .  .
 . -b  a |  .  .  . |  .  .  .        . -b  . |  .  .  . |  .  .  .
---------+----------+----------      ---------+----------+----------
 .  .  / |  .  .  . |  .  .  .        a  a  / |  .  .  . |  .  .  .
 .  .  / |  .  .  . |  .  .  .        a  a  / |  .  .  . |  .  .  .
 .  .  / |  .  .  . |  .  .  .        a  a  / |  .  .  . |  .  .  .
 Type D1:                             Type D2:
                               

 .  .  . |  /  a  / |  .  .  .
 . ab  . |  a a-b a |  .  .  .
 .  .  . |  /  a  / |  .  .  .
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
 . -b  . |  . ab  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 Type E:

KEY: '/' <=> cells void of candidate 'a'
     'a' <=> cells with candidate 'a'; not all are required
    "-b" <=> potential eliminations of candidate 'b'


w-ring patterns -- continuous loops comprised of two bivalues and two bilocals -- are also possible. [edit3: The w-ring may be viewed as two w-wings that share bivalued cells, one with a (grouped or ungrouped) bilocal in 'a' and the other with a bilocal in 'b'. The correspondence between a w-ring and a w-wing is similar to that between an xy-ring and an xy-wing.

Below are two illustrations for what is likely the simplest w-ring pattern. The left illustration shows the four strong links without potential eliminations; the right includes the 28 possible eliminations.

Code: Select all
 .  .  . |  .  .  . |  .  /  .        . -b   . |  . -b   . |  .  /  .
 . ab  . |  .  .  . |  .  a  .       -a ab  -a | -a -ab -a | -a  a -a
 .  .  . |  .  .  . |  .  /  .        . -b   . |  . -b   . |  .  /  .
---------+----------+----------      ----------+-----------+----------
 .  .  . |  .  .  . |  .  /  .        . -b   . |  . -b   . |  .  /  .
 .  .  . |  . ab  . |  .  a  .       -a -ab -a | -a ab  -a | -a  a -a
 .  .  . |  .  .  . |  .  /  .        . -b   . |  . -b   . |  .  /  .
---------+----------+----------      ----------+-----------+----------
 .  .  . |  .  .  . |  .  /  .        . -b   . |  . -b   . |  .  /  .
 /  b  / |  /  b  / |  /  /  /        /  b   / |  /  b   / |  /  /  /
 .  .  . |  .  .  . |  .  /  .        . -b   . |  . -b   . |  .  /  .

 r2c2 -a- r2c8 =a= r5c8 -a- r5c5 -b- r8c5 =b= r8c2 -b- r2c2 - continuous loop

 ==> r2c1345679<>a, r5c1234679c5<>a, r1234679c5<>b, r1345679c2<>b (28 potential eliminations)

[edit: 1) added w-ring topic; 2) added link to xy-ring definition; 3) added equivalent type D2, as suggested by StrmCkr]
Last edited by ronk on Fri Mar 13, 2009 11:07 pm, edited 3 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Mon Nov 10, 2008 7:34 am

ronk: nice graphical examples. I wish you had gone on to show that they are all simple chains that rely on: 1) two identical bivalue cells that aren't peers, and 2) each bivalue cell sees all of the endpoint cells on one end of a (possibly grouped) strong link on one of the bivalue candidates. (Whew, what a mouthful!)

Code: Select all
Type A:  b-[r2c2]-a-[r2c8]  =a=[r5c8]  -a-[r5c5]-b  =>  eliminations in b
Type C:  b-[r2c2]-a-[r2c8]  =a=[r5c8]  -a-[r5c3]-b  =>  eliminations in b
Type B:  b-[r2c2]-a-[r123c3]=a=[r5c3]  -a-[r5c5]-b  =>  eliminations in b
Type D:  b-[r2c2]-a-[r123c3]=a=[r456c3]-a-[r5c1]-b  =>  eliminations in b
Type E:  b-[r2c2]-a-[r2c456]=a=[r13c5] -a-[r5c5]-b  =>  eliminations in b

Note: At least one definition of W-Wing require a strong link for the first weak inference. The generalized case doesn't.

===== ===== ===== ===== =====

Please, don't anyone bring up a similar discussion on M-Wing because it's just as bad.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Mon Nov 10, 2008 7:45 am

daj95376 wrote:Note: At least one definition of W-Wing require a strong link for the first weak inference. The generalized case doesn't.

I'm not aware of such a definition. Have you got a link:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Pat » Mon Nov 10, 2008 8:15 am

ronk wrote:
daj95376 wrote:Note: At least one definition of W-Wing require a strong link for the first weak inference. The generalized case doesn't.

I'm not aware of such a definition. Have you got a link:?:

sudopedia defines W-Wing as exactly 4 cells
    and requires a strong link
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby JasonLion » Mon Nov 10, 2008 8:29 am

daj95376, I much prefer your definition to the ones I have seen elsewhere. It neatly brings everything together and eliminates my confusion.

The Sudopedia definition covers Ronk's types A, C, and some instances of B and D. TexCat's definition covers Ronk's type D.

Now I wonder if the "grouped w-wing" name has much value. The new definition, along with Ronk's types, explains things more clearly. There isn't any one to one mapping of Ronk's types into grouped strong links and simple strong links. Specifically Types B and D can sometimes have simple strong links and sometimes grouped links, depending on how many of the 'a' cells actually contain a.
User avatar
JasonLion
2017 Supporter
 
Posts: 624
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Postby daj95376 » Mon Nov 10, 2008 8:31 am

ronk wrote:
daj95376 wrote:Note: At least one definition of W-Wing require a strong link for the first weak inference. The generalized case doesn't.

I'm not aware of such a definition. Have you got a link:?:

Mea Culpa:(:(:(

I mixed up an M-Wing constraint with the W-Wing constraints. My apologies:!::!::!:
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby re'born » Mon Nov 10, 2008 9:53 am

JasonLion wrote:Now I wonder if the "grouped w-wing" name has much value.

I just started learning Spanish last month and as probably everyone one but me has known for a while, 'I want' is 'quiero', but if you want to emphasize I, you can say 'yo quiero'. Similarly, I would suggest that w-wing is appropriate in most cases. If, however, you are teaching a beginner the technique and you give an example with a grouped w-wing, it will be useful to emphasize that point.

Incidentally, why restrict the pattern to 4 cells? It costs almost nothing to allow it to extend to any even number of cells.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby JasonLion » Mon Nov 10, 2008 10:11 am

There was a previous discussion of longer chains of this form in http://forum.enjoysudoku.com/viewtopic.php?t=6126. There was some momentum to call them W-Chains, though it was also suggested that longer chains simply be called by their normal chain names (XY-Chain, AIC, Nice Loop as appropriate). The situation is closely related to the XY-Wing, which is just a short XY-Chain.
User avatar
JasonLion
2017 Supporter
 
Posts: 624
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Two Definitions of the of W-wing, terminology question

Postby Bud » Fri Nov 21, 2008 8:31 am

I would like to add a few comments about TexCat's definition. First of all I think there is a tacit constraint in the pattern. that at least one G candidate is in both r2b2 and r3b2. Otherwise a G cell elimination will occur in either r2c1 or r3c9 and the pattern will no longer exist. With this constraint, the pattern is a good one for the 3 box W-wing since it covers all three posibilities. These are a G conjugate pair in a single column of box2, a G diagonal conjugate pair in box 2, and G grouped conjugates in box3. All three possibilities give the same cell eliminations and should be called W-wings.

Code: Select all
 
.     .    .  |  NotG NotG NotG | .    .    . 
GW    .    .  |   .    .      . |NotW NotW NotW 
NotW NotW NotW|   .    .      . | .    .    GW


I also want to thank Daj for bringing up the M-Wing. Since I hadn't heard of this before I googled it. I have some questions on this but I will wait until someone brings this up in another post.
Bud
 
Posts: 56
Joined: 24 August 2008

Re: Two Definitions of the of W-wing, terminology question

Postby daj95376 » Fri Nov 21, 2008 11:01 am

Bud wrote:I would like to add a few comments about TexCat's definition. First of all I think there is a tacit constraint in the pattern. that at least one G candidate is in both r2b2 and r3b2. Otherwise a G cell elimination will occur in either r2c1 or r3c9 and the pattern will no longer exist. With this constraint, the pattern is a good one for the 3 box W-wing since it covers all three posibilities. These are a G conjugate pair in a single column of box2, a G diagonal conjugate pair in box 2, and G grouped conjugates in box3. All three possibilities give the same cell eliminations and should be called W-wings.

Code: Select all
 
.     .    .  |  NotG NotG NotG | .    .    . 
GW    .    .  |   .    .      . |NotW NotW NotW 
NotW NotW NotW|   .    .      . | .    .    GW


I also want to thank Daj for bringing up the M-Wing. Since I hadn't heard of this before I googled it. I have some questions on this but I will wait until someone brings this up in another post.

I believe that it's not necessary to dot every i and cross every t when presenting an argument. If one assumes that basic techniques have already been performed before needing an advanced technique, then your constraint is really just an extension of this assumption. Otherwise, everything has to be qualified all the way back to a Naked Single in [b2] at [r2c5]=G. This is ridiculous!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby StrmCkr » Sun Mar 15, 2009 1:03 am

Grouped Type E:

you can link two type E's similar to that of
grouped empty rectangles.

and produce extended eliminations.

as in this example.

Code: Select all
 .  .  . |  /  a  / |  .  .  .
 . ab  . |  a  a  a |  .  -b .
 .  .  . |  /  a  / |  .  .  .
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
---------+----------+----------
 .  .  . |  /  a  / |  .  .  .
 .  -b . |  a  a  a |  .  ab .
 .  .  . |  /  a  / |  .  .  .


and the eliminations can extend further if they share the same common R5C5 as the bivavle.

(basically view each half as the normal type E, and combined with the above)

Code: Select all
 .  .  . |  /  a  / |  .  .  .
 . ab  . |  a a-b a |  . -b  .
 .  .  . |  /  a  / |  .  .  .
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
 . -b  . |  . ab  . |  . -b  .
 .  .  . |  .  .  . |  .  .  .
---------+----------+----------
 .  .  . |  /  a  / |  .  .  .
 . -b  . |  a a-b a |  .  ab .
 .  .  . |  /  a  / |  .  .  .
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 664
Joined: 05 September 2006

Next

Return to Advanced solving techniques