 |
Sudoku Players' Forums
|
| View previous topic :: View next topic |
| Author |
Message |
Steve K
Joined: 18 Jan 2007
Posts: 133
Location: Cincinnati Ohio
|
 Posted: Sun Mar 18, 2007 2:15 am Post subject: Y Wing Styles |
 |
|
Nothing earth shattering, of course.
As I solve puzzles, I frequently use AIC that consider exactly 3 strong inference sets. By that I mean, 3 sets upon which I use the strong inference. All of these can be represented with one common idea. Almost all of them are completely analagous to the standard Y wing, thus the name, Y Wing Styles.
Some of them are easier to find than the standard Y wings. As a group, many of them occur much more frequently than standard 3 bivalue cell Y wings. None of them are something new, by and of themselves.
Nevertheless, considering all of them as part of a simple whole:
A strong inference set as the vertex, with two strong inference sets as the endpoints - thus forming a Y, is a very simple but powerful tool.
Added Detail:
Here is a broad and very general explanation of the idea, Y Wing Styles:
| Code: |
Consider exacly three native sets upon which one can perform a Strong Inference.
View one or more of these three sets as a vertex.
Using only the base set of puzzle constraints, prove one or more non-native sets which satisfies the strong inference requirement.
Make eliminations based upon these newly proven (non-native) strong inference sets. |
Native : naturally occurring in the current puzzle possibility matrix.
Many puzzles that I have found with suggested solutions completely ignore the existence of most of these Y Wing Styles.
One of the types of Y wing Styles, that I call in my blog as being very common, is not only more common than the standard Y wing, but also much easier to find.
I have a number of pages in my sudoku blog that deal extensively with this concept. Also, I have a number of puzzle proofs that use this concept as the primary solving tool for that particular puzzle (but rarely the only solving tool).
The nomenclature that I use to describe many of the ideas commonly used in this forum is a bit non-standard. Nevertheless, the nomenclature is well described within my blog and hopefully easy to decipher.
If this concept is of any interest to those who frequent this forum, I can add more details here later.
To investigate Y Wing Styles, the two following web pages of my blog are probably fair (slightly better than poor) places to start:
http://sudoku.com.au/YWingStyle.aspx
http://sudoku.com.au/YWingStyle2.aspx |
|
| Back to top |
|
 |
