Forcing chains: Terminology and Definition

Advanced methods and approaches for solving Sudoku puzzles

Postby Jeff » Sun Jan 29, 2006 2:23 am

Thanks MJ for the comments.:D Most of these comments are related to B/B plot and I have no problem to incorporate them. However, it would be difficult not to give an impression that the definition list is just another description of B/B plot and nice loops. At the moment, people can find all B/B plot related terms under the thread bilocation/bivalue plot & nice loops: description. Could anyone give me more advices?

Myth Jellies wrote:3. A little explanation of how a continuous cycle can be cut between each of their nominal links to form a different discontinuous path, hence all of the potential deletions; might be nice.

I don't quite understand this one.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Sun Jan 29, 2006 6:20 am

Jeff wrote:Thanks MJ for the comments.:D Most of these comments are related to B/B plot and I have no problem to incorporate them. However, it would be difficult not to give an impression that the definition list is just another description of B/B plot and nice loops.


I just think that if you are going to use terms like "discontinuity" and "nice loop rules", you might as well include a definition for them...or at least make the term a link to where they are defined. The cells and strong/nominal link symbology seems to be included in practically every post on this subject, including this one, so I don't think it is exclusively related to B/B plots.

Jeff wrote:
Myth Jellies wrote:3. A little explanation of how a continuous cycle can be cut between each of their nominal links to form a different discontinuous path, hence all of the potential deletions; might be nice.

I don't quite understand this one.


It might be a little goofiness on my part. Consider a simple continuous cycle, an xy-ring.

[r3c3] - 1 - [r3c4] - 2 - [r4c4] - 3 - [r4c3] - 4 - [r3c3] ([r3ci] <> 1, [rjc4] <> 2, [r4cm] <> 3, [rnc3] <> 4)

You can disconnect this at each of the nominal links to get

[r3ci] - 1 - [r3c4] - 2 - [r4c4] - 3 - [r4c3] - 4 - [r3c3] - 1 - [r3ci] ([r3ci] <> 1)
[rjc4] - 2 - [r4c4] - 3 - [r4c3] - 4 - [r3c3] - 1 - [r3c4] - 2 - [rjc4] ([rjc4] <> 2)
[r4cm] - 3 - [r4c3] - 4 - [r3c3] - 1 - [r3c4] - 2 - [r4c4] - 3 - [r4cm] ([r4cm] <> 3)
[rnc3] - 4 - [r3c3] - 1 - [r3c4] - 2 - [r4c4] - 3 - [r4c3] - 4 - [rnc3] ([rnc3] <> 4)

Thus, to some extent, continuous cycles are just a composite of discontinuous paths.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Mon Jan 30, 2006 5:42 am

Definition for Single Implication Network added to the first post.
Definition for Forcing Net also adjusted to suit.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Feb 09, 2006 10:42 am

Hi MJ, I haven't forgotten your post, but need more time to observe the reaction from the majority.:D

Myth Jellies wrote:You explain how strong links and links look on your B/B plots, but there is nothing about how they are represented by '=' and '-' in the typical symbology.

I can see that the symbols '=x=' and '-x-' are gradually accepted, not only for nice loop, but in a general sense to represent 'strong inference' and 'weak inference', I will added them to the first post.

Myth Jellies wrote:Nice loop refers to "nice loop propagation rules in accordance with the fundamentals of forcing chains." As far as I can tell, neither these rules nor these fundamentals have been explicitly defined.

I would like to ask this question: Would anyone wish the nice loop propagation rules to be included to the definition list? Please give me some indications.

Myth Jellies wrote:A little explanation of how a continuous cycle can be cut between each of their nominal links to form a different discontinuous path, hence all of the potential deletions; might be nice.

I see no harm to explain how a continuous cycle can be broken up into a number of discontinuous paths. Would you have any suggestion of wordings?

Myth Jellies wrote:Discontinuous Path refers to a "discontinuity" which has not been defined. Also, some explanation for why a Discontinuous Path is synonymous with the opposite sounding Repetitive Path might be in order.

Continuity is related to the nice loop propagation rules. Let’s consider this in a later stage.

Myth Jellies wrote:I would expect to find in this post, an explanation of all the preferred symbology used in most representations of forcing chains. When the chains start encompassing multiple streams and groups, their symbolic representation can be almost unfathomable.

Totally agree. To my knowledge, nice loop notation symbols can express multiple inferences and grouped inferences quite well. Do anyone has any objection for me to include these notations in the first post? Please express your opinion.

Myth Jellies wrote:I would hope to find a little more exposition on why this alternating strong (link/node) - link combination works and is required for some of these definitions. It just seems to be mentioned in passing, and it appears to be the backbone for a lot of what you are doing.

Could you explain this one a bit more please?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Feb 24, 2006 1:39 pm

Descriptions for 'strong inference' and 'weak inference' updated and notation symbols =x= and -x- explained in first post.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sat Feb 25, 2006 6:39 am

Jeff wrote:Strong Inference
..................
As applied to nodes, strong inference strictly implies "if a candidate or a group of candidates in a node is false, then the rest of the candidates in the node is true".


"The rest of" implies two or more can be true simultaneously, which is impossible. "One of the remaining" would be better.

Also, if that's meant to apply to multi-celled node for a single digit, it's a false statement. For example, if one node of a conjugate pair is multi-celled, then the two possibilities for that multi-celled node are:
  1. Exactly one of the candidates is true, or
  2. all of the candidates are false.
Overall, I think trying try to make one definition apply to both multiple candidates in a single cell and to multiple cells for a single digit is too confusing, even if possible. But maybe that's not what you're currently trying to to.

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

Postby Jeff » Sat Feb 25, 2006 8:16 am

Jeff wrote:Strong Inference
..................
As applied to nodes, strong inference strictly implies "if a candidate or a group of candidates in a node is/are false, then the rest of the candidates in the node is/are true".

Hi Ronk.

"The rest of" implies one or more can be true simultaneously; consider the following examples:

    Node = [r1c1] containing candidates {4,5}
    This is a strong node when r1c1<>4, then r1c1=5

    Node = [r1c123] containing a lockedset+1 of {4,5,6,7}
    This is a strong node when r1c123<>4, then r1c123={5,6,7}

    Node = [r1c1] containing condidates {4,5,6}
    This is a strong node when r1c1<>{4,5}, then r1c1=6

    Node = [r1c12] containing a lockedset+2 of {4,5,6,7}
    This is a strong node when r1c12<>{4,5}, then r1c12={6,7}
This is what I meant to say in the statement. Please advise further comments.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sat Feb 25, 2006 12:23 pm

Jeff wrote:
Jeff wrote:Strong Inference
..................
As applied to nodes, strong inference strictly implies "if a candidate or a group of candidates in a node is/are false, then the rest of the candidates in the node is/are true".

Node = [r1c1] containing candidates {4,5}
This is a strong node when r1c1<>4, then r1c1=5

Node = [r1c123] containing a lockedset+1 of {4,5,6,7}
This is a strong node when r1c123<>4, then r1c123={5,6,7}
...........................
This is what I meant to say in the statement. Please advise further comments.

Your illustrations above definitely clarify the text description. Suggest you add them to the OP.

However, that still leaves me wondering about grouped candidates for a single digit. Are you not applying the term 'node' there also? I think most people will, even if you don't, and the definition just doesn't fit that scenario.

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

Postby Jeff » Sat Feb 25, 2006 1:10 pm

ronk wrote:Suggest you add them to the OP.

Done.

ronk wrote:However, that still leaves me wondering about grouped candidates for a single digit. Are you not applying the term 'node' there also? I think most people will, even if you don't, and the definition just doesn't fit that scenario.

I supposed you are referring to grouped x-cycle nodes for a single digit. These nodes should not be restricted to strong nodes; they are just "nodes" as they only need weak inference to propagate.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sat Feb 25, 2006 4:55 pm

Jeff wrote:I supposed you are referring to grouped x-cycle nodes for a single digit.

Yes, and I was confusing the strong inference of a strong link with that of a strong node. Link ... node ... link ... node ... link ... node ...
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Mon Feb 27, 2006 5:50 am

Single Implication Network - a network that has one implication stream that starts with a candidate selected in one node and propagates with or without multiple inferences until a contradiction is revealed (eg. empty cell, one digit appears 2 times in a unit or no place for a digit in a unit), thus concluding the candidate selected at the start is invalid. This is also the principle of a "backtest" (Refer definition of a backtest below).

I propose to adjust the above description as follow. Please advise your comments.

Error Net - a single implication network with one implication stream that starts with a candidate selected in one node and propagates with or without multiple inferences until a contradiction is revealed. Due to this contradiction, such as 'empty cell', 'one digit appears 2 times in a unit' and 'no place for a digit in a unit', it can be concluded that the candidate selected at the start is invalid. This is also the principle of a "backtest" (Refer definition of a backtest below).
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Mon Feb 27, 2006 11:43 am

Links, Strong Links, Weak Links, and ???

I'm still not happy with the link definitions. I'm referring to the absence of a link type ... as well as their formal names.

