Forcing chains: Terminology and Definition

Advanced methods and approaches for solving Sudoku puzzles

Re: Forcing chains: Terminology and Definition

Postby ronk » Mon Jan 16, 2006 12:53 am

Jeff wrote:
ronk wrote:I suggest saying for a multivalued cell ...

"if a candidate is false, then one of the remaining (candidates) must be true",

Firstly, a multivalued cell is just a "node" consisting of one cell. It is not a "strong node" and strong inference doesn't apply.

I was writing about a Node, but somehow cited Strong Node. I was obviously confused, so I'll start over.

Node - a cell or a group of 2 or more cells between 2 links in a chain propagation. A node is multi-valued, ie. it contains 2 candidates or more {a,b,c.......}. Each node has a weak inference that implies "If a candidate is true, then at least one of the remaining candidates must be false"; along the flow if(sic) an implication stream.

Firstly, make the opening statement)s) of Node and Strong Node read as much alike as possible so it's easy to spot the differences, e.g.,

Node - a node with n cells containing at least n+1 candidates.
Strong Node - a node with n cells containing exactly n+1 candidates.


Secondly, RE "If a candidate is true, then at least one of the remaining candidates must be false", I don't think any candidate becomes false (is eliminated) until n=0. I think the statement should read something like ...

"For each candidate set true within the set of n cells, n is decremented until n=0 at which point all remaining candidates must be false".

Somebody else really needs to cross-check that one though.

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

Re: Forcing chains: Terminology and Definition

Postby Jeff » Mon Jan 16, 2006 7:46 am

Good thinking, Ronk.

ronk wrote:Firstly, make the opening statement)s) of Node and Strong Node read as much alike as possible so it's easy to spot the differences, e.g.,

Node - a node with n cells containing at least n+1 candidates.
Strong Node - a node with n cells containing exactly n+1 candidates.

You are right; they should be alike. However, are you aware that a strong node is not necessarily limited to n cells with n+1 candidates? For example, a node having n+2 candidates can be a strong node with a strong inference that if 2 of its candidates (entering link label with 2 candidates) are false, then the remaining candidates are true. These possibilities may require the definition of "strong node" to be expanded. This is why I am not keen to use n and n+1 to define "node". Proposed revision as follows:

Node - a cell or a group of cells joining 2 links in a chain propagation. A node is multi-valued and may contain any number of candidates. Each node has a weak inference ..............

Strong Node - a node that has an additional strong inference that implies if a candidate or a group of candidates is false .............

ronk wrote:"If a candidate is true, then at least one of the remaining candidates must be false", I don't think any candidate becomes false (is eliminated) until n=0. I think the statement should read something like ...

"For each candidate set true within the set of n cells, n is decremented until n=0 at which point all remaining candidates must be false".

Your suggestion is very correct and precise. However, these precise descriptions are of academic interest because they are not required to propel a chain. In chain propagation, the status of the remaining candidates in a node is only important when it is a strong node and it is used to connect 2 links with weak inference. Consider the following examples:

=5=[x5xx]-5- (stronglink – node – link)
If 5 is true, the status of the remaining candidates is not important.

=5=[x57x]=7= (stronglink – node – stronglink)
If 5 is true, the status of the remaining candidates is not important, except that the node must contain 7 which is the pre-requisite for a link.

=4=[xx4][x4xx][xx4xx]-4- (stronglink – node – link)
If 4 is true, the status of the remaining candidates is not important.

=4=[xx4][x4xx][xx4xx]=x= (stronglink – node – stronglink)
If 4 is true, there will not be enough information to allow a strong link leaving the node to made a strong inference. It means a strong link cannot be established anyway; Therefore the status of the remaining candidates is again not important.

In conclusion, every “node” has a trivial weak inference that if a candidate set {a,b,c....} in the node is true, then at least one of the remaining candidates must be false; but this information is not important in terms of chain propagation.

As such, the definitions can be written as:

Node - a cell or a group of cells joining 2 links in a chain propagation. A node is multi-valued and may contain any number of candidates. Each node has a weak inference that implies a candidate or a group of candidates (labelled candidate(s) of the link entering the node) in the node is true; along the flow of an implication stream.

Strong Node - a node that has an addition strong inference that implies if a candidate or a group of candidates (labelled candidate(s) of the link entering the node) is false, then all remaining candidates are true; along the flow of an implication stream. A bivalue cell and an almost locked set are examples of a strong node.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Forcing chains: Terminology and Definition

Postby ronk » Mon Jan 16, 2006 10:48 am

Jeff wrote:For example, a node having n+2 candidates can be a strong node with a strong inference that if 2 of its candidates (entering link label with 2 candidates) are false, then the remaining candidates are true.

Jeff wrote:Each node has a weak inference that implies a candidate or a group of candidates (labelled candidate(s) of the link entering the node) in the node is true; along the flow of an implication stream.

