Links: Not in MY House!

Advanced methods and approaches for solving Sudoku puzzles

Links: Not in MY House!

Postby keith » Sun Sep 30, 2007 7:45 pm

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)
keith
2017 Supporter
 
Posts: 221
Joined: 03 April 2006

Re: Links: Not in MY House!

Postby ronk » Sun Sep 30, 2007 9:18 pm

keith wrote:
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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby keith » Sun Sep 30, 2007 9:53 pm

Ronk,

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

Keith
keith
2017 Supporter
 
Posts: 221
Joined: 03 April 2006

Postby re'born » Sun Sep 30, 2007 10:21 pm

keith wrote: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.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby keith » Sun Sep 30, 2007 10:38 pm

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
keith
2017 Supporter
 
Posts: 221
Joined: 03 April 2006

Postby re'born » Sun Sep 30, 2007 11:22 pm

keith wrote: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.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Ruud » Mon Oct 01, 2007 12:05 am

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
Ruud
 
Posts: 664
Joined: 28 October 2005

Re: Links: Not in MY House!

Postby keith » Mon Oct 01, 2007 1:31 am

ronk wrote:
keith wrote:
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
keith
2017 Supporter
 
Posts: 221
Joined: 03 April 2006

Re: Links: Not in MY House!

Postby ronk » Mon Oct 01, 2007 2:59 am

keith wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Mon Oct 01, 2007 10:03 am

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.
champagne
2017 Supporter
 
Posts: 7334
Joined: 02 August 2007
Location: France Brittany

Postby keith » Tue Oct 02, 2007 1:25 am

Ruud wrote: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
2017 Supporter
 
Posts: 221
Joined: 03 April 2006

Postby keith » Tue Oct 02, 2007 2:21 am

Ruud wrote: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
Last edited by keith on Mon Oct 01, 2007 10:41 pm, edited 1 time in total.
keith
2017 Supporter
 
Posts: 221
Joined: 03 April 2006

Re: Links: Not in MY House!

Postby keith » Tue Oct 02, 2007 2:34 am

ronk"][quote="keith wrote: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
keith
2017 Supporter
 
Posts: 221
Joined: 03 April 2006

Postby daj95376 » Tue Oct 02, 2007 3:32 am

keith wrote: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      |
 *--------------------------------------------------------------------*
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Ruud » Tue Oct 02, 2007 9:26 am

keith wrote:
Ruud wrote: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
Ruud
 
Posts: 664
Joined: 28 October 2005

Next

Return to Advanced solving techniques

cron