The addition of inferences -- Strong Inference and Weak Inference -- was a big improvement and certainly helped clear things up. It was the 'usage' part of what I referred to as making a distinction between 'type' and 'usage' during our earlier discussion on this thread. But 'type' definitions still leave something to be desired.

Other than the trivial case of "no inferences", there are three cases -- "combinations" of Strong Inference and Weak Inference -- and IMO a different link type should be associated with each of those cases. Rather obviously, the three cases are:
  1. a link with both Strong and Weak Inferences
  2. a link with only a Weak Inference
  3. a link with only a Strong Inference
As I see it, we have Names for the first two -- Strong Link and Link, respectively -- but none for the last.

Now "Link" stinks (rhyme intended) anyway because 1) without an adjective it just doesn't sound like a definition, 2) one can't tell if that's what was intended or if the adjective was accidentally omitted, and 3) it leaves no way to discuss links generically without resorting to an 'l' vs 'L' case distinction. Therefore, I propose the following name assignments:
  1. Conjugate Link <--> a link with both Strong and Weak Inferences
  2. Weak Link <--> a link with only a Weak Inference
  3. Strong Link <--> a link with only a Strong Inference
Ron

P.S. The 'Error Net' definition looks fine.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Mon Feb 27, 2006 12:45 pm

Hi Ronk, thanks for the comments.

Can you give an example of a link that can only have a strong inference? Reason for my asking is that it seems to me that a link with a strong inference will always have a weak inference.

If we could define unanimously 'Weak Link' as a link with only a 'Weak Inference' and Strong Link' as a link with only a 'Strong Inference', the terms 'Strong Inference' and 'Weak Inference' wouldn't need to be introduced in the first place.

Without any ambiguity, a 'Strong Link' has been commonly agreed as a conjugate link with both strong inference and weak inference. I think it should remain that way, in order not to cause any new form of confusion.

Without any ambiguity, a 'Weak Link' has been commonly agreed as a link with weak inference only. The argument was whether weak links should include strong links which also have weak inferences. Furthermore, if weak links does include strong links, then why demarcate them as weak links; thus, the term ‘Link’ was born.

Nowadays, people basically use the terms 'strong link' and 'weak link' as simple English and their interpretation have to read in conjunction with the context. This makes it even harder to define, don't you think?

Currently, people have the following choices:

Strong Link => both strong inference and weak inference
Strong Inference => strictly strong inference only
Weak Inference => strictly weak inference only
Weak Link => definitely weak inference and it may or may not have a strong inference also

The last one is the only problem. This problem can be avoided but can't be fixed since it is just simple English.

I agree that the term ‘link’ without an adjective is quite annoying. Why don’t you call it a weak link in general sense and use the term ‘a link of weak inference’ when the description is required to be very specific.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby vidarino » Mon Feb 27, 2006 1:16 pm

Jeff wrote:Can you give an example of a link that can only have a strong inference? Reason for my asking is that it seems to me that a link with a strong inference will always have a weak inference.


"Normal" strong links can - as far as I can see - always have a weak inference as well, but links that utilize e.g. Almost Unique Rectangles and similar structures might not.

Code: Select all
      6      3      1 |     459    459     89 |     478    479      2
      9      7      4 |     136      2   1368 |     358     15     35
      5      2      8 |       7    349    139 |      34    149      6
----------------------+-----------------------+----------------------
      1      5    379 |      39      8      4 |       2      6     37
      2      8    379 |     359      6    379 |     345     45      1
      4      6     37 |      12    357     12 |       9      8    357
----------------------+-----------------------+----------------------
      7      9      2 |       8      1      5 |       6      3      4
      8      1      6 |     234     34     23 |      57     57      9
      3      4      5 |      69     79    679 |       1      2      8


Note the Almost Unique Rectangle in R46C39.

The link R6C9=5|9=R4C3 only has a strong inference. (Elimination of one forces the other, but the presence of one does not eliminate the other.)

Vidar

(Edit: less ambiguous inference description.)
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Jeff » Mon Feb 27, 2006 1:48 pm

vidarino wrote:Note the Almost Unique Rectangle in R46C39.

The link R6C9=5|9=R4C3 only has a strong inference. (Elimination of one forces the other, but the presence of one does not eliminate the other.)

Hi Vida, good point.

Strictly speaking, this is not a link. The almost unique rectangle is really a node, a node with a strong inference only. This node consists of 4 cells acting like a bivalue cell. A better notation for inferences concerning this node would be:

-5-[AUR(37):R46C39]-9-

which is in line with other almost patterns such as an almost swordfish.:D
Last edited by Jeff on Mon Feb 27, 2006 10:03 am, edited 2 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

PreviousNext

Return to Advanced solving techniques