Forcing chains: Terminology and Definition

Advanced methods and approaches for solving Sudoku puzzles

Re: Forcing chains: Terminology and Definition

Postby Jeff » Fri Jan 13, 2006 6:56 pm

ronk wrote:
Code: Select all
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

I don't intend to standardise the notation of implication streams. One reason being that I have no idea what the standards are. I always feel that any implication streams that show all inferences clearly are good enough. However, if you can provide another implication stream in standard formats, I can list them under the heading of 'Some standard formats of implication streams'.:D

BTW, 2 points that are important to the definitions:

  1. With the information given in the implication stream, how did you know that these links between nodes are 'weak' since your definition of a weak link is 'weak > 2'. In fact, some of these links have end-nodes with conjugate relationship. Does it mean that you are actually applying the definition of 'weak >= 2'?
  2. You have used the term 'strong link' loosely. You should have specified that these strong links are bivalue links between candidates within a cell.:(
All links described in the definition list are bilocational links between nodes. I defined bilocational links only because I needed them to define continuous cycle and discontinuous path. There is already enough confusion on strong and weak links between nodes. Introducing strong and weak links between candidates will definitely confuse the issue even more, and the benefit is minimal as far as forcing chains are concerned.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Forcing chains: Terminology and Definition

Postby ronk » Fri Jan 13, 2006 7:33 pm

Jeff wrote:With the information given in the implication stream, how did you know that these links between nodes are 'weak' since your definition of a weak link is 'weak > 2'. In fact, some of these links have end-nodes with conjugate relationship. Does it mean that you are actually applying the definition of 'weak >= 2'?

Amazing! You *still* don't get the distinction between link type and link usage ... and yet you are able to use your "sharp pencil" to critique, or even criticize others.

Jeff wrote:You have used the term 'strong link' loosely. You should have specified that these strong links are bivalue links between candidates within a cell.

Check out some of Bob Hanson's posts, and you'll see he has the same viewpoint. You selectively cited him to make your point, yet you filtered out his viewpoints with which you don't agree.

Jeff wrote:All links described in the definition list are bilocational links between nodes. I defined bilocational links only because I needed them to define continuous cycle and discontinuous path. There is already enough confusion on strong and weak links between nodes. Introducing strong and weak links between candidates will definitely confuse the issue even more, and the benefit is minimal as far as forcing chains are concerned.

No kidding. I've come to the conclusion that you are not of an open mind and have an agenda to promote bivalue/bilocation plots and nice loops in conjunction with forcing chains so I'll get, and stay, out of your way.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Forcing chains: Terminology and Definition

Postby Jeff » Fri Jan 13, 2006 9:32 pm

ronk wrote:Amazing! You *still* don't get the distinction between link type and link usage ... and yet you are able to use your "sharp pencil" to critique, or even criticize others.

Hi ronk, you are right. I didn't understand, so I asked. Your response doesn't seem to be very helpful though.

ronk wrote:Check out some of Bob Hanson's posts, and you'll see he has the same viewpoint. You selectively cited him to make your point, yet you filtered out his viewpoints with which you don't agree.

Could you just tell me what viewpoint are you referring to? I admit I have just read what I considered relevant to the issue at hand. This is the first time I come across links being used to express the strongness of a node. I don't know why this is important as I have never seen it being used in this forum; may be it's just me. I did observe that you were trying to use the term 'strong link' for something else though, so I made a point. Your response doesn't seem to be very helpful though.

ronk wrote:No kidding. I've come to the conclusion that you are not of an open mind and have an agenda to promote bivalue/bilocation plots and nice loops in conjunction with forcing chains so I'll get, and stay, out of your way.

I am sorry Ronk. I simply can't define something that I am not familiar with such as the 'strong link' between candidates that you are trying to introduce in sketchy detail. If you are serious about adding a definition, please give me a better example to show how the term is used? Would it be confusing to describe a different thing with the same name?

BTW, the definitions of b/b plot and nice loop are not on the list, even though I think they should be because they are techniques for identification of forcing chains. Excuse me for being not open mind as expected. Apart from using links between nodes, I really don't know a better way to define forcing chains of continuous type.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby tso » Sat Jan 14, 2006 12:44 am

1) Though I understand Jeff's explanation of what "unconditional" refers to, it strikes me as the same as describing a naked person with two hats as "overdressed".

2) My difficulty with "conjugate" and "unconditional" is that the relationship between the two is not obvious. The usage of "unconditional" cannot be deciphered merely by checking a dictionary and in fact will be taken to mean the opposite by some people (read: me). The search system within this forum is useless to help. Newcomers will continue to be confused with no clear path for clarification. If one is "unconditional", then the other ought to be "conditional". That condition is "conjugated".

3) The advantage with "weak" and "strong" is that there is a clear comparative relationship implied between the two types. The idea a strong link can always be used where only a weak link is needed is implied. Though the exact meaning cannot be discerned simply from the words -- the words are basic enough that the reader will *know* s/he cannot know what they mean in without context, and will not waste time looking in the dictionary. S/he will have to search the forum or figure out what they mean from the context in which they are used.

4) Actually, the word "weak" is superfluous. For all useful purposes, there are only two types of links: STRONG LINKS and simply LINKS. This makes it completely unambiguous that STRONG LINKS are a subset of LINKS in general. There is never a need to specifically use a non-strong link.

5) Words and phrases such as "IF/THEN", "IFF or IF AND ONLY IF", "XOR or EXCLUSIVE OR", "NAND or NOT AND" are in common usage beyond this forum and can be easily looked up elsewhere. STRONG LINK could be described as an IFF LINK. All links are NAND LINKS.

6) Digressing, some use =3= for STRONG LINK and -3- for WEAK. A double line clearly includes a single line. The relationship between -3- and ~3~ is not quite as obvious.

7) I might have posted something like this months ago -- but I was never really sure until this thread what conjugate and unconditional meant.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Jeff » Sat Jan 14, 2006 5:22 am

Hi Tso,

Personally I like 'strong' and 'weak' very much for the same reasons that you have mentioned. It is a pity that the meaning of 'weak' isn't specific enough for technique description that I had to settle with 'unconditional'. I agree that the term 'unconditional' could have double meanings (although this wasn't obvious to me when it was first introduced), and better be replaced. In my previous posts, I have been trying to fix an unambiguous definition to the term 'weak'. If this is successful, no matter which way it turns out to be, I could at least determine whether to replace 'unconditional' with 'weak' or to forget it and move on. So far, I think I have gathered enough evidence and opinions from this forum to shown that 'strong' and 'weak' should not be interpreted as mutually exclusive. But then again, some users may disagree. So, here are some options:

Option 1:
    Strong link - {number of nodes in the unit = 2}
    Link - {number of nodes in the unit >= 2}
Option 2:
    Strong link - {number of nodes in the unit = 2}
    Any-link - {number of nodes in the unit >= 2}
Option 3:
    Strong link - {number of nodes in the unit = 2}
    Free Link - {number of nodes in the unit >= 2}
Option 4:
    Strong link - {number of nodes in the unit = 2}
    Unrestricted link - {number of nodes in the unit >= 2}
Option 5:
    X-link - {number of nodes in the unit = 2}
    Y-link - {number of nodes in the unit >= 2}
Option 6:
    Strong link - {number of nodes in the unit = 2}
    Nominal link - {number of nodes in the unit >= 2}
Option 1 seems to be the most appropriate; perhaps the only problem is that it is not specific enough to be recognised as a definition. In Option 2, the term "Any link' doesn't stand out as a definition; perhaps adding a hyphen (ie. 'Any-link') can improve that.

Actually, I quite like option 5 because a) they are simple to write, b) X feels stronger then Y, c) it fits well with the y-cycle (another name for xy-chain) which consists of all Y-links, and d) it doesn't interfere with the terms 'strong' and 'weak'. I am going to try this in the x-cycle description. What do you, you,...and you think?:D

I suggest a link with 'number of nodes in the unit > 2' be called a non-strong link, hence it is crystal clear what it means.

Tso wrote:Actually, the word "weak" is superfluous. For all useful purposes, there are only two types of links: STRONG LINKS and simply LINKS. This makes it completely unambiguous that STRONG LINKS are a subset of LINKS in general. There is never a need to specifically use a non-strong link.

You are right; there is never a need to specifically use a non-strong link.

Tso wrote:Digressing, some use =3= for STRONG LINK and -3- for WEAK. A double line clearly includes a single line. The relationship between -3- and ~3~ is not quite as obvious.

Agreed. It is even better that the mode of implication can be unambiguously represented by these notations as well. The only way to do this is to define strong link as a subset of weak link.
Last edited by Jeff on Sat Jan 14, 2006 8:36 pm, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Sat Jan 14, 2006 11:24 am

I, too, have been mislead by the existing terms. With a nod to Tso, I like a strong link vs nominal link terminology. A strong link would obviously suffice where only a nominal link was required. I believe it most accurately describes the relationships, yet allows for expansion. For example, we have started using Almost Unique Rectangles (AUR) as nodes, and in this case we could have a new reverse link, where a false implies a true, but a true does not imply anything. It would be nice to incorporate these links into our scheme without having to redefine existing terms.

I also believe that the links should be defined by the logical relationship of their nodes, and not by how many nodes you could have chosen from. Again, this allow for expansion into new territory such as AURs. You can certainly indicate for a normal case that two nodes results in a strong link, whereas 2 or more is a nominal link, but this does not need to be part of the definition.

Any-link, and similar terms are dangerous when it comes to expansion.

We already have too many x's and y's in our terms. In my mind, the relationship of 'x' to 'y' is not the same as 'strong' to 'nominal'.

Just my two cents.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Sat Jan 14, 2006 1:01 pm

Thanks MJ,

Just to clarify that Tso's option is strong link vs link.

Your option is strong link vs nominal link and are to be defined as follows:

    Strong link - if A is false, then B is true
    Nominal link - if A is true, then B is false
Myth Jellies wrote:For example, we have started using Almost Unique Rectangles (AUR) as nodes, and in this case we could have a new reverse link, where a false implies a true, but a true does not imply anything. It would be nice to incorporate these links into our scheme without having to redefine existing terms.

'Strong link' is currently accepted to imply if 'A is false, then B is true' or 'if A is true then B is false'. If we want a 'strong link' to represent 'if A is false, then B is true' only, this existing term would have to be redefined; and I don’t think this can be easily done.

Myth Jellies wrote:We already have too many x's and y's in our terms. In my mind, the relationship of 'x' to 'y' is not the same as 'strong' to 'nominal'.

Just would like to clarify that:

It is 'X-link' vs 'Y-link' in capital letters.
You are right, 'X-link' and 'strong link' are not the same thing in that:

    'X-link' represents 'if A is false, then B is true' only, whereas
    'Strong link' represents if 'A is false, then B is true' or 'if A is true then B is false'.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Sat Jan 14, 2006 6:51 pm

Ah, I am still goofed up with this terminology I guess.

I have been working with the following in my head...

Strong Link: A = not B (same as B = not A; same as if A then (not B) AND if (not A) then B). If only 2 nodes in a group contain candidate x, then those two nodes are strongly linked via x. In a bivalue cell containing only candidates x and y, candidate x is strongly linked to candidate y.

Nominal Link: if A then not B (same as if A true then B false, along with its contrapositive, if B true then A false). Examples include any two cells containing candidate x that belong to the same group, or any two candidates within a multi-candidate cell.

I'm thinking that my definition of a link is not the same as yours, if this does not correspond to your strong and weak links.

[edit--had strongly linked via candidate n--don't know where n came from]
Last edited by Myth Jellies on Sat Jan 14, 2006 4:24 pm, edited 1 time in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby JeffInCA » Sat Jan 14, 2006 7:20 pm

I've read through this entire thread, and I thought I'd just throw in my 2 cents for what it's worth. First, I'd like to thank Jeff for his effort to organize all this terminology. He's obviously put a lot of thought and effort into this pursiut.

That being said, I tend to be in agreement with Tso's recommendation to classify the terms as follows:

Link - number of nodes >= 2
Strong Link - number of nodes exactly = 2

If you go back to Jeff's original definition of Link, it requires at least 2 nodes. Therefore for ALL links by definition there are >= 2 nodes in the unit.

Then a Strong link simply places a further restriction on a link in that it must be a link where exactly 2 nodes contain the candidate value.

Of all of the proposed definitions I think these make it easiest to quickly visualize the pattern from the words, which is the intent, correct? Ironically, this is pretty close to how Jeff's original proposal read at the beginning of the thread.

Regarding X-Link and Y-Link, I definitely want to vote against this as I think it would just lead to confusion with all the other terms out there containing X's and Y's and IMHO there isn't a quick mental connection to the pattern.

Jeff
JeffInCA
 
Posts: 33
Joined: 02 January 2006

Postby ronk » Sat Jan 14, 2006 8:50 pm

Myth Jellies wrote:Nominal Link: if A then not B (same as if A true then B false, along with its contrapositive, if B true then A false)

Contrapositive:?: Now there's a word you don't hear every day, but it's definitely correct. I had to dig up my logic reference to relearn the following:

If the original statement is "if A is true, then B is false", then the converse, inverse, and contrapositive statements are:
converse: "if B is false, then A is true"
inverse: "if A is false, then B is true"
contrapositive: "if B is true, then A is false"

While only the contrapositive is true for a weak link, errr ... nominal link, errr ... unconditional link, errr ... Y-link, errr ... whatever I missed:) ... the converse, inverse, and contrapositive all apply for a strong link.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tso » Sat Jan 14, 2006 9:16 pm

I agree with Myth Jellies that the number of times the candidate appears in a group is one *reason* that there are logical relationships -- they are not the relationships. Those logical relationships are:

ALL links: NOT (A and B)
Strong Links: A if and only if NOT B



(By "ALL links" I mean weak, any, default, etc. Actually, ALL cells in the same group are weakly linked by the candidate(s) they share based on the underlying rules of the game. A blank sudoku grid has weak links between every candidate in every cell and every other cell in its group. Unless we're working on a sudoku variant that allows, say 2 or 3 copies of each digit in a group, the logical relationship is assumed.)

Strong links are "if and only if" or IFF. They could be called IFF links.
ALL links, including Strong links are NOT AND.

One possible drawback from this way of defining the links is that there is no simple way to include Non-Strong Links without falling back on the number of candidates in the group.

One advantage of using IFF and "if/then" rather that candidates=2 and candidates>=2 is that there can be a logical relationship between two candidates that is IFF even though there are more than two candidates. For example:

Code: Select all
[12][23][13]|[12345]


Because of the naked triple in r1c123, r1c1=2=r1c2=3=r1c3=1=r1c1.

Of course, you could take a first step of removing candidates 1, 2 and 3 from r1c4 based on the naked triple -- but you don't have to. The IFF relationship and the strong links already exists. If it were defined based in the number of candidates, the links would have to be considered a weak until after the simplification.

Then there more complex links:

Here is a xy-ring:

Code: Select all
 12    .    .  |  .    .   23
  .    .    .  |  .    .    . 
 14    .    .  |  .    .   34
---------------+---------------

[12]-2-[23]-3-[34]-4-[14]-1-[12]


These are all weak links -- until this ring is recognized. At that point, they can all be considered strong links before making any exclusions it allows. In fact, the exclusions are made BECAUSE these are strong links -- NOT the other way around! Same thing in an x-wing -- as soon as you see the pattern, you can mark all four edges as strong links -- and then make exclusions.

The situation is clearer if you allow links between groups of candidates:
Code: Select all
 12    .    .  |  .    .   234
  .    .    .  | 34    .    . 
 15    .    .  |  .    .   345
---------------+---------------
  .    .    .  |  .    .   34
  .    .    .  |  .    .   346


[12]-2-[234]-34-[34]-34-[345]-5-[15]-1-[12]

All these weak links can be used as stong links once this pattern is noted. There is a strong link between [234]=34=[345], as exactly one of them can be reduced to [34] allowing the exclusion r5c6<>[34] -- yet there are 3 of each candidate 3 and 4 in the 6th column, even after the exclusion, showing that in these situations, weak vs strong MUST be defined based on IFF rather than number of candidates=2.


Jeff:
The definition "Strong link - if A is false, then B is true" is not accurate, as it allows both A and B to be true at once.

Also
'Strong link' is currently accepted to imply
"if 'A is false, then B is true' or 'if A is true then B is false'." should be:
"if 'A is false, then B is true' AND 'if A is true then B is false'." or simply "A iff NOT B"
Last edited by tso on Sun Jan 15, 2006 1:34 pm, edited 1 time in total.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Jeff » Sun Jan 15, 2006 1:31 am

Jeff wrote:'Strong link' represents if 'A is false, then B is true' or 'if A is true then B is false'.
Link - if A is true, then B is false

Myth Jellies wrote:Strong Link: A = not B (same as B = not A; same as if A then (not B) AND if (not A) then B).
Nominal Link: if A then not B (same as if A true then B false, along with its contrapositive, if B true then A false).

I'm thinking that my definition of a link is not the same as yours, if this does not correspond to your strong and weak links.

Tso wrote:'Strong link' is currently accepted to imply
"if 'A is false, then B is true' AND 'if A is true then B is false'." or simply "A iff NOT B"

Hi MJ & Tso, You are right. Sorry that I have confused everyone!:(

When I wrote my link inferences, I was thinking in line with the uni-directional flow of an implication stream from left to right.

For example:

r5c5<>6 => r3c5=6 => r3c5<>5 => r3c8=5 => r2c9<>5 => r5c9=5 => r5c7<>5 => r5c7=7 => r6c8<>7

"r5c5<>6 => r3c5=6" is a strong-link; it implies if r5c5<>6, then r3c5=6.
"r3c5=6 => r3c5<>5" could be a strong-node or just-a-node; it implies if r3c5=6, then r3c5<>5.
"r3c5<>5 => r3c8=5" is a strong-link; it implies if r3c5<>5, then r3c8=5 .
"r3c8=5 => r2c9<>5" could be a strong-link or a just-a-link; it implies if r3c8=5, then r2c9<>5.
"r2c9<>5 => r5c9=5" is a strong-link; it implies if r2c9<>5, then r5c9=5.
"r5c9=5 => r5c7<>5" could be a strong-link or a just-a-link; it implies if r5c9=5, then r5c7<>5.
"r5c7<>5 => r5c7=7" is a strong-node; it implies if r5c7<>5 => r5c7=7.
"r5c7=7 => r6c8<>7" could be a strong-link or a just-a-link; it implies if r5c7=7, then r6c8<>7.

Now, can you see what I meant by:

    Strong-link - if "A is false, then B is true" or "if A is true or B is false", and
    Link - "if A is true, then B is false", as applied from left to right in a implication stream.
I totally agree with your definitions of these links when they are considered in isolation, in which case a strong link means "A is false, then B is true" AND "if A is true or B is false".:D
Last edited by Jeff on Sun Jan 15, 2006 12:26 am, edited 3 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sun Jan 15, 2006 1:53 am

Myth Jellies wrote:Strong Link: ........In a bivalue cell containing only candidates x and y, candidate x is strongly linked to candidate y.

Nominal Link: ..........or any two candidates within a multi-candidate cell.

Hi MJ,

Is it possible to use other existing terms to express links between candidates within a cell just to make things crystal clear? The following terms are currently in use.

Strong Node - a bivalue cell containing only candidates x and y; it implies "if x is false, then y is true" or "if x is true, then y is false" as applied from left to right in a implication stream.

Weak Node - a polyvalue cell containing 2 candidates or more: {x,y,z.......}; it implies "if x is true, then y is false" as applied from left to right in a implication stream. Since a weak node could be ambiguous similar to a weak link, we could adopt the same concept and just call it Node.
Last edited by Jeff on Sun Jan 15, 2006 12:28 am, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sun Jan 15, 2006 2:17 am

It seems to me the following option is the most popular so I would like to pursue it further.

    Link - number of nodes in the unit >= 2
    Strong Link - number of nodes in the unit exactly = 2
Any suggestion on how to make the definition 'link' to be recognisable as a definition?

For example:
Combination Chain is a chain with mixed strong links and links.

Does 'links' at the end look like a definition to you?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sun Jan 15, 2006 4:23 am

Jeff wrote:Any suggestion on how to make the definition 'link' to be recognisable as a definition?

For example:
Combination Chain is a chain with mixed strong links and links.

Perhaps the answer to this question is to avoid using links to specify a particular condition, but use "strong inference" and "weak inference" defined as follows:

    Strong Inference - if A is false, then B is true.
    Weak Inference - if A is true, then B is false.
As such, some statements could read:

A Combination Chain is a chain with links that make both strong and weak inferences to yield a deduction.
A Pure Bivalue Chain is a chain with links that make weak inferences only to yield a deduction.
A Pure Bilocation Chain is a chain with links that make strong inferences only to yield a deduction.
xy-chain is a chain with links that make weak inferences only to yield a deduction.
Jeff
 
Posts: 708
Joined: 01 August 2005

PreviousNext

Return to Advanced solving techniques