Forcing chains: Terminology and Definition

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Sun Jan 15, 2006 5:34 am

Jeff wrote:
    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 Pure Bivalue Chain is a chain with links that make weak inferences only to yield a deduction.

If we have only the two weak inferences ...

if A is true, then B is false, and
if B is true, then C is false

... how then do we propagate inferences from A to C?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Sun Jan 15, 2006 6:24 am

ronk wrote:A Pure Bivalue Chain is a chain with links that make weak inferences only to yield a deduction.

If we have only the two weak inferences ...

if A is true, then B is false, and
if B is true, then C is false

... how then do we propagate inferences from A to C?

Hi Ronk, Link is a defined term. The 2 weak inferences are for links only as stated in the statement, therefore the 2 inferences should be expressed as:

if X is true, then Y is false, and
if X is true, then Y is false

Candidate relationship within a node is a type of link but the word 'link' is not used to describe it in order to avoid confusion. If a node is strongly linked, then this node is called a "strong node", otherwise, just "node", similar to "strong link" and 'link' respectively.

There is no need to specify node inference in this statement because the title "Bivalue" is more than sufficient to describe this condition. However, the statement could be modified to include node inferences as follows:

A Pure Bivalue Chain is a chain with nodes that made strong inferences and links that make weak inferences only to yield a deduction.

Note: The definitions of strong and weak inferences for nodes are the same as those for links.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby tso » Sun Jan 15, 2006 6:41 am

Nothing to add here except I'm glad Jeff started this thread. Minor (and mostly) semantic and syntactic quibbles aside, it explains a lot that I had been confused about.

I worry that there isn't any easy way to archive all this information. This forum has already been hacked at least once. Plus Wayne has the domain on the auction block.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Myth Jellies » Sun Jan 15, 2006 6:50 am

Point 1

Jeff wrote: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.

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....


Of course you can do this, but there may be a distinct advantage in the inclusion of strong links between candidates. It certainly cannot have escaped your notice that in the following type of xy-loop between bivalue cells,

[rNcM]-b-[]-c-[]-d-[]-a-[rNcM]

you can make the same kind of sweeping eliminations in rows, columns, and boxes that you can when you have an x-cycle such as

[rNcM]-a-[]=a=[]-a-[]=a=[rNcM]

The reason you can make those same type of eliminations is because each cell in the above xy-loop contains a strong link which makes both examples I have given effectively equivalent to each other (alternating strong and nominal links). Perhaps history is against me, but I'd like to see a nomenclature and symbology that highlights that equivalence rather than hides it.

Point 2

I don't care about link vs nominal link. Based on dictionary definitions, you can probably use them both in the same post, and no one would be confused. We do have another link type, though. It is an inverse link (thanks for looking up those definitions, Ronk). An inverse link has the property

if A false then B true

Examples of this include the bug avoidance candidates of a BUG+2 grid and also the c and d candidates in the following AUR.

Code: Select all
.  .  ab | abc .  .
.  .  abd| ab  .  .


I can bet these are useful links, but they aren't nominal links.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

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

tso wrote:I worry that there isn't any easy way to archive all this information. This forum has already been hacked at least once. Plus Wayne has the domain on the auction block.

Hi Tso, Everyone can save a copy of this thread in his/er own PC and update it from time to time.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sun Jan 15, 2006 6:58 am

Myth Jellies wrote:.......... but there may be a distinct advantage in the inclusion of strong links between candidates.

Hi MJ, First post updated to include "Strong Node' and "Node" which will be useful.

I am going to add "Strong Inference" and "Weak Inference" later.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Scott H » Sun Jan 15, 2006 7:38 am

Some comments on this interesting thread:

1. Link usage, not intrinsic link type (if there is such a thng of any relevance), is what matters in a sudoku inference. So standard terminology should reference link usage.

2. An inference "candidate A implies not candidate B" is the standard weak link (or link, nominal link, weak inference, or whatever you call it). For this inference it doesn't matter whether or not there are other candidates C for which "candidate A implies not candidate C", and you might not even know if there are other such C. So "weak link" should refer to this logical relation between two or more candidates. The "or more" doesn't matter, and has no business affecting the name.

3. It is desirable to choose terminology that will also extend to forcing nets. In forcing nets you can have either "strong" or "weak" relations among N candidates for N>2. A "strong" relation among N candidates asserts that "exactly one of the candidates is true" (the generalization from forcing chains is "exactly one", not XOR). A "weak" relation among N candidates asserts "at most one of the candidates is true" (generalizing from chains is "at most one", not OR).

A strong relation among N candidates must include all the relevant candidates in the unit or in the cell, and you can deduce truth of one candidate from the falsity of the other N-1. A weak relation works with a subset of candidates in a unit or cell, and can deduce falsity of others from truth of one, but not vice versa.
Scott H
 
Posts: 73
Joined: 28 July 2005

Postby Jeff » Sun Jan 15, 2006 9:36 am

Thanks for the advices Scott. For those who may be interested, Scott is the lord of logic who introduced "nice loops" to this forum.

I think, towards the end of the 'strong' and 'weak' discussions, we concluded a system which basically covers all your good points and most importantly, all terms and definitions are unambiguous.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sun Jan 15, 2006 12:03 pm

Jeff wrote:There is no need to specify node inference in this statement because the title "Bivalue" is more than sufficient to describe this condition. However, the statement could be modified to include node inferences as follows:

A Pure Bivalue Chain is a chain with nodes that made strong inferences and links that make weak inferences only to yield a deduction.

That modified statement is much improved IMO, but the word 'only' should either be used with both inferences or neither. I vote both.

Jeff wrote:
ronk wrote:if A is true, then B is false, and
if B is true, then C is false