Jeff wrote:Strong Node - a node that has an addition strong inference that implies if a candidate or a group of candidates (labelled candidate(s) of the link entering the node) is false, then all remaining candidates are true; along the flow of an implication stream. A bivalue cell and an almost locked set are examples of a strong node.

AFAIK label refers to the numbered ellipses and squares on a bivalue/bilocation (b/b) plot. I don't do b/b plots and have no intentions of doing so. Therefore most of your statements about labeling are lost on me ... and I suspect most others as well. That's why, at the outset of this thread, I objected to any references to b/b plots being included in the basic definitions.

However, if label also refers to candidates enumerated in a nice loop expression, then I would listen up. But that's probably a "chicken and egg" situation, where one wouldn't be generating(understanding) nice loops of that type unless one does(has done) b/b plotting.

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

Re: Forcing chains: Terminology and Definition

Postby Jeff » Mon Jan 16, 2006 11:40 am

ronk wrote:AFAIK label refers to the numbered ellipses and squares on a bivalue/bilocation (b/b) plot. I don't do b/b plots and have no intentions of doing so. Therefore most of your statements about labeling are lost on me ... and I suspect most others as well. That's why, at the outset of this thread, I objected to any references to b/b plots being included in the basic definitions.

However, if label also refers to candidates enumerated in a nice loop expression, then I would listen up. But that's probably a "chicken and egg" situation, where one wouldn't be generating(understanding) nice loops of that type unless one does(has done) b/b plotting.

I am really disappointed with you, Ronk. Knowing what you are like, that's exactly why I put “link label” in brackets as additional information. I made use of link labels in my response to you (having considered your analytical ability), to show and to explain the definitions of terms. That's how I think and how I am able to explain it. Link label need not be related to b/b plot; it is just the candidate connecting 2 nodes in a propagating chain. In other words, It is this link labelled candidate that defines the location of a link, similar to the 'placeholder' you mentioned earlier. How could you tell us that strong links and weak links were well established in your mind if you don't know how a link is defined? If you can't understand that, you would have to prove me wrong some time in the future.:(

Although I haven't yet included b/b plot and nice loop in the terminology and definition list, I can't really understand why you would object to any references to b/b plots being included in the definitions. IMO, b/b plot is one of the 2 current human executable techniques that can identify forcing chain deductions without T&E. Why shouldn't it go onto the list? Who said that the definitions have to be basic and what basic stands for? And, you have reprimanded me for not being open minded?:(

B/b plots and nice loops go hand in hand. Without b/b plot, nice loops will just be a T&E mess. You have been using link labels in nice loop notations without probably knowing it; how sad can that be? The following example was extracted from one of your posts from the other thread:

ronk wrote:I got this far ...
Code: Select all
  468  5    468  | 346  2    1    | 7    9    348   
  2    7    69   | 69   348  348  | 34   5    1     
  1    3    489  | 49   5    7    | 48   2    6     
 ----------------+----------------+----------------
  349  6    7    | 1    34   349  | 5    8    2     
  5    49   2    | 8    7    349  | 1    6    34   
  34   8    1    | 2    6    5    | 9    34   7     
 ----------------+----------------+----------------
  469  49   5    | 34   1    2    | 3468 7    348   
  7    2    346  | 5    348  348  | 346  1    9     
  48   1    348  | 7    9    6    | 2    34   5     


-[r7c4]-4-[r8c5|r8c6]=4=[r2c5|r2c6]-4-[r2c7]-3-[r2c5|r2c6]=3=[r8c5|r8c6]-3-[r7c4]-

... although I'm unsure of the left and right ends.

Well, the matter of the fact is that no one should be forced to do anything that he/she doesn't want to. But, you are using nice loops that originated from b/b plot and yet not showing any respect at all. I am feeling very sorry that I have wasted so much time trying to explain things to you. Am I obliged to answer your questions without any references to b/b plot, nice loops and all their related terms?:(
Last edited by Jeff on Thu Jan 19, 2006 4:32 am, edited 6 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Forcing chains: Terminology and Definition

Postby ronk » Mon Jan 16, 2006 1:38 pm

Jeff wrote:... that's exactly why I put “link label” in brackets as additional information.
Noted and appreciated.

I made use of link labels in my response to you (having considered your analytical ability), to show and to explain the definitions of terms.
...
I am feeling very sorry that I have wasted so much time trying to explain things to you.
I politely stated that I don't do b/b plots, so that in your future responses to me, you wouldn't continue to waste your time. Would you rather I pretended I did b/b plots, so that you would waste your time? BTW you're not the only one who feels like they're "wasting their time", at least part of the time.:)

Although I haven't yet included b/b plot and nice loop in the terminology and definition list, I can't really understand why you would object to any references to b/b plots being included in the definitions. IMO, b/b plot is one of the 2 current human executable techniques that can identify forcing chain deductions without T&E.
.................
B/b plots and nice loops go hand in hand. Without b/b plot, nice loops will just be a T&E mess. You have been using link labels in nice loop notations without probably knowing it; how sad can that be?
I disagree, as I think of nice loops as shorthand for double implication chains. And all one really needs to know to convert to nice loops for the simple deductions of double implication chains, is that