Steve K
Joined: 18 Jan 2007
Posts: 133
Location: Cincinnati Ohio
|
| Posted: Mon Mar 26, 2007 2:15 am Post subject: |
|
|
The following is an example of what I call a Very Common Y Wing Style.
As such, it occurs more frequently, in my experience, than a standard Y wing, or xy wing. Furthermore, I find it easier to spot than a standard Y wing. Certainly, as all techniques are, it is a subset of other techniques.
Nevertheless, since it is almost ridiculously easy to find, and occurs often, it bears special attention.
| Code: |
Puzzle start
*-----------*
|...|..5|..2|
|...|..8|3..|
|165|...|...|
|---+---+---|
|6.1|..3|...|
|.8.|.4.|.2.|
|...|6..|7.4|
|---+---+---|
|...|...|917|
|..6|3..|...|
|2..|8..|...|
*-----------*
*-----------*
|...|..5|..2|
|...|..8|35.|
|165|.32|.7.|
|---+---+---|
|641|723|...|
|.8.|549|.2.|
|...|681|734|
|---+---+---|
|.3.|256|917|
|..6|3..|2..|
|2..|8..|..3|
*-----------*
Possibility matrix after SS solving set is done.
*-----------------------------------------------------------*
| 38 79 38 | 149 67 5 | 146 469 2 |
| 479 279 2479 | 19 67 8 | 3 5 16 |
| 1 6 5 | 49 3 2 | 48 7 89 |
|-------------------+-------------------+-------------------|
| 6 4 1 | 7 2 3 | 58* 8&9 -589 |
| 37 8 37 | 5 4 9 | 16 2 16 |
| 59 259 29 | 6 8 1 | 7 3 4 |
|-------------------+-------------------+-------------------|
| 48 3 48 | 2 5 6 | 9 1 7 |
| 579 1579 6 | 3 19 47 | 2 48& 58* |
| 2 1579 79 | 8 19 47 | 4-56 46 3 |
*-----------------------------------------------------------*
|
The two cells marked with an asterisk are common markers to find such a pattern. The two cells do not share a common house, but are both limited to the same two candidates. All that is required is a strong inference in either 5's or 8s to connect them. Marked with &, there exists such a link using candidate 8. Thus the 5's marked with - are eliminated.
One can justify this elimination succintly, as with all Y Wing Styles, with a mere strong inference set list:
r4c7(58), r48c8(8), r8c9(58) => r9c7,r4c9<>5 |
|
| Back to top |
|
|
daj95376
Joined: 15 May 2006
Posts: 1521
|
| Posted: Mon Mar 26, 2007 8:18 am Post subject: |
|
|
Withdrawn.
Last edited by daj95376 on Sat Jul 07, 2007 7:02 am; edited 1 time in total |
|
| Back to top |
|
|
re'born
Joined: 31 May 2007
Posts: 552
Location: Wilmington, MA
|
| Posted: Wed Mar 28, 2007 6:56 am Post subject: |
|
|
Here is another example of this nice elimination technique.
.23.9..641...6.....6....19......2...7..148..2...3......87....1.....1...824..3.97.
Basic techniques take you to
| Code: |
*-----------------------------------------------------------*
| 8 2 3 | 7 9 1 | 5 6 4 |
| 1 7 9 | 45 6 45 | 28 28 3 |
| 5 6 4 | 2 8 3 | 1 9 7 |
|-------------------+-------------------+-------------------|
| 346 135 8 | 69 57 2 | 467 45 19 |
| 7 9 56 | 1 4 8 | 36 35 2 |
| 46 15 2 | 3 57 69 | 4678 458 19 |
|-------------------+-------------------+-------------------|
| 369 8 7 | 4569 2 4569- | 34 1 56* |
| 369 35 56 | 469 1 7 | 234 234 8 |
| 2 4 1 | 8 3 56* | 9 7 56* |
*-----------------------------------------------------------*
|
where a type 1 UR eliminates [56] from r7c6. Next,
| Code: |
*-----------------------------------------------------------*
| 8 2 3 | 7 9 1 | 5 6 4 |
| 1 7 9 | 45* 6 45* | 28 28 3 |
| 5 6 4 | 2 8 3 | 1 9 7 |
|-------------------+-------------------+-------------------|
| 346 135 8 | 69 57 2 | 467 45 19 |
| 7 9 56 | 1 4 8 | 36 35 2 |
| 46 15 2 | 3 57 69 | 4678 458 19 |
|-------------------+-------------------+-------------------|
| 369 8 7 | 4569* 2 49- | 34 1 56 |
| 369 35 56 | 469 1 7 | 234 234 8 |
| 2 4 1 | 8 3 56 | 9 7 56 |
*-----------------------------------------------------------*
|
the strong link on 5 in column 4 implies that to avoid a deadly pattern, we must have r7c6=9. Singles then take us to
| Code: |
*--------------------------------------------------*
| 8 2 3 | 7 9 1 | 5 6 4 |
| 1 7 9 | 5 6 4 | 28 28 3 |
| 5 6 4 | 2 8 3 | 1 9 7 |
|----------------+----------------+----------------|
| 36* 35 8 | 9 57 2 | 467- 45 1 |
| 7 9 56- | 1 4 8 | 36* 35 2 |
| 4 1 2 | 3 57 6 | 78 58 9 |
|----------------+----------------+----------------|
|(3)6 8 7 | 46 2 9 |(3)4 1 5 |
| 9 35 56 | 46 1 7 | 234 234 8 |
| 2 4 1 | 8 3 5 | 9 7 6 |
*--------------------------------------------------*
|
where
6-[r4c1]-3-[r7c1]=3=[r7c7]-3-[r5c7]-6
implies that r4c7,r5c3<>6, solving the puzzle.
I believe this is the same pattern Steve K mentioned above: Two bivalued cells with the same values, weakly linked to opposite ends of a strong link on one of the above values.
Alternatively, one can see the same pattern in a different location:
| Code: |
*--------------------------------------------------*
| 8 2 3 | 7 9 1 | 5 6 4 |
| 1 7 9 | 5 6 4 | 28 28 3 |
| 5 6 4 | 2 8 3 | 1 9 7 |
|----------------+----------------+----------------|
| 36 35 8 | 9 57 2 | 467 45 1 |
| 7 9 (5)6 | 1 4 8 | 36 35* 2 |
| 4 1 2 | 3 57 6 | 78 58 9 |
|----------------+----------------+----------------|
| 36 8 7 | 46 2 9 | 34 1 5 |
| 9 35* (5)6 | 46 1 7 | 234 234- 8 |
| 2 4 1 | 8 3 5 | 9 7 6 |
*--------------------------------------------------*
|
3-[r5c8]-5-[r5c3]=5=[r8c3]-5-[r8c2]-3
implies that r8c8<>3, solving the puzzle. Of course, if you're paying close attention you will notice that this is also an xy-chain.
Last edited by re'born on Thu Mar 29, 2007 4:48 am; edited 1 time in total |
|
| Back to top |
|
|
Steve K
Joined: 18 Jan 2007
Posts: 133
Location: Cincinnati Ohio
|
| Posted: Thu Mar 29, 2007 4:21 am Post subject: |
|
|
| Nicely done! Thanks! |
|
| Back to top |
|
|
Mike Barker
Joined: 22 Jan 2006
Posts: 458
Location: Tucson, AZ
|
| Posted: Fri Mar 30, 2007 9:50 am Post subject: |
|
|
My understanding is that Y-wing styles are equivalent to nice loops with 3 links. This being the case then we should be able to define the different options using nice loop techniques. I break nice loops into three types: continuous (the start and end nodes see each other with a valid link between them), different-house discontinuous (the start and end nodes do not see each other), same-house discontinuous (the start and end nodes see each other, but no valid link exists between them). Below lists Y-wing style possibilities based on bivalue cells (for example, "ab") and bilocation cells (strong links, for example "aX=a=aY" where "X" and "Y" are the remaining candidates in the cell). Although not standard, I indicate a discontinuous link with a "~" (for example bc~c~aW=a=aX is a discontinuity between "bc" and "aW").
In these cases 1-6 are continuous or different-house discontinuous and 7-9 are same-house discontinuous. Assuming I'm on the right track similar templates can be generated with ALS and grouped strong links.
| Code: | 1) -a-ab-b-bc-c-ca-a- continuous => a naked triple, otherwise an XY-wing = Y-wing
2) -a-ab-b-bX=b=bY-b-ab-a-
3) -a-aW=a=aX=b=bY-b-ab-a-
4) -a-aW=a=aX-a-aP=a=aQ-a-aY=a=aZ-a- continuous => an 222 Swordfish, otherwise a turbot chain
5) -a-aW=a=abX=b=abY=a=aZ-a- continuous => eliminate X and Y otherwise equivalent to #4
6) -a-aW=a=aX-a-ab-b-ab-a- equivalent to #4
7) aW=a=aX-a-ab-b-bc~c~aW eliminate "c" in "aW" only
8) aW=a=abX=b=bY-b-bc~c~aW eliminate "c" in "aW" only
9) cZ~a~aW=a=abX=b=bcY=c=cZ~c~aW eliminate "c" in "aW" or "a" in "cZ" only |
Note: In my experience there are about as many cases of nice loops with 4 links as there are with 3.
Last edited by Mike Barker on Sat Jul 07, 2007 4:37 pm; edited 1 time in total |
|
| Back to top |
|
|
Steve K
Joined: 18 Jan 2007
Posts: 133
Location: Cincinnati Ohio
|
| Posted: Tue Apr 03, 2007 4:08 am Post subject: |
|
|
Hi Mike!
Certainly, you are correct that one can classify the technique according to continuous and discontinuous nice loops. I am not convinced of the value in limiting the analysis, however, to only bivalue and bilocation strong inferences.
In my very poor attempt to explain the idea of Y Wing Styles, I am using the following commonly accepted ideas:
| Code: | Strong inference: At least one of a set must be true.
Weak inference: At most one of a set must be true |
.
However, in order to limit the discussion, I add the further qualifier, native.
Y Wing Styles is an attempt to look at exactly 3 strong native strong inferences. By this, I mean, given the original puzzle constraints, sans everything - a blank grid - one could say that there are 81(4) strong inferences, and 81(4) weak inferences. The weak inferences, for the purpose of AIC, never change. Thus, in every puzzle, every time,
(1)r1c1-(1)r9c1, with no regard as to whether or not either cell can contain 1. On the other hand, every particular puzzle is defined by limiting the native strong inferences. In other words, when given a puzzle, we are given some solved cells.
Each solved cell limits 4 native strong inferences to exactly one value.
Y wing styles is meant to focus on exactly 3 of the original strong inferences( modified by the particular puzzle, and any eliminations made). The arbitrary narrowing of the technique to 3 native strong inferences is admittedly very narrow. On the other hand, placing no limits on the type of native strong inferences, or their size, is fairly broad.
Typically, we ignore those strong inferences that have only one possible value. I prefer, though, to not limit investigations of the remaining strong inferences to those that contain exactly two possible states. There is, in my opinion, much less special about those particular strong inferences than generally thought.
The basis for my point of view is perpaps off topic. The long and short of it is, though, that even an easy technique such as locked candidates does not limit itself to bilocation, so therefor limiting any investigation to only bi-anything must miss the short path to a lot of available eliminations. Of course, examples of the shortcomings of only considering bi-anything are plentiful (swordfish, triples, xyz wing, ALS, etc.)
One can certainly use the templates that you have provided as objects in which one can insert other techniques.
One can also insert the templates you have provided into any AIC.
That is, of course, nothing new, as all possible nice loops, or AIC, can be inserted into AIC, as Almost Locked AIC, (I suppose that is a possible name..... - I just call them Booleans)
Finally, I agree that in terms of useful frequency of occurence, my experience is also that nice loops using 4 strong inferences exist at least as often as those using exactly 3 strong inferences. In terms of theoretical frequency, the number of possible interactions (thus perhaps definable techniques) increases quite fast as the number of strong inferences used increases. One could be trite and say it is an exponential increase, but the true representation of that number is perhaps a bit different. Also, it begs the question of defining techniques! Viewed with enough generality, I suppose we only need one technique, regardless of complexity.
The general idea of Y Wing Styles is to open the mind towards potential building blocks for eliminations. By themselves, they are useful. But, as with all techniques, there is significant utility when viewed as a building block. Such building blocks can be both containers (insert techniques into them), and contained (insert them into another technique).
It seems the emphasis in finding techniques has been to use a base concept, like a naked pair, for example, and derive by induction n-tuples, and then use n-tuples as an insertable object in chains, such as AIC. However, every imaginable elimination technique has the same potential, both for inductive expansion, and as an object for use within some sort of logical construct. This fact is of course well known, but perhaps under-used.
I suppose I have now gone quite far off topic, and should stop. |
|
| Back to top |
|
|
re'born
Joined: 31 May 2007
Posts: 552
Location: Wilmington, MA
|
| Posted: Thu Apr 12, 2007 6:16 am Post subject: |
|
|
Below is another example of the pattern. There is a corresponding xy-chain to make the same exclusion (as pointed out to me by SudoCue), but it's length makes it clear (at least to me) which is the easier pattern to spot:
| Code: |
.---------------.---------------.---------------.
| 26 4 12 | 37 16* 378 | 5 38 9 |
| 35 589 7 | 359 (1)5 4 | 6 2 (1)8 |
| 356 5689 19 | 3569 2 1358| 13 7 4 |
:---------------+---------------+---------------:
| 259 59 29 | 4 8 6 | 7 1 3 |
| 4 1 6 | 27 3 27 | 8 9 5 |
| 8 7 3 | 1 59 59 | 4 6 2 |
:---------------+---------------+---------------:
| 69 2 4 | 356 7 135 | 139 358 168 |
| 7 3 5 | 8 169- 19 | 2 4 16* |
| 1 69 8 | 2356 4 23 | 39 35 7 |
'---------------'---------------'---------------'
|
An xy-chain making the same elimination is:
[r8c9]-1-[r2c9]-8-[r1c8]-3-[r3c7]-1-[r3c3]-9-[r4c3]-2-[r1c3]-1-[r1c5]
Is there a shorter xy-chain?
Edit: Here is the original puzzle-
| Code: |
. . .|. . .|5 . 9
. . 7|. . 4|6 2 .
. . .|. 2 .|. 7 .
-----+-----+-----
. . .|. . 6|. 1 3
4 . 6|. . .|8 . 5
8 7 .|1 . .|. . .
-----+-----+-----
. 2 .|. 7 .|. . .
. 3 5|8 . .|2 . .
1 . 8|. . .|. . .
|
|
|
| Back to top |
|
|
gsf
Joined: 21 Sep 2005
Posts: 4032
Location: NJ USA
|
| Posted: Thu Apr 12, 2007 8:04 am Post subject: |
|
|
| rep'nA wrote: |
An xy-chain making the same elimination is:
[r8c9]-1-[r2c9]-8-[r1c8]-3-[r3c7]-1-[r3c3]-9-[r4c3]-2-[r1c3]-1-[r1c5]
Is there a shorter xy-chain?
|
here is a 6 cell chain that contradicts [r8c9]=1
| Code: | | [r8c9]-1-[r8c6]-9-[r6c6]-5-[r6c5]-9-[r2c5]-5-[r2c9]-1-[r8c9]-1- |
these are labeled y-knot in my solver |
|
| Back to top |
|
|
tarek
Joined: 05 Jan 2006
Posts: 2257
Location: The Midlands, UK
|
| Posted: Thu Apr 12, 2007 8:26 am Post subject: |
|
|
| gsf wrote: | here is a 6 cell chain that contradicts [r8c9]=1
| Code: | | [r8c9]-1-[r8c6]-9-[r6c6]-5-[r6c5]-9-[r2c5]-5-[r2c9]-1-[r8c9]-1- |
these are labeled y-knot in my solver |
How about a ring
tarek |
|
| Back to top |
|
|
re'born
Joined: 31 May 2007
Posts: 552
Location: Wilmington, MA
|
| Posted: Thu Apr 12, 2007 9:01 am Post subject: |
|
|
| gsf wrote: | | rep'nA wrote: |
An xy-chain making the same elimination is:
[r8c9]-1-[r2c9]-8-[r1c8]-3-[r3c7]-1-[r3c3]-9-[r4c3]-2-[r1c3]-1-[r1c5]
Is there a shorter xy-chain?
|
here is a 6 cell chain that contradicts [r8c9]=1
| Code: | | [r8c9]-1-[r8c6]-9-[r6c6]-5-[r6c5]-9-[r2c5]-5-[r2c9]-1-[r8c9]-1- |
these are labeled y-knot in my solver |
For the notation guru's: Is gsf's notation correct? I would have expected it to be written
[r8c9]-1-[r8c6]-9-[r6c6]-5-[r6c5]=5=[r2c5]=1=[r2c9]-1-[r8c9]. |
|
| Back to top |
|
|
gsf
Joined: 21 Sep 2005
Posts: 4032
Location: NJ USA
|
| Posted: Thu Apr 12, 2007 9:04 am Post subject: |
|
|
| tarek wrote: | | gsf wrote: | here is a 6 cell chain that contradicts [r8c9]=1
| Code: | | [89]1[86]9[66]5[65]9[25]5[29]1[89]1 |
these are labeled y-knot in my solver |
How about a ring
|
the X and Y constraint code is based on graph cycle detection
(it awoke some brain cells from grad school graph theory)
that code defines a sudoku cycle to be a consistent path that closes on itself
in this scheme a path that exposes a contradiction is not a cycle
so I did some wordplay with { y knot not }
I don't use ring because is has a group theoretic meaning and there is a lot of group theory crossover with sudoku
I don't use chain or loop because I chose to use the terms
edge => segment => path => { cycle or knot }
an edge connects two cells
a segment is multiple connected edges that can collapse to an equivalent edge
a path is multiple connected segments
a cycle is a consistent path that closes on itself
a knot is an inconsistent path that closes on itself
there's a ternary algebra on sudoku edges that the X and Y constraints use
I've been putting off describing it for 1.5 years now
the edge algebra basically defines "a sees b" in a few mathematic terms
that cover all of the { turbot* sky* kite* other-names-I-never-remember }
Last edited by gsf on Thu Apr 12, 2007 9:10 am; edited 1 time in total |
|
| Back to top |
|
|
gsf
Joined: 21 Sep 2005
Posts: 4032
Location: NJ USA
|
| Posted: Thu Apr 12, 2007 9:09 am Post subject: |
|
|
| rep'nA wrote: | | gsf wrote: |
here is a 6 cell chain that contradicts [r8c9]=1
| Code: | | [r8c9]-1-[r8c6]-9-[r6c6]-5-[r6c5]-9-[r2c5]-5-[r2c9]-1-[r8c9]-1- |
these are labeled y-knot in my solver |
For the notation guru's: Is gsf's notation correct? I would have expected it to be written
[r8c9]-1-[r8c6]-9-[r6c6]-5-[r6c5]=5=[r2c5]=1=[r2c9]-1-[r8c9]. |
probably not since I don't do nice loop notation
I should have stuck with my default output form which doesn't label knot edges
| Code: | | [89]1[86]9[66]5[65]9[25]5[29]1[89]1 |
|
|
| Back to top |
|
|
re'born
Joined: 31 May 2007
Posts: 552
Location: Wilmington, MA
|
| Posted: Thu Apr 12, 2007 9:12 am Post subject: |
|
|
| gsf wrote: |
I don't use ring because is has a group theoretic meaning and there is a lot of group theory crossover with sudoku
|
I never saw any rings in group theory proper, but the term ring certainly has a ring theoretic meaning. 
| gsf wrote: |
there's a ternary algebra on sudoku edges that the X and Y constraints use
I've been putting off describing it for 1.5 years now
the edge algebra basically defines "a sees b" in a few mathematic terms
that cover all of the { turbot* sky* kite* other-names-I-never-remember } |
I would be very interested in seeing such a description. |
|
| Back to top |
|
|
gsf
Joined: 21 Sep 2005
Posts: 4032
Location: NJ USA
|
| Posted: Thu Apr 12, 2007 9:24 am Post subject: |
|
|
| rep'nA wrote: | | gsf wrote: |
I don't use ring because is has a group theoretic meaning and there is a lot of group theory crossover with sudoku
|
I never saw any rings in group theory proper, but the term ring certainly has a ring theoretic meaning.
|
sorry, to be precise I should have said abstract algebra
wiki "ring"
I'll try to make some time to write up the ternary algebra |
|
| 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
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
