The New Sudoku Players' Forum

[keith]

There are many Sudoku techniques which are based on pattern recognition, including XY-wings, W-wings and Unique Rectangles. ("Pattern Techniques")

There are other techniques which involve logic, not a pattern: Loops, chains, and coloring. These are based on the notions of "Strong Links" and "Weak Links". ("Chaining Techniques")

1. Strong Link: If only two cells in the same house (row, column, or box) contain a particular candidate, these cells are a (conjugate) strong link. In the solution, one of the cells will be that candidate.

2. Weak Link: If any two cells in the same house contain a a candidate, they are a weak link. In the solution, one or both cells will not be that candidate.

The simplest example of the use of strong links is perhaps an X-wing, which is two strong links that "line up" on both ends.

Weak links are useful only in conjunction with strong links. The simplest examples are perhaps the skyscraper and the turbot fish.

Let me propose that we can overlay the two classes of techniques, to make "new" techniques. If we are to do so, we need to expand our definitions of "links".

To start:

3. (XY-wing): One (not both) of two cells not in the same house will be a particular candidate in the solution.

4. (W-wing): One (or both) of two cells not in the same house will be a particular candidate in the solution.
http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=2008

5. (Diagonal UR): Two cells are not in the same house. One is <X>, and/or the other is <Y>.

Code: Select all

 *-------------------------*
 | . . . | .  .  . | . . . |
 | . . . |12  . 125| . . . |
 | . . . | .  .  . | . . . |
 |-------+---------+-------|
 | . . . | .  .  . | . . . |
 | . . . | .  .  . | . . . |
 | . . . | .  .  . | . . . |
 |-------+---------+-------|
 | . . . | .  .  . | . . . |
 | . . . |126 . 12 | . . . |
 | . . . | .  .  . | . . . |
 *-------------------------*

(Thanks to daj and Ruud.)

My question is, how do we take the results of one deduction (a "link" across two cells not in the same house) and use it in another (chaining) deduction?

I made an attempt at this in my post, "W-wing meets coloring".
http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=2028

Best wishes,

Keith

(edited for formatting)

[ronk]

Code: Select all

 *-------------------------*
 | . . . | .  .  . | . . . |
 | . . . |12  . 125| . . . |
 | . . . | .  .  . | . . . |
 |-------+---------+-------|
 | . . . | .  .  . | . . . |
 | . . . | .  .  . | . . . |
 | . . . | .  .  . | . . . |
 |-------+---------+-------|
 | . . . | .  .  . | . . . |
 | . . . |126 . 12 | . . . |
 | . . . | .  .  . | . . . |
 *-------------------------*

My question is, how do we take the results of one deduction (a "link" across two cells not in the same house) and use it in another (chaining) deduction?

On the Players' Forums, you would likely see this strong inference written as ...

r2c6 =5|6= r8c4

... meaning at least one of r2c6=5 and r8c4=6 must be true. More specifically, ...

if r2c6<>5, then r8c4=6
if r8c4<>6, then r2c6=5

This strong inference -- despite the fact that the cells are in different houses -- may be used in a chain just like a strong inference based on a conjugate link or a bivalued cell. Your other cases of xy-wing and w-wing are "derived" strong inferences.

[keith]

Ronk,

Does your logic, and notation, capture the fact that BOTH may be true?

Keith

[re'born]

Ronk,

Does your logic, and notation, capture the fact that BOTH may be true?

Keith

Yes, because a strong link is just a logical OR, allowing both candidates to be true. This, of course, cannot happen when the candidates lie in the same house, but in the case of UR's, it can and does happen often.

[keith]

It is not my intent to take on the great Sudoku theorists.

But:

if r2c6<>5, then r8c4=6
if r8c4<>6, then r2c6=5

is incomplete.

Both r8c4=6 and r2c6=5 are valid (together).

Keith

[re'born]

It is not my intent to take on the great Sudoku theorists.

But:

if r2c6<>5, then r8c4=6
if r8c4<>6, then r2c6=5

is incomplete.

Both r8c4=6 and r2c6=5 are valid (together).

Keith

I don't see how it is incomplete. The statement, "if one isn't true the other is true" allows for the possibility that both are true.

[Ruud]

Keith,
the connection between these candidates is similar to the one between the pincers of an XY-Wing. Both can be true, but we cannot deduce anything from that fact because it doesn't always happen. Therefore, we can omit this "useless" piece of information from our definition.

Ruud

[keith]

Code: Select all

 *-------------------------*
 | . . . | .  .  . | . . . |
 | . . . |12  . 125| . . . |
 | . . . | .  .  . | . . . |
 |-------+---------+-------|
 | . . . | .  .  . | . . . |
 | . . . | .  .  . | . . . |
 | . . . | .  .  . | . . . |
 |-------+---------+-------|
 | . . . | .  .  . | . . . |
 | . . . |126 . 12 | . . . |
 | . . . | .  .  . | . . . |
 *-------------------------*

My question is, how do we take the results of one deduction (a "link" across two cells not in the same house) and use it in another (chaining) deduction?

On the Players' Forums, you would likely see this strong inference written as ...

r2c6 =5|6= r8c4

... meaning at least one of r2c6=5 and r8c4=6 must be true. More specifically, ...

if r2c6<>5, then r8c4=6
if r8c4<>6, then r2c6=5

This strong inference -- despite the fact that the cells are in different houses -- may be used in a chain just like a strong inference based on a conjugate link or a bivalued cell. Your other cases of xy-wing and w-wing are "derived" strong inferences.

How am I missing something?

Please explain: If r2c6 <5>, how do we know that r8c4 <> 6 ??

Keith

[ronk]

Please explain: If r2c6 <5>, how do we know that r8c4 <> 6 ??

I'm assuming there's a typo and you meant ...

If r2c6 = 5, how do we know that r8c4 <> 6 ??

The short answer is ... we don't. For this example UR, we have only the strong inferences ...

if r2c6<>5, then r8c4=6
if r8c4<>6, then r2c6=5

There are no weak inferences, meaning ...

if r2c6=5, we can infer nothing about r8c4
if r8c4=6, we can infer nothing about r2c6

Bi-located like-candidates in a unit (row, column and box) and unlike candidates in a bi-valued cell have both strong and weak inferences, but "uniqueness links" have only strong inferences.

[champagne]

Keith wrote

5. (Diagonal UR): Two cells are not in the same house. One is <X>, and/or the other is <Y>.

Code: Select all

 *-------------------------*
 | . . . | .  .  . | . . . |
 | . . . |12  . 125| . . . |
 | . . . | .  .  . | . . . |
 |-------+---------+-------|
 | . . . | .  .  . | . . . |
 | . . . | .  .  . | . . . |
 | . . . | .  .  . | . . . |
 |-------+---------+-------|
 | . . . | .  .  . | . . . |
 | . . . |126 . 12 | . . . |
 | . . . | .  .  . | . . . |
 *-------------------------*

(Thanks to daj and Ruud.)

My question is, how do we take the results of one deduction (a "link" across two cells not in the same house) and use it in another (chaining) deduction?

The question has been answered with the logical OR

r2c6 =5|6= r8c4


I would just add a comment on the way such a situation is handled in "full tagging".

A logical OR has always a corrresponding "weak link" on groups complementary to the components of the logical OR. (may be one, not both).


These groups can enter in an alternate chain as any other weak link.

To be honest, I have not yet implemented use of that OR condition coming out of UR. It seems a little to specific and likely overlapping existing solving capabilities.

Nevertheless, this is a very common situation. Any distant weak link is working the same way.

[keith]

Keith,
the connection between these candidates is similar to the one between the pincers of an XY-Wing. Both can be true, but we cannot deduce anything from that fact because it doesn't always happen. Therefore, we can omit this "useless" piece of information from our definition.

Ruud

Incorrect. The pincers of an XY-wing cannot both be true.

XZ-XY-YZ

Only one can (and one must) be Z.

Keith

[keith]

Keith,
the connection between these candidates is similar to the one between the pincers of an XY-Wing. Both can be true, but we cannot deduce anything from that fact because it doesn't always happen. Therefore, we can omit this "useless" piece of information from our definition.

Ruud

Really? "Useless information"?

Let me try to explain.

Notation:
# Any value
== Strong Link
-- Weak link
++ W-link
a (lower case) Is not true
A (upper Case) Is true


Strong Link:

Two cells are connected in the same house (or not) by the fact that one, and only one, must be true. Possibilities are:

a == A
A == a


Weak Link:

Two cells are connected in the same house (or not) by the fact that one, or both, are not true. Possibilities are:

a -- A
A -- a
a -- a


W-link:

Two cells are connected, not in the same house, by the fact that one, or both, are true. Possibilities are:

a ++ A
A ++ a
A ++ A


Now, suppose we have a chain of five links:



Simple coloring:

#==#==#==#==#==#

Possibilities are:

a==A==a==A==a==A
A==a==A==a==A==a

Any other cell that sees both ends of the chain cannot be A.



Multi-coloring:

#==#--#==#==#==#

Possibilities are:

a==A--a==A==a==A
A==a--A==a==A==a
A==a--a==A==a==A

Any other cell that sees both ends of the chain cannot be A.

(Extra credit: Note that the ends of this multi-coloring chain are a W-link.)



W-coloring:

#==#++#==#==#==#

Possibilities are:

a==A++a==A==a==A
A==a++A==a==A==a
a==A++A==a==A==a

Any other cell that sees both ends of the chain ... You can make no statement!!

But, if you lengthen (or shorten) the chain by two links, one on each side of the W-link:

Possibilities are:

A==a==A++a==A==a==A==a
a==A==a++A==a==A==a==A
A==a==A++A==a==A==a==A

Any other cell that sees both ends of the chain cannot be A.

"Useless" information, indeed!

(And, for double extra credit, note that the ends of the above chain are a W-link.)

Keith

[keith]

I'm assuming there's a typo and you meant ...

If r2c6 = 5, how do we know that r8c4 <> 6 ??

Ronk,

It was not a typo, just my misunderstanding of accepted notation. You understood my intended message correctly, and I thank you for your reply.

Keith

[daj95376]

Incorrect. The pincers of an XY-wing cannot both be true.

XZ-XY-YZ

Only one can (and one must) be Z.

It will be interesting to see you solve this PM w/o [r4c5]=1,[r6c1]=1 of the XY-Wing being true.

Code: Select all

PM from Simple Sudoku xy-wing3.ss
 *--------------------------------------------------------------------*
 | 8      7      5      | 3      4      1      | 6      2      9      |
 | 349    6      49     | 789    278    257    | 378    134    1358   |
 | 349    2      1      | 789    678    567    | 378    34     358    |
 |----------------------+----------------------+----------------------|
 | 6-1    9      36     | 2     *13     8      | 5      7      4      |
 | 57     35     8      | 6      379    4      | 239    19     123    |
 |*17     4      2      | 5      1379  *37     | 39     8      6      |
 |----------------------+----------------------+----------------------|
 | 4569   35     479    | 478    2678   2367   | 1      369    238    |
 | 469    1      479    | 478    23678  2367   | 2389   5      238    |
 | 2      8      36     | 1      5      9      | 4      36     7      |
 *--------------------------------------------------------------------*


[Ruud]

Keith,
the connection between these candidates is similar to the one between the pincers of an XY-Wing. Both can be true, but we cannot deduce anything from that fact because it doesn't always happen. Therefore, we can omit this "useless" piece of information from our definition.

Incorrect. The pincers of an XY-wing cannot both be true.

XZ-XY-YZ

Only one can (and one must) be Z.

Since the pincers never belong to the same house (otherwise we would have a naked triple), they can have the same value.

Possible resolutions to XZ-XY-YZ are:
Z-X-Y
Z-X-Z
Z-Y-Z
X-Y-Z

Ruud