Strong Wing vs XY Wing

Advanced methods and approaches for solving Sudoku puzzles

Strong Wing vs XY Wing

Postby tso » Mon Mar 06, 2006 4:55 am

I thought it might be interesting to contrast the XY-WING with what I'm calling a STRONG WING.

The XY-WING is the shortest forcing chain using all weak links.

The STRONG WING is it's analog using all strong links.

By 'weak link' I mean that at MOST one of the [two connected cells] contains the (link number).
By 'strong link' I mean that EXACTLY one of the [two connected cells] contains the (link number).

Weak links are drawn as single lines, strong links as double lines. The linking numbers are in (paranthesis).


First, an XY-Wing:

Code: Select all
 *-----------------------------------------*
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  . [14]----(1)---[13]  .  |  .   .   .  |
 |  .   |   .  |  .   |   .  |  .   .   .  |
 |-----(1)-----+-----(3)-----+-------------|
 |  .   |   .  |  .   |   .  |  .   .   .  |
 |  . [12]----(2)---[23]  .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |-------------+-------------+-------------|
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 *-----------------------------------------*

If r5c5=2, then r5c2<>2, then r5c2=1, then r2c2<>1
If r5c5=3, then r2c5<>3, then r2c5=1, then r2c2<>1
Therefore, r2c2<>1


Now, a Strong Wing:
Code: Select all
 *-----------------------------------------*
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  . [145]===(1)===[136] .  |  .   .   .  |
 |  .  | |  .  |  .  | |  .  |  .   .   .  |
 |-----(1)-----+-----(3)-----+-------------|
 |  .  | |  .  |  .  | |  .  |  .   .   .  |
 |  . [128]===(2)===[237] .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |-------------+-------------+-------------|
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 *-----------------------------------------*


r5c5<>2, then r5c2=2, then r5c2<>1, then r2c2=1
r5c5<>3, then r2c5=3, then r2c5<>1, then r2c2=1
Therefore, r2c2=1

It's interesting that the two similar patterns have opposite conclusions and therefore cannot co-exist. This is impossible pattern:
Code: Select all
 *-----------------------------------------*
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  . [14]====(1)===[13]  .  |  .   .   .  |
 |  .  | |  .  |  .  | |  .  |  .   .   .  |
 |-----(1)-----+-----(3)-----+-------------|
 |  .  | |  .  |  .  | |  .  |  .   .   .  |
 |  . [12]====(2)===[23]  .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |-------------+-------------+-------------|
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 *-----------------------------------------*

If r5c5=2, then r5c2<>2, then r5c2=1, then r2c2<>1
If r5c5<>3, then r2c5=3, then r2c5<>1, then r2c2=1
This is a contradiction.

If r5c5=3, then r2c5<>3, then r2c5=1, then r2c2<>1
If r5c5<>2, then r5c2=2, then r5c2<>1, then r2c2=1
Also a contradiction.

This leads to this slightly interesting pattern:
Code: Select all
 *-----------------------------------------*
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  . [14]====(1)===[13]  .  |  .   .   .  |
 |  .  | |  .  |  .  | |  .  |  .   .   .  |
 |-----(1)-----+-----(3)-----+-------------|
 |  .  | |  .  |  .  | |  .  |  .   .   .  |
 |  . [12]====(2)===[235] .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |-------------+-------------+-------------|
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 *-----------------------------------------*


If r5c5<>5, the puzzle has no solution, therefore, r5c5=5.
tso
 
Posts: 798
Joined: 22 June 2005

Re: Strong Wing vs XY Wing

Postby ronk » Mon Mar 06, 2006 5:46 am

tso wrote:This leads to this slightly interesting pattern:
Code: Select all
 *-----------------------------------------*
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  . [14]====(1)===[13]  .  |  .   .   .  |
 |  .  | |  .  |  .  | |  .  |  .   .   .  |
 |-----(1)-----+-----(3)-----+-------------|
 |  .  | |  .  |  .  | |  .  |  .   .   .  |
 |  . [12]====(2)===[235] .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |-------------+-------------+-------------|
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 *-----------------------------------------*


If r5c5<>5, the puzzle has no solution, therefore, r5c5=5.

AIR ???:D:D
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Strong Wing vs XY Wing

Postby Jeff » Mon Mar 06, 2006 6:47 am

tso wrote:By 'weak link' I mean that at MOST one of the [two connected cells] contains the (link number).
By 'strong link' I mean that EXACTLY one of the [two connected cells] contains the (link number).

Hi Tso, good catch.:D How effectively would these definitions help one to identify these links.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby tso » Mon Mar 06, 2006 3:33 pm

I define terms like 'weak' and 'strong' within posts like like this because of my worry that I'll use a term incorrectly or that not everyone will interpret them the same way rather than try to get people to follow my lead. I assume terms can have multiple definitions depending on context without confusion as long as the definitions are specified.

I find it easier to think of patterns that exist all-at-once rather than as a sequence of nodes and links that depend on the direction of propagation. A link between two cells can be drawn without regard to connections between any other two cells. I want to be able to draw links before I know how they will be used.


AIR? Almost IR?
tso
 
Posts: 798
Joined: 22 June 2005

Postby ronk » Mon Mar 06, 2006 3:47 pm

tso wrote:AIR? Almost IR?

Yes, almost impossible rectangle, and an AIR acronym seemed funny to me at the time.

This (sudoku) world is full "almosts" lately. Personally, I think I'm AR. That's almost rich, but almost almost rich might be the reality.:D

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tso » Mon Mar 06, 2006 6:21 pm

ronk wrote:
tso wrote:AIR? Almost IR?

Yes, almost impossible rectangle, and an AIR acronym seemed funny to me at the time.


It doesn't have to be rectangular.

Code: Select all
 
 *-----------------------------------------*
 |  .   .  [14]|  .   .  [13]|  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 | [12] .   .  |  . [235] .  |  .   .   .  |
 |-------------+-------------+-------------|
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |-------------+-------------+-------------|
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 *-----------------------------------------*


Also, haven't found this pattern in an actual puzzle -- its just theoretical at this point. There may be a perfectly good reason why I'll never come across this.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Mike Barker » Sat Mar 11, 2006 3:20 pm

I'm just trying to get my arms around nice loops, but consider a more general form of the strong wing (I'm using "#" instead of "=" for vertical strong links)
Code: Select all
 A=w=B
 ?   #
 z   x
 ?   #
 D=y=C

If A?z?D is a strong link with a label other than w or y, then Nice Loop Th. 1 applies - not a strong wing. In all other cases then A<>y and D<>w. In the case that A?z?D is a strong link with label w (or y) then D<>w => A=w (A<>y => D=y). This is Th. 3, but we didn't need Th. 3. First of all, this approach makes a strong wing and an XY-wing look alot more alike. In both cases we eliminate two candidates from two cells:
Code: Select all
Strong wing:
 A=w=B
 |   #
 |   x
 |   #
 D=y=C

XY wing:
 (wx)-x-(xy)
  |      |
  |      y
  |      |
  D---w-(yw)

In both cases D<>w (typical XY-wing). Note also in both cases A<>y.
There is a lot of symmetry in these examples - so much so that it seems that Nice Loops Th. 3-5 could be combined into 1.

Consider first an additional line drawing rule 8:
    1) Use solid lines and +ve labels to show strong links.
    2) Use broken lines and -ve labels to show 'links'.
    3) Draw solid line between nodes with conjugate relationship in a unit.
    4) Draw broken line between bivalue nodes sharing same candidate.
    5) Draw broken line between ends of 2 solid lines with same labels.
    6) Draw broken line between the end of a solid-line to a bivalue node with the same labels.
    7) Identify nice loops. Draw additional broken lines to complete nice loops as required.
    8) Draw a broken line from a node to a bivalue node sharing the same candidate.
Rule 8 might be explicit in rule 7, but it seems good to make it explicit. Note the directionality of the link.

Next a theorem which combines Th. 3-5 (one theorem to rule them all):
Theorem 6: At the discontinuity of a nice loop, the digit that would label the discontinuity can be eliminated.

I use the term "would" because at a discontinuity I don't understand how there can be a label since it violates all of the line drawing rules. Depending on the direction there are two possible labels for the discontinuity. For example, coming from a strong link, rule 5 or 6 would require the label to be minus the strong link label. Depending on the direction this label would have two different values.

Consider the strong wing with a discontinuity between A and D. If A->D is a strong link then Th. 3 would have held, if not then Th. 5 (assume y<>w below otherwise the loop is continuous). Labels at the discontinuity are shown in braces:
Code: Select all
clockwise starting at A where rule 5 would be used for [-y]:
 A=w=B
 |   #
[-y] x
 |   #
 D=y=C

counter clockwise starting at D where rule 5 would be used for [-w]:
 A=w=B
 |   #
[-w] x
 |   #
 D=y=C

In the first case Th. 6 gives A<>y and in the second D<>w.

An XY-wing where the discontinuity is at D would have used Th. 4 (assume w<>y and w<>x otherwise the solution is trivial):
Code: Select all
clockwise starting at D where rule 4 would be used for [-w]:
 (wx)-x--(xy)
  |       |
 -w       y
  |       |
  D-[-w]-(yw)

counter clockwise starting at D where rule 4 would be used for [-w]:
 (wx)-x--(xy)
  |       |
[-w]      y
  |       |
  D---w--(yw)