[r1c1]=3=[r1c7] means r1c1<>3 implies r1c7=3, and

[r1c1]-3-[r1c7] means r1c1=3 implies r1c7<>3.

Oh, there's other details like: the discontinuity node is at the ends of the nice loop; implication streams are valid for both left and right directions; and others that I've forgotten or already take for granted.

None of the immediate above requires digging out paper and pencil to draw links on a grid, which is my primary objection to b/b plotting. However, if someone comes out with a solver with user-friendly b/b plots as a manual solution tool, my viewpoint would likely change.

Am I obliged to answer your questions without any references to b/b plot, nice loops and all their related terms?:(
The question to which you referred was directed to Carcul.

Why shouldn't it go onto the list? Who said that the definitions have to be basic and what basic stands for? And, you have reprimanded me for not being open minded?:(
Have you ever enumerated the people who currently post nice loops in this forum? There's you (lots of loops), Carcul (lots of loops), me (you can count 'em on two hands, maybe even one), err, err ... gee, I can't think of anyone else. That's not saying there aren't other people who use b/b plots, as I'm sure there are. But the low count of people posting nice loops here suggests to me the count of people using b/b plots is also quite low.

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

Postby Jeff » Thu Jan 19, 2006 11:43 am

The terms "Bilocation/Bivalue Plot" and "Nice Loop" have been added to the list.

Please advise if any more terms should be added.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sun Jan 22, 2006 6:21 am

Here:
Jeff wrote:In the forcing chain definition, conjugate node is one type of "strong nodes" that means bivalue cell. It is desirable not to create definitions in colouring that would confuse with those in forcing chains.

(Aside: The word 'conjugate' is actually no longer even in the first post of this thread.)

Just like 'bilocation' implies conjugate locations, 'bivalue' implies conjugate values ... not 'conjugate nodes'. And 'conjugate pairs' has become more ambiguous IMO, because it could be either pairs of values or locations or, I guess now, groups of locations.

Given the definition of 'Node' on this thread, I can't see a logical parallel between 'conjugate locations', 'conjugate values', and 'conjugate nodes'. Do we say conjugate row/col/box just because that row/col/box has exactly two candidates of the same value? To my knowledge, the answer is "no".

So why propose using the term 'conjugate node' just because we have a node with exactly two candidates of different values? It's just not a logical parallel IMO ... and usurps the term from possible future, but presently unknown, usage.

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

Postby Jeff » Sun Jan 22, 2006 6:51 am

ronk wrote:So why propose using the term 'conjugate node' just because we have a node with exactly two candidates of different values?

Hi Ronk, points taken. Perhaps I should have made it clear that one of the meanings of "conjugate node" is conjugate bivalue cell. I agree that "conjugate node" can also mean conjugate bilocation link. I interpret "conjugate node" as a collective term which is okay to be used in general sense. When it comes to colouring definition, however, it is desirable to use something which has a more specific meaning.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Mon Jan 23, 2006 4:56 pm

New term "Backtest" added to first post.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Jan 27, 2006 3:24 am

I would like to add the following definition to the first post. Please advise if anything I need to know.

Single Implication network - An open path that has one implication stream that starts with a candidate selected in one node and propagates until a contradiction is revealed, eg. one digit appears 2 times in a unit. This is the principle of a "backtest" (Refer definition of a backtest below). There is currently no known technique for non-T&E identification of such an open path.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Fri Jan 27, 2006 4:09 am

Jeff wrote:Single Implication network - An open path that has one implication stream that starts with a candidate selected in one node and propagates until a contradiction is revealed, eg. one digit appears 2 times in a unit.

How can one implication stream imply two instances of the same digit?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Fri Jan 27, 2006 4:34 am

How can one implication stream imply two instances of the same digit?


If one of the instances existed prior to starting the implication stream.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Fri Jan 27, 2006 4:57 am

Myth Jellies wrote:
How can one implication stream imply two instances of the same digit?


If one of the instances existed prior to starting the implication stream.

In the context of backtesting, I think both digits will occur when placing a digit that would be validly eliminated by a technique. Take a look at my simple x-wing example here. Neither of the 8s and neither of the 5s existed before the backtest.

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

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

Should the wording of the definition be adjusted?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Fri Jan 27, 2006 5:27 pm

Jeff wrote:
ronk wrote:
Jeff wrote:Single Implication network - An open path that has one implication stream that starts with a candidate selected in one node and propagates until a contradiction is revealed, eg. one digit appears 2 times in a unit.

How can one implication stream imply two instances of the same digit?

Should the wording of the definition be adjusted?


I suggest the following:

Implication Network - A network with multi-implication streams that start with a selected candidate in one node and propagate until two implication streams reveal a contradiction in other nodes, e.g., the same digit appearing twice in a unit.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques