The New Sudoku Players' Forum

[tso]

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.

[ronk]

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 ???

[Jeff]

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. How effectively would these definitions help one to identify these links.

[tso]

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?

[ronk]

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.

Ron

[tso]

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.

[Mike Barker]

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?

[Jeff]

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.

[Mike Barker]

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.

[Jeff]

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

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.

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.

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.

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.

[Mike Barker]

Thanks, I understand a lot better now.