This is where rule 8 is used since D is not necessarily a bivalue. In both cases by Th. 6, D<>w and of course A<>y (doesn't really matter, but maintains the symmetry).

In the case of transitioning from a strong link to a bivalue cell, Th. 5 would be used (assume y<>w below otherwise the loop would be continuous):
Code: Select all
clockwise starting at A where rule 6 would be used for [-y]:
  A==w==B
  |     #
[-y]    x
  |     #
 (xy)-x-C

counter clockwise starting at D where rule 6 would be used for [-w]:
  A==w==B
  |     #
[-w]    x
  |     #
 (xy)-x-C

Again by Th. 6, we have A<>y and D<>w, although the later is trivial.

I can't claim this as a proof of Th. 6, but it sure supports its validity. Of course being new to nice loops I could be out in left field. On the other hand there is a lot of symmetry between Th. 1, 2, and 6 - I wonder if there isn't one final theorem to rule them all?
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Jeff » Sat Mar 11, 2006 5:10 pm

Hi Mike, I have read your post 3 times already. But, I still don't know what you are trying to do regarding the nice loop and b/b plot technique. Would it be that my description on the subject isn't all that clear? In which case, I'll be happy to explain. But, I couldn't see any questions asked.

May be I should clarify the following:

To be specific, 'strong inference' and 'weak inference' should be used to describe the type of link between nodes. 'Strong link' is not a good term because it can have a strong inference as well as a weak inference.

All weak inferences should have a -ve label.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Mike Barker » Sat Mar 11, 2006 10:30 pm

Like I said I'm just starting to understand nice loops. If I were to present the post as questions they would be:
1) Would it be better to define a stong wing as three links with strong inference and a discontinuity rather than specifically a fourth link with strong inference as this allows much stronger similarities between the strong wing and an XY-wing, ie eliminations using Th. 5 rather than Th. 3?
2) in constructing a nice loop for an XY-wing it seems that the first step is to contruct a link from the cell where the elimination may occur (D in the post) to a bivalue. Given the construction rules is this valid or do we need an 8th rule which allows a weak inference from an arbitrary cell to a bivalue cell where both contain the labeled candidate?
3) the three theorems for discontinuous nice loops all appear to be closely related. Is it possible to combine them into one theorem, eg theorem 6, and deal with one common theorem rather than applying each of the three to a given situation?
4) At a discontinuity how does one apply a label since by definition a valid link cannot be constructed and it appears that there are actually two possible candidates for the link depending on the direction?

The post attempts to answer these questions though apparently not very clearly. Also when I show a link as ---w---, the minus sign is there its just included in the line. If this is unclear I'll put parentheses around the -w.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Jeff » Sun Mar 12, 2006 6:08 am

Hi Mike, This is much clearer with the questions.:D May I give you my version of answers to these questions?

Mike Barker wrote:1) Would it be better to define a strong wing as three links with strong inference and a discontinuity rather than specifically a fourth link with strong inference as this allows much stronger similarities between the strong wing and an XY-wing, ie eliminations using Th. 5 rather than Th. 3?

Let me clarify that the discontinuity in a nice loop is actually a node, not a link. In that sense, strong ring/strong wing and xy-ring/xy-wing have the following similarities:

    Strong wing
    length=4
    discontinuous loop
    all links with strong inference
    Candidate inclusion at discontinuity

    xy-wing
    length=4
    discontinuous loop
    all links with weak inference
    Candidate exclusion at discontinuity

    Strong ring
    length=4
    continuous loop
    all links with strong inference
    Candidate exclusion in cell between 2 adjacent strong links

    xy-ring
    length=4
    continuous loop
    all links with weak inference
    Candidate exclusion in other cells of the unit housing a weak link
Your idea about changing the application of theorems is based upon the discontinuity being mistaken as a link rather than a node. This is a fundamental change and it surely affects the entire operation.

Mike Barker wrote:2) in constructing a nice loop for an XY-wing it seems that the first step is to contruct a link from the cell where the elimination may occur (D in the post) to a bivalue. Given the construction rules is this valid or do we need an 8th rule which allows a weak inference from an arbitrary cell to a bivalue cell where both contain the labeled candidate?

The construction rules are related to the b/b plot which should be done for the entire grid, but not for just one single loop at a time. After all links of strong inference and weak inference are drawn, nice loops can be identified by pattern recognition by adding a final link or two to complete each loop, thus overcoming the problem on which cell to start looking for a chain. Your rule No.8 suggests picking a cell hoping that elimination may occur and draw all possible links from that cell to other nodes, does fall into the category of trial and error in my opinion. On the other hand, if you draw all possible links for the whole grid in accordance with rule No.8, the grid will end up as a pile of spaghetti that makes pattern recognition impossible.

Mike Barker wrote:3) the three theorems for discontinuous nice loops all appear to be closely related. Is it possible to combine them into one theorem, eg theorem 6, and deal with one common theorem rather than applying each of the three to a given situation?

As I said, the identification of nice loops is based upon pattern recognition of links drawn in a b/b plot. The function of the different theorems is to allow us to look at the b/b plot and recognise (a) that a loop is valid and (b) what type of deduction is resulted in that loop. To this regard, I don't know how the theorems can be combined without compromising this function.

Mike Barker wrote:4) At a discontinuity how does one apply a label since by definition a valid link cannot be constructed and it appears that there are actually two possible candidates for the link depending on the direction?

If you take the discontinuity as at a node rather than a link, you will not have this problem.
Last edited by Jeff on Sun Mar 12, 2006 11:39 am, edited 3 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Mike Barker » Sun Mar 12, 2006 2:25 pm

Thanks, I understand a lot better now.
Mike Barker
 
Posts: 458
Joined: 22 January 2006


Return to Advanced solving techniques