Y Wing Styles

Advanced methods and approaches for solving Sudoku puzzles

Postby daj95376 » Thu Apr 12, 2007 5:25 pm

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?

Probably not, but there is a shorter chain that contradicts your xy-chain.

[r8c9]-1-[r8c6]-9-[r8c5]-6

So, this begs the question: What's right?
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby udosuk » Thu Apr 12, 2007 5:56 pm

daj95376 wrote:So, this begs the question: What's right?

rep'nA's chain proves that if r8c9=1, then r1c5=6.
And if r8c9<>1, then r8c9=6.
Either way, r8c5<>6. So we can eliminate 6 from r8c5.

Your short chain proves that if r8c9=1, then r8c5=6.
Combine with rep'nA's xychain (r8c9=1 => r1c5=6), the conclusion is r8c9=1 => two 6s on c5 => contradiction.

Therefore r8c9<>1.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby re'born » Thu Apr 12, 2007 7:25 pm

gsf wrote:sorry, to be precise I should have said abstract algebra
wiki "ring"


Don't sweat it. I was just giving you a hard time. I am delighted to be a part of a forum where many of the folk are familiar with abstract algebra. You don't get too much of that on the Guns N' Roses forum I occasionally frequent.:)

gsf wrote:I'll try to make some time to write up the ternary algebra


I look forward to reading it.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby udosuk » Fri Apr 13, 2007 8:52 am

gsf wrote: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

Besides wikipedia, Wolfram MathWorld is a fabulous reference source for anything mathematical...:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Fri Apr 13, 2007 9:52 am

rep'nA wrote:
gsf wrote:I'll try to make some time to write up the ternary algebra

I look forward to reading it.

I posted a first draft here.
Feel free to snarf parts to the forum if there is interest (too lazy to get the bb tags right, the src is nroff -mm!)
Also feel free to make a new topic to keep this one from straying.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ravel » Fri Jul 06, 2007 8:27 am

The type of Y Wing style in Steve K's example got the name "W-Wing" in the dailysudoku forum, where it was found independently, see here.
I think to remember, that rep'nA used W-Wings calling them Y Wings (probably because there was no own name for this type of "Y Wing style" ?).
IMO it earns an own name, because it is rather common (maybe Mike, Danny or others can check this) and rather easy to spot (often easier than an xy-wing).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby re'born » Fri Jul 06, 2007 11:54 am

ravel wrote:The type of Y Wing style in Steve K's example got the name "W-Wing" in the dailysudoku forum, where it was found independently, see here.
I think to remember, that rep'nA used W-Wings calling them Y Wings (probably because there was no own name for this type of "Y Wing style" ?).
IMO it earns an own name, because it is rather common (maybe Mike, Danny or others can check this) and rather easy to spot (often easier than an xy-wing).


I've lately been calling this type of deduction a semi-remote naked pair. I prefer this terminology as both techniques (this and the traditional remote naked pairs) start and end with bivalue cells containing the same candidates, and the "semi" is a reference to the semidirect product in group theory, where there is a "preferred" subgroup, namely the normal subgroup. In our case the preferred candidate is the one which links the endpoints while the other candidate is eliminated from the intersection of the endpoints.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ravel » Fri Jul 06, 2007 12:17 pm

So this name was chosen very thoroughly - but it is definitively too long:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby re'born » Fri Jul 06, 2007 6:46 pm

ravel wrote:So this name was chosen very thoroughly - but it is definitively too long:)

Why? Does it bother you that the name is longer than the explanation of the technique or the accompanying nice loop?:)

Part of my inspiration was from a comment made by richardm here
richardm wrote: Ok, I understand your y-wing - a weak form of remote pairs.

For beginners, I would think the terminology would be better since it is more descriptive. W-wing or Y-wing or Y-wing style tell me nothing.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Steve K » Fri Jul 06, 2007 10:11 pm

semi-remote naked pair

A very good name. It is a bit more general, as it can include more than 3 strong inferences in the deduction. The idea of Y wing styles, which perhaps is a terrible name, is that all bivalue/bilocation chains using precisely 3 strong inferences are basically the same animal. There are merely hidden differently by the possibility matrix. Nevertheless, in each case they are not difficult to find.

Admittedly, I am terrible at nomeclature. The nature of the thread was not to present a new idea, as it is not that at all. Rather, it was to open eyes on the ease of finding all such depth 3 chains.

Later,once one has mastered finding easy depth 3 chains, they are very easy to use as "Almost Chains", much like an Almost Locked Set. To that end, studying short chains can be very helpful. Many truly complex derivations are easily broken down into managable pieces using short almost chains as building blocks for larger chains.

An example of how this works can be found in my blog on this page:
http://sudoku.com.au/AlmostAIC111006Page1.aspx

Unfortunately, that page is not converted to Eureka format. Let it suffice to say that I use == to mean strong inference instead of =
I use -- to mean weak inference instead of -
I use = to mean equals.
The grid that I use is illustrated, so that should not be a problem.

BTW, I think that rep'na had some posts, now gone, that were in this thread.
Steve K
 
Posts: 98
Joined: 18 January 2007

Postby re'born » Fri Jul 06, 2007 10:41 pm

Steve K wrote:semi-remote naked pair
A very good name. It is a bit more general, as it can include more than 3 strong inferences in the deduction.

Thanks!:)
Steve K wrote:The nature of the thread was not to present a new idea, as it is not that at all. Rather, it was to open eyes on the ease of finding all such depth 3 chains.

Nonetheless, you revealed a pattern that I had never looked for and now I look for all of the time. New idea or old idea? I say, good idea.
Steve K wrote:An example of how this works can be found in my blog on this page:
http://sudoku.com.au/AlmostAIC111006Page1.aspx
Unfortunately, that page is not converted to Eureka format. Let it suffice to say that I use == to mean strong inference instead of =
I use -- to mean weak inference instead of -
I use = to mean equals.
The grid that I use is illustrated, so that should not be a problem.

For any one who hasn't checked out Steve's blog, I highly recommend it. He does some serious analysis of puzzles that I haven't found matched anywhere.
Steve K wrote:BTW, I think that rep'na had some posts, now gone, that were in this thread.

Unfortunately, they were lost when my account was unceremoniously (and apparently unintentionally and unknowingly purged). I was able to retrieve some, but not all of my previous posts. The ones from this thread are those that are now extinct.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ravel » Sat Jul 07, 2007 2:04 pm

I think, that we have to distinguish here between "sudoku solving science" techniques like Steve K has developed, and advanced techniques like xy-wing, xyz-wing or UR's with strong links, which can easily be applied by advanced manual solvers.
From following some threads on the dailysudoku forum, where a couple of those advanced solvers are posting, IMO "semi-remote naked pairs" should be added to the arsenal of "basic" advanced techniques. And i wonder, if it would not be a good idea to look for them before to search for xy-wings. I remember, that my friend, who is a better manual solver than me, sometimes said "look, this is suspicious, the pair here and the same pair there..., so this cannot be ...". So she found the same, but there was no name for it.
Now, those players are no sudoku scientists and dont like long, though meaningful names. Thats why i prefer W-Wing.

I have posted this 37 clue puzzle here and on the dailysudoku forum:
Code: Select all
 +-------+-------+-------+
 | 1 . . | 4 5 . | . 8 . |
 | 4 . 7 | 1 8 . | . . 3 |
 | 8 . . | 3 2 7 | 1 . 4 |
 +-------+-------+-------+
 | 2 7 . | 6 3 . | 4 . 5 |
 | 3 . . | . 7 . | . 2 6 |
 | . . . | . . . | 3 . . |
 +-------+-------+-------+
 | . 1 . | . . . | . . 2 |
 | . . 2 | 7 1 . | . . . |
 | 7 8 . | 2 6 . | 5 . 1 |
 +-------+-------+-------+
Following the hierarchy of Explainers solving methods you would solve it with
x-wing, 3 xy-wings, 1 semi-remote naked pair, xyz-wing, x-wing, xy-wing.
SudoCue:
x-wing, 2 xy-wings, ER, 2 ALS, xy-wing
jLo pointed out:
"X-wing, W-wing, XYZ-wing, X-wing, W-wing did it for me".
ravel
 
Posts: 998
Joined: 21 February 2006

Postby re'born » Wed Sep 05, 2007 12:35 pm

For all of the sudoku historians:

I just rediscovered an old post on the Eureka forum (don't ask why I was surfing over there:) ) that is now the earliest appearance I've found of a semi-remote naked pair in the 'literature'. It was written down by John MacLeod and called the "Corkscrew Rule". Of all people, I responded (though I don't remember doing so) with a slight generalization of his rule. This generalization is what is now called W-wing or semi-remote naked pair.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby daj95376 » Tue Jun 03, 2008 7:21 am

How about 3x W-Wing ... for the same two candidates ... with five eliminations for only one candidate.

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

Code: Select all
 +--------------------------------------------------------------------------------+
 |  4       5689    2       |  568     1       5689    |  7       56      3       |
 |  689     3       568     |  578     589     256789  |  4       256     1       |
 |  1       56      7       |  4       3       256     |  8       256     9       |
 |--------------------------+--------------------------+--------------------------|
 |  68      1568    3       |  2       4       56      |  156     9       7       |
 |  2       156     56      |  9       7       3       |  156     8       4       |
 |  79      79      4       |  568     58      1       |  56      3       2       |
 |--------------------------+--------------------------+--------------------------|
 |  58      4       1       |  3       589     89      |  2       7       6       |
 |  57      2       9       |  1       6       57      |  3       4       8       |
 |  3       678     68      |  78      2       4       |  9       1       5       |
 +--------------------------------------------------------------------------------+

Code: Select all
5- r1c8 -6- r1c4 =6= r6c4 -6- r4c6 -5  => [r1c6]              <>5
5- r3c2 -6- r2c1 =6= r4c1 -6- r4c6 -5  => [r3c6],[r4c2]       <>5
5- r3c2 -6- r2c1 =6= r4c1 -6- r5c3 -5  => [r2c3],[r4c2],[r5c2]<>5
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby udosuk » Tue Jun 03, 2008 8:56 am

And with these 3 Y/W-wings the puzzle still takes a bit work to solve!:!:

Here is a move that cracks the puzzle (without all those Y/W-wings):

ALS-xz:

ALS A: r247c1={5689}
ALS B: r26c5={589}
restricted common: x=9 (r2c15)
common: z=5 (r26c5+r7c1)

Therefore r7c5, seeing r26c5+r7c1, can't have 5.

PS: Your 3rd Y/W-wing is also workable with the strong link of 6 @ r9c23, and is easier to spot that way.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Previous

Return to Advanced solving techniques

cron