The 2 weak inferences are for links only as stated in the statement, therefore the 2 inferences should be expressed as:

if X is true, then Y is false, and
if X is true, then Y is false (ronk edit: should be 'if Y is true, then X is false)

:?:Where did that come from? A, B, C ...., X, Y are just placeholders ... for r2c1=4 and r2c5=4, for example. How are your placeholder letters any more appropriate than mine?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Sun Jan 15, 2006 12:59 pm

Post cancelled
Last edited by Jeff on Sun Jan 15, 2006 9:26 am, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sun Jan 15, 2006 1:24 pm

ronk wrote:........but the word 'only' should either be used with both inferences or neither. I vote both.

Hi Ronk, Good point. The 'only' is applicable to both strong node inference and weak link inference. But, I shall fix that to make it crystal clear. Thanks.

ronk wrote:if A is true, then B is false, and
if B is true, then C is false
Jeff wrote:if X is true, then Y is false, and
if X is true, then Y is false (ronk edit: should be 'if Y is true, then X is false)

:?:Where did that come from? A, B, C ...., X, Y are just placeholders ... for r2c1=4 and r2c5=4, for example. How are your placeholder letters any more appropriate than mine?

There is no placeholder, Ronk. X & Y are unknowns for each individual link where X is the end-node upstream and Y is the end-node downstream. A weak inference implies that the upstream node contains the link label and the downstream-node does not.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sun Jan 15, 2006 1:25 pm

Jeff wrote:There is no placeholder, Ronk. X & Y are unknowns for each individual link where X is the end-node upstream and Y is the end-node downstream. A weak inference implies that the upstream node contains the link label and the downstream-node does not.

One more thing, Ronk. Do you know why I don't need a placeholder? That's because I have the link label which is equivalent to the placeholder. Nevertheless, you still can interpret the inference with placeholders, as long as you take the strong nodes into account. Thus,

If A is true, then B is false -- weak link inference
If B is false, then C is true-- strong node inference
If C is true, then D is false -- weak link inference
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Forcing chains: Terminology and Definition

Postby ronk » Sun Jan 15, 2006 3:26 pm

Jeff wrote:Strong Node - a node with n cells containing n+1 candidates. Each strong node has a strong inference as well as a weak inference that implies "if a candidate is false, then the rest are true" and "if a candidate is true, then the rest are false" respectively; along the flow of an implication stream. A bivalue cell and an almost locked set are examples of a strong node.

I suggest saying for a multivalued cell ...

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

"if one candidate is true, then the remaining (candidates) must be false"
... with use of the parenthesized 'candidates' optional, depending upon how unambiguous you wish to be.

As for "A bivalue cell and an almost locked set are examples of a strong node":
  1. While both the strong inference and weak inference (as currently defined) are valid for a bivalue, only the strong inference is valid for the almost locked set
  2. The phrase "if a candidate is false, then one of the remaining (candidates) must be true" would necessarily be something like "if one candidate is removed from the set, then *all* of the remaining (candidates) must be true"
  3. The phrase "if one candidate is true, then the remaining (candidates) must be false" just doesn't apply because of 1 (above).
I also recommend using "multi-valued" for 2 or more candidates to (mostly) avoid confusion with "poly-valued" for 3 or more candidates as in the BUG principle.

Ron
Last edited by ronk on Sun Jan 15, 2006 2:18 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tso » Sun Jan 15, 2006 5:55 pm

Thinking it was the simplest way to put it, I had said:

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


Scott H said:

ALL links: "at most one of the candidates is true"
Strong Links: "exactly one of the candidates is true"

... which has the huge advantages of being in plain english and not being limited to pairs of candidates -- as well as opening the door to simple descriptions of exotic links should they ever be useful, such as "at most one must be false", "exactly two must be true", etc.
tso
 
Posts: 798
Joined: 22 June 2005

Re: Forcing chains: Terminology and Definition

Postby Jeff » Sun Jan 15, 2006 7:31 pm

Thanks Ronk, I do need more guidance from more guys like you.

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.

ronk wrote:"if one candidate is true, then the remaining (candidates) must be false"... with use of the parenthesized 'candidates' optional, depending upon how unambiguous you wish to be.

Done.

ronk wrote:The phrase "if a candidate is false, then one of the remaining (candidates) must be true" would necessarily be something like "if one candidate is removed from the set, then *all* of the remaining (candidates) must be true"

The strong inference of a "strong node":

if a candidate is false, then not just one of the remaining candidates must be true; in fact all the remaining candidates must be true. Consider the following node consisting of 3 cells with 4 candidates:

    [123][23][1234]
If 4 is false in this node, than the 3 cells will form a naked triple of 123. For 3 cells with 3 remaining candidates, they must be all true for this strong node.

ronk wrote:While both the strong inference and weak inference (as currently defined) are valid for a bivalue, only the strong inference is valid for the almost locked set.

The weak inference of:

    a "strong node" with 1 cell (bivalue cell)
    if a candidate is true, then the other candidate must be false.

    a "node" with 1 cell (multivalue cell)
    if a candidate is true, then all remaining candidates must be false.

    a "strong node" with n cell:
    if a candidate is true, then one of the remaining candidates must be false.

    a "node" with n cell:
    If a candidate is true, then at least one of the remaining candidates must be false
The intercept of the 4 cases above gives:
If a candidate is true, then at least one of the remaining candidates must be false. This definition will be updated accordingly.

ronk wrote:I also recommend using "multi-valued" for 2 or more candidates to (mostly) avoid confusion with "poly-valued" for 3 or more candidates as in the BUG principle.
Done.
Jeff
 
Posts: 708
Joined: 01 August 2005

PreviousNext

Return to Advanced solving techniques