Forcing chains: Terminology and Definition

Advanced methods and approaches for solving Sudoku puzzles

Postby Jeff » Fri Jan 13, 2006 4:59 am

ronk wrote:
Jeff wrote:
Bob Hanson wrote:A={26 23}
B={79 39 679}
x=3 (weak link)
z=6 (can be eliminated)

Ronk, can you see that the unit (box 4) housing the weak link with label 3 above has exactly 2 nodes (r4c3 & r6c2) containing the digit 3?:D

Bob Hanson was illustrating bennys' almost locked set xz rule ... which requires only a weak link for x. So with "x=3 (weak link)" above, Bob was merely denoting the requirements of the rule ... NOT that the 'edge' between the two candidates is a weak link.

Hi Ronk, This is exactly why the term 'weak link' is so confusing. In this particular case, it is not just an indication, but a clear description that confirms 'x=3 (weak link)' is a weak link with a 3 label. Yet, the 2 nodes of the link have a conjugate relationship. No matter what the reason is, you cannot rule out the fact that the definition of 'weak link > 2' and the actual usage are inconsistent.

Another point. You mentioned in your statement that a weak link for x is a requirement of the xz rule. But, according to your own definition ‘weak link > 2’, the link with conjugate nodes r4c3 & r6c2 surely doesn’t meet that requirement. Nevertheless, this problem can be easily overcome by defining ‘weak link >= 2’, a definition that make good sense.

ronk wrote:My answer is "no" to the direct question ... because the meaning of "weak link" is too well established.

Perhaps it's more appropriate to say that the meaning of 'weak link' has been well established in every individual's mind, but these meanings are not necessarily same.

ronk wrote:At the moment, I don't have any better suggestions than "conjugate" and "unconditional" ... but I'll definitely give it some thought.

There is no ambiguity problem regarding the terms 'conjugate' and 'unconditional'.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Jan 13, 2006 5:31 am

tso wrote:I know its months to late to bring this up, but, but I've always wondered why (and been confused because) the term "unconditional" is used rather than "conditional" and "conjugate" is used instead of "unconditional"


Image

This nice diagram:D from Ronk explains the situation.

A 'conjugate link' is conditional because the labeled digit must appear exactly 2 times in the unit. The set element of conjugate link is the number of times the link label appears in the unit = {exactly 2}.

An 'unconditional link' is unconditional because there is no restriction on the number of times the labeled digit must appear in the unit. The set element of unconditional link is the number of times the link label appears in the unit = {exactly 2,3,4.......}.

For example, there is a requirement for an xy-chain to have bivalue nodes. But, there is no requirement on the type of links. In other words, the end-node relationship of the links could be conjugate or non-conjugate. Hence, the links being used in an xy-chain can be regarded as unconditional.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Forcing chains: Terminology and Definition

Postby Jeff » Fri Jan 13, 2006 5:57 am

tarek wrote:The use of Multi & Poly can get confusing..... Using the Forcing net as a general term then using implcation nets (double/triple/poly) as subsets is better & delete the terms multi/mutiple, or the other way round, because we use the words DOUBLE & TRIPLE, replace every poly with Multi or Multiple.

Hi Tarek, you are right, the use of Multi & Poly can get confusing.....:( However, I think the answer is not to delete them all, but to make it more user friendly. The problem is with '-implication', but not with 'multi'. How about we just retain 'multiple implication' or change it to something like 'multiple inference'.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Jan 13, 2006 6:03 am

tarek wrote:Is it possible to give an example on how to write the notation for a poly implication net ?

Hi Tarek, Refer the example under the definition of ‘forcing net’. It's a double implication net, but the principle is the same for a poly implication net.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Jan 13, 2006 6:54 am

Hi Ronk, According to this post , Wolfgang is believed to be the one who introduced 'strong link' and 'weak link' to this forum. His post under this thread (quoted below for easy reference) reflects his latest opinion on the 'weak link' issue.
Wolfgang wrote:I agree with Jeff that a strong link *also* is a weak link, because if for some chain or technique you need a weak link at some place, you always can use a strong link also.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Jan 13, 2006 7:19 am

Here is another example showing that a weak link does include end nodes with conjugate relationship, ie. exactly 2 candidates in the unit.

The following description of an xy-wing was extracted from the Sudoku Assistant site.

Image

In this description, the term 'weak link' is being used to describe the type of links required for an xy-wing. Needless to say, these weak links must include links with a conjugate relationship. Otherwise, a good proportion of xy-wings will not be able to meet the requirement.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Jan 13, 2006 8:00 am

Hi Ronk, here is another post that describes and uses strong and weak links in forcing chains. The relevant statements are quoted below for easy reference:

Nick70 wrote:..........One thing that perhaps I haven't made very clear when talking about forcing chains, is that the alternation of strong and weak links is the fundament of its power. In fact, I always write chains with this notation:

Code: Select all
(6,8)=5 => (6,8)<>2 => (6,5)=2 => (1,5)<>2 => (1,3)=2
(2,8)=5 => (2,5)<>5 => (2,5)=2 => (1,5)<>2 => (1,3)=2

Each transition from = to <> is a weak link, each transition from <> to = is a strong link. It is of course not necessary for weak links to be weak, they could also be strong but their strongness is not needed for the chain to work...........

The statement "It is of course not necessary for weak links to be weak, they could also be strong but their strongness is not needed for the chain to work" spells out that a weak link can have end-nodes with conjugate relationship, ie. a strong link can be used as if it is a weak link.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Forcing chains: Terminology and Definition

Postby tarek » Fri Jan 13, 2006 12:55 pm

Jeff wrote:
Code: Select all
Example:

 *-----------------------------------------------------------------------------*
 | 247     5       28      | 479     4789    1       | 6       379     3789    |
 | 3       1478    6       | 479     45789   2       | 578     1579    5789    |
 | 17      178     9       | 3       5678    678     | 2       157     4       |
 |-------------------------+-------------------------+-------------------------|
 | 79      679     4       | 5       3       679     | 1       8       2       |
 | 1279    123679  23      | 8       679     4       | 57      35679   359     |
 | 8       3679    5       | 1       2       679     | 4       3679    39      |
 |-------------------------+-------------------------+-------------------------|
 | 6       2489    1       | 479     4789    5       | 3       27      78      |
 | 245     2348    238     | 6       478     378     | 9       257     1       |
 | 59      389     7       | 2       1       389     | 58      4       6       |
 *-----------------------------------------------------------------------------*

r9c1=5 => r9c7=8 => r7c9=7 (=> r8c8<>7) => r7c8=2 => r8c8=5 => r3c8<>5 => (r3c18=17) => r3c2<>17 => r3c2=8 => r1c3=2 => r5c3=3

r9c1=9 (=> r5c1<>9) => r4c1=7 (=> r5c1<>7) => r3c1=1 => r5c1=2 => r5c3 =3

Therefore r5c3=3

where
(=> r8c8<>7), (=> r5c1<>9) and (=> r5c1<>7) are multiple implications.
(r3c18=17) is a grouped node, not a multiple implication.



Thanx Jeff,

My solver probably would do the first line less elegantly as follows:
r9c1=5 => r9c7=8 => r7c9=7 (=> r8c8<>7) => r7c8=2 => r8c8=5 => r3c8<>5 => (r3c18=17) => r3c2<>1 (=>r3c2<>7) => r3c2=8 => r1c3=2 => r5c3=3

Tarek
User avatar
tarek
 
Posts: 2612
Joined: 05 January 2006

Postby ronk » Fri Jan 13, 2006 1:12 pm

Jeff wrote:This is exactly why the term 'weak link' is so confusing. In this particular case, it is not just an indication, but a clear description that confirms 'x=3 (weak link)' is a weak link with a 3 label. Yet, the 2 nodes of the link have a conjugate relationship. No matter what the reason is, you cannot rule out the fact that the definition of 'weak link > 2' and the actual usage are inconsistent.

Jeff, making a distinction between 'what a link is' (type) and 'how a link is used' (usage) isn't difficult IMO. The context should make it clear, if not always then almost always. IOW the statements ...

a weak link can only be used as a weak link (if A true, then B false), and
a strong link can be used as either a strong link (if A false, then B true) or a weak link

.. should not be leading to confusion IMO. By comparison, I still have to pause to reason out what 'unconditional link' means, even though I've been reading and using the term for several weeks now. So ... for different reasons ... it appears we're both confused.:)

As much as I dislike the introduction of new terms (especially poly-syllabled ones (pun)), maybe we need different terms for link type and link usage. ('Conjugate link' and 'unconditional link' don't really do that since 'conjugate link' is also a term indicating both type and usage.)

The only possible terms I've come up with are 'assertion link' and 'negation link' where ...

'assertion' strongly hints its usage : if A asserted (is true), then B is false, and
'negation' strongly hints its usage: if A negated (is false), then B is true.

Then we would say ...

A weak link (or any other applicable type) can only be used as an assertion link, and
A strong link (or any other applicable type) can be used either as an assertion link or a negation link.

Jeff wrote:You mentioned in your statement that a weak link for x is a requirement of the xz rule. But, according to your own definition ‘weak link > 2’, the link with conjugate nodes r4c3 & r6c2 surely doesn’t meet that requirement. Nevertheless, this problem can be easily overcome by defining ‘weak link >= 2’, a definition that make good sense.

Jeff, you're obviously an intelligent guy. That being the case, I really don't understand why you have difficulty distinguishing between link type and link usage.:(

Jeff wrote:
ronk wrote:My answer is "no" to the direct question ... because the meaning of "weak link" is too well established.

Perhaps it's more appropriate to say that the meaning of 'weak link' has been well established in every individual's mind, but these meanings are not necessarily same.

My pencil is not that sharp.:)

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

Postby vidarino » Fri Jan 13, 2006 1:43 pm

Hmm, how about adding a new term; "any-link", that really is >=2?

E.g. an x-cycle would then expressed as a chain of strong->any->strong->any links, instead of the more traditional, but arguably more ambiguous strong->weak->strong->weak...

Either would be correct, as far as I can tell, but the use of "any" makes it clearer that indeed any kind of link will do.

Just my 0.02 norwegian kroner. ;)
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Jeff » Fri Jan 13, 2006 2:43 pm

Hi Ronk, Try not to over-complicate the issue. We surely don't need any more new terms. Take a look at the examples I posted and you might get an overall picture on how the terms 'strong' and 'weak' are being used to their best potential.

Those who consider 'weak link has >= 2 nodes in the unit' would appreciate the 2-way-implication property of a strong link, and would like to find a way to differentiate the direction of the implication being used. So, here is the deal:

    Let 'weak link' means if A is true, then B is false (only choice).
    Let 'strong link' just means if A is false, then B is true (forego the other direction)
    If a strong link operates in the opposite direction (ie. if A is true, then B is false), lets call it a weak link.
Having defined strong and weak in this fashion, the exact mode of implications can be reflected by the type of links used. This is very important for description of a technique using strong and weak links.

Those who consider 'weak link has > 2 nodes in the unit' would like to see strong links and weak links being mutually exclusive of each other. The implication modes become:

    'weak link' means if A is true, then B is false (only choice).
    'strong link' means if A is false, then B is true or if A is true, then B is false.
As you can see, the word 'strong' doesn't show a specific direction of implication. For example, we know that the minimum requirement of an xy-wing is to have 4 weak links. With this definition, you will find the following combinations:

    xy-wing No.1 has 2 strong links and 2 weak links,
    xy-wing No.2 has 1 strong link and 3 weak links,
    xy-wing No.3 has 3 strong links and 1 weak link, and
    xy-wing No.4 has 4 strong links,
just because you want to keep the terms ‘strong’ and ‘weak’ completely separate.

Having done the research, I am becoming more convinced that a weak link should have >= 2 nodes in the unit.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Jan 13, 2006 3:07 pm

vidarino wrote:Hmm, how about adding a new term; "any-link", that really is >=2?

E.g. an x-cycle would then expressed as a chain of strong->any->strong->any links, instead of the more traditional, but arguably more ambiguous strong->weak->strong->weak...

Either would be correct, as far as I can tell, but the use of "any" makes it clearer that indeed any kind of link will do.

Thank you for sharing your thought, vidarino.

At the moment, x-cycle has been defined as .....conjugate->unconditional->conjugate->unconditional.....with an effort to avoid 'strong' and 'weak' at the time when the technique was being described. So, I don't have a problem in that area. I do admit that 'any' is more concise and perhaps as meaningful.:D However, I try not to consider any new terms before I am sure that I cannot claim back what's the best for the terms 'strong' and 'weak.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Fri Jan 13, 2006 4:32 pm

Jeff wrote:Try not to over-complicate the issue. We surely don't need any more new terms.

You've apparently forgotten that you asked.
Jeff wrote:I understand that the definitions are for forcing chains, not specifically for bilocation/bivalue plot. Would you like to suggest some good words to describe the terms in question?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Fri Jan 13, 2006 4:53 pm

ronk wrote:
Jeff wrote:Try not to over-complicate the issue. We surely don't need any more new terms.

You've apparently forgotten that you asked.
Jeff wrote:I understand that the definitions are for forcing chains, not specifically for bilocation/bivalue plot. Would you like to suggest some good words to describe the terms in question?

Sorry Ronk, it was my poor expression again. What I meant to say was to use better words to describe the existing terms, but not to invent more terms to describe similar things.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Forcing chains: Terminology and Definition

Postby ronk » Fri Jan 13, 2006 5:38 pm

Jeff wrote:Implication Stream - a sequence of nodes where implications are made from one node to the other(s).

Code: Select all
Example:

r1c3=9 => r8c3=7 => r8c9=3 => r3c9=2 => r2c8=1 => r2c8=5 => r1c8<>5

Your example implication stream is not in canonical form, where weak links and strong links alternate. The canonical form (for the left portion of the stream) might be ...
Code: Select all
r1c3=9 => r8c3<>9 => r8c3=7 => r8c9<>7 => r8c9=3 => r3c9<>3 => r3c9=2 => r2c8<>2
  |-- weak->|--strong->|-- weak->|--strong->|-- weak->|--strong->|-- weak->|


Now where do you suppose the above strong links are located? Don't you think that makes your definition of strong links just a wee bit lacking?
Jeff wrote:Strong Link or Conjugate Link - a link with a labeled digit which appears in exactly 2 nodes within the unit. A strong link implies if A is false, then is B true or if A is true, then B is false.


Aside: The chain may also be expressed as a list with parity tags, such as ...

r1c3#9(T), r8c3#9(F), r8c3#7(T), r8c9#7(F), r8c9#3(T), r3c9#3(F), r3c9#2(T), r2c8#2(F)

for left-to-right implications. Then the T/F parity can just be toggled for right-to-left implications.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques