Forcing chains: Terminology and Definition

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Mon Feb 27, 2006 1:54 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.

One example from uniqueness:
vidarino wrote:Consider this grid, with a type 5 UR in R14C12.
Code: Select all
     13*   135*     8 |      15     27     67 |       9     46    246
     12      6      4 |      18      3      9 |       5      7     28
      9     57     27 |     568    268      4 |       1      3    268
----------------------+-----------------------+----------------------
    135*    13*     9 |      68     68      2 |       7     45     34
    567      8     67 |       4      1      3 |       2     56      9
      4      2     36 |       7      9      5 |       8      1     36
----------------------+-----------------------+----------------------
   3678     37   1367 |       9     67     18 |       4      2      5
     28      4     12 |       3      5     18 |       6      9      7
     67      9      5 |       2      4     67 |       3      8      1


Now, since one of the 5s in the UR must be true, they can be considered as forming a strong link between their respective corners.

According to current definitions, there exists the Strong Inference "if r4c2<>5 then r1c2=5" and v.v., but there is no Strong Link since "if r4c2=5 then r1c2<>5" is not also true.

One example from almost-locked-sets:
bennys wrote:
Code: Select all
 +-------------+-------------+-------------+
 | 24  7   8   | 24  6   5   | 1   9   3   |
 | 9   3   24  | 248 1   48  | 56  7   56  |
 | 5   1   6   | 7   3   9   | 8   4   2   |
 +-------------+-------------+-------------+
 | 28  9   23  | 458 7   6   |#35  1  #45  |
 |*17  6   5   | 3   9   14  | 2   8  #47  |
 | 178 4  *13  | 58  2   18  | 357 6   9   |
 +-------------+-------------+-------------+
 | 6   5   7   | 1   4   2   | 9   3   8   |
 | 14  2   14  | 9   8   3   | 67  5   67  |
 | 3   8   9   | 6   5   7   | 4   2   1   |
 +-------------+-------------+-------------+
A={R5C1,R6C3}
B={R4C7,R4C9,R5C9}
x=7
z=3

I'm reasonably sure you would treat both ALS sets A and B as strong nodes, but I think the option to treat them as links should also exist. Under current definitions, we have Strong Inferences "if r5c1<>7 then r6c3=3" and "if r4c7<>3 then r5c9=7" and v.v., but neither is a Strong Link.

However, if Strong Link implied only Strong Inference, there would be less confusion IMO, at least in the long run.

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

Maybe, but I think the inference definitions would still be useful because the (proposed) Conjugate Link term can then be defined in terms of both inferences.

Ron

P.S. If appropriate, I plan to address the balance of your post separately.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Mon Feb 27, 2006 3:00 pm

ronk wrote:
Code: Select all
 +-------------+-------------+-------------+
 | 24  7   8   | 24  6   5   | 1   9   3   |
 | 9   3   24  | 248 1   48  | 56  7   56  |
 | 5   1   6   | 7   3   9   | 8   4   2   |
 +-------------+-------------+-------------+
 | 28  9   23  | 458 7   6   |#35  1  #45  |
 |*17  6   5   | 3   9   14  | 2   8  #47  |
 | 178 4  *13  | 58  2   18  | 357 6   9   |
 +-------------+-------------+-------------+
 | 6   5   7   | 1   4   2   | 9   3   8   |
 | 14  2   14  | 9   8   3   | 67  5   67  |
 | 3   8   9   | 6   5   7   | 4   2   1   |
 +-------------+-------------+-------------+
A={R5C1,R6C3}
B={R4C7,R4C9,R5C9}
x=7
z=3

I'm reasonably sure you would treat both ALS sets A and B as strong nodes, but I think the option to treat them as links should also exist. Under current definitions, we have Strong Inferences "if r5c1<>7 then r6c3=3" and "if r4c7<>3 then r5c9=7" and v.v., but neither is a Strong Link.

I hear what you are saying and I understand what you are doing. But, I can't understand what benefit can be had to treat the almost locked set as a link instead of a node. In doing so, the piece of information in r4c9 becomes not part of the notation. It just likes leaving out one cell in a grouped node of a grouped x-cycle and arguing that the link is still valid without the omitted cell.

I also don't understand why you would create a new type of link and not give it a new name, but rather redefine existing terms to suit. A better option is of course to treat the element as a conventional node without having to change any definitions at all.

ronk wrote:However, if Strong Link implied only Strong Inference, there would be less confusion IMO, at least in the long run.

I don't think there would be less confusion because this term has been in use for a long time, so long that it is basically untouchable.
If there is really a need for a term to express ‘a link with pure strong inference’, I suggest calling it something else.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Mon Feb 27, 2006 3:29 pm

Jeff wrote:I hear what you are saying and I understand what you are doing. But, I can't understand what benefit can be had to treat the almost locked set as a link instead of a node. In doing so, the piece of information in r4c9 becomes not part of the notation. It just likes leaving out one cell in a grouped node of a grouped x-cycle and arguing that the link is still valid without the omitted cell.

You might try "because that's what people are doing". On what planet do you see anyone besides yourself using the "nodal notation"? I don't recall even Carcul doing so.

Jeff wrote:
ronk wrote:However, if Strong Link implied only Strong Inference, there would be less confusion IMO, at least in the long run.

I don't think there would be less confusion because this term has been in use for a long time, so long that it is basically untouchable.
If there is really a need for a term to express ‘a link with pure strong inference’, I suggest calling it something else.

It was suggestion, and you're free to suggest an alternative, but I don't really think the name is your hangup.

But more to the point: People pretty much equate Conjugate Link to Strong Link anyway, so I don't think it's much of definition change. And I see it as no different than your redefinition of Weak Link. (For reasons stated earlier, I don't count the change from Weak Link to Link as a new name.)

But I see your mind has again (or is that 'still is') shut like a steel trap door, so I'll quit wasting my time.

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

Postby Jeff » Mon Feb 27, 2006 4:09 pm

ronk wrote:But more to the point: People pretty much equate Conjugate Link to Strong Link anyway, so I don't think it's much of definition change. And I see it as no different than your redefinition of Weak Link. (For reasons stated earlier, I don't count the change from Weak Link to Link as a new name.)
But I see your mind has again (or is that 'still is') shut like a steel trap door, so I'll quit wasting my time.

Please be fair, Ronk. Apart from being condescending, you statement above is not factual.

Firstly, I did not redefine 'Weak Link'. Please check the first post. 'Weak Link' has dual meanings and is still being described as having dual meanings. The term 'Link' was included separately after lengthy discussions with and having been accepted by other members. For your information, 'Link' is a new term and it is not changed from 'Weak Link'. They are two separate terms.

Further, you are right in saying that people pretty much equate Conjugate Link to Strong Link. This means people always see Conjugate Link exactly same as Strong Link. But, what you are proposing is to make:

    Conjugate Link => both strong and weak inference
    Strong Link => strong inference.
How can you say that there is not much of definition change?

Lastly, how did I shut the door on you, Ronk? I haven't rejected your proposal, but am in the process to discuss and understand the requirement. Even though I don't agree with changing the definition of the term 'Strong Link' to suit the new link type, I did suggest a different name to be used if necessary. I think I am the one wasting time on you, Ronk.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Mar 02, 2006 6:07 pm

The term "Single Implication Network" replaced with "Error Net" in the first post.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Thu Mar 02, 2006 7:16 pm

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


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

Hi Vidar, Having read your posts on nice loops involving unique rectangles, now I can see that there are cases where unique rectangles cannot be treated as single nodes, but as links with strong inference only. I can also see that your description goes quite well even without a specific term designated for this type of link.

So, my advice to Ronk is:
A) I am now convinced that there are links with strong inference only,
B) Yes, we could give this type of link a name, and
C) This name must be unique such that it is not going to be confused with any existing terms.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ravel » Sat Mar 04, 2006 12:30 am

Sorry, if i am repeating something, i did not read the whole thread. When i look at all these definitions, it is no question that good work was done (with fine examples). But it also gives the feeling that it is much more complicated as it is.
My point of view is:
For any deduction step you have only 3 possibilities (according to the sudoku rules):
1. If a cell A=x, you can eliminate x from the cells in all 3 units that contain A. If there is any (other) unit then, which has no cell with a candidate x, you have a contradiction.
2. If A<>x, one of the other cells in the 3 units containing A must be x. In each of the 3 units that is left then with only one cell containing candidate x, it can be set to x. If in one of the 3 units no cell with candidate x remains, there is a contradiction.
3. (Given, that the puzzle is unique) Deadly non-unique patterns, that either lead to no or multiple solutions (UR, BUG, US), are a contradiction.

The rest is logic [edit: and of course the experience/intuition to find a good starting point] - including combination of steps and using logically derived pattens - and notation. To force or eliminate a candidate in a cell, you have 2 possibilities:
(a) Take all candidates of a cell, or all possible cells with a fixed candidate in a unit, or all candidates that avoid a deadly non-unique pattern, and deduce from all of them the same result(s), i.e. forcing a candidate in a cell or eliminating it (from one or more cells).
(b) The other way round: Assume that a cell is not or is a candidate and show that it leads to a contradiction.
Since A=>B is equivalent to (not B)=>(not A), these 2 ways are also equivalent: Just go back each step with the opposite assumption to get from (a) to (b) or vice versa.

The discussion above about different kinds of links (which i see is a point for the terminology) does not change anything for my logic view. I know that from a conjugated pair it follows that both A=x <=> B<>x and A<>x <=> B=x , and from an AUR might only follow A<>x => B=y and B<>y => A=x. But in any deduction i will only use an implication in one direction (the negation for the opposite direction must follow anyway), so i do not need an explicit distinction.

So i think that the impression i got at the first glance, namely that i have to understand all the definitions to be able to understand forcing chains, should be avoided in the starting page. What i am missing is an introduction for newcomers, eg stating (with examples like xy wing) , that all techniques can be derived by means of (sometimes rather complicated) forcing chains/nets/networks or what is it called when i need another if/then/else for notating a swordfish chain ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Jeff » Sat Mar 04, 2006 9:49 am

Hi ravel, thanks for your comments.

This thread and the definition list was started at the time when terms in relation to forcing chains, some have dual meaning and some were often misused (still are occasionally), eg. chain, net, weak link, implication etc. As such, the purpose of the list was primarily to provide clarification for the correct use of such terms, hoping that everyone who describes forcing chains will speak the same language. The list is never meant to be a full description for teaching the technique of forcing chain. There are heaps of other threads which do teach various kinds of forcing chains, from easy to advanced levels. The examples given in the list are intended to guide the users towards using the correct terms in his/er post description. Some of the examples in the list may be detailed enough that have led you to think they are for teaching purpose. However, if it does enable some newcomers to gain some understanding for the forcing chain technique; I would consider this as a bonus.

Your first point does very well explain the principle of a link inference step of a forcing chain/net. The list suggests that you may use the terms 'strong inference' and 'weak inference' to describe such steps simply.

Your second point does very well explain the concept of contradiction in a forcing chain/net. The list suggests that you may use the collective term 'error net' to describe the deduction, or 'implication chain/net' where more details are needed, provided that the deduction meets the requirements of a 'implication chain/net'.

ravel wrote:The discussion above about different kinds of links (which i see is a point for the terminology) does not change anything for my logic view. I know that from a conjugated pair it follows that both A=x <=> B<>x and A<>x <=> B=x , and from an AUR might only follow A<>x => B=y and B<>y => A=x. But in any deduction i will only use an implication in one direction (the negation for the opposite direction must follow anyway), so i do not need an explicit distinction.

The terms 'strong inference' and 'weak inference' are sufficient to describe all inferences in a single direction along a implication stream. However, since the list is meant to have a collection of terms, other common terms such as 'strong link' and 'weak link' are also welcome. It will be up to each individual to choose which term to use. I am happy to add any terms as proposed and agreed by the majority members of this forum. The discussion above is for a term to describe a new type of link with strong inference only. I can see such link exists in unique rectangles and it may well be important for some members to be able to describe this kind of link with a specific name, which is then up to others whether to use or not.

ravel wrote:So i think that the impression i got at the first glance, namely that i have to understand all the definitions to be able to understand forcing chains, should be avoided in the starting page. What i am missing is an introduction for newcomers, eg stating (with examples like xy wing) , that all techniques can be derived by means of (sometimes rather complicated) forcing chains/nets/networks or what is it called when i need another if/then/else for notating a swordfish chain ?

Quite the other way around; you don't have to understand all the definitions to be able to understand forcing chains because you should not learn the forcing chain technique from here. Rather, you need to have some understanding in forcing chains already in order for you to pick the terms to describe your network in line with others. Having said this, it doesn't mean that we should not add an example to the 'xy-wing' to made it easier to understand the term either. Any suggestions?
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Forcing chains: Terminology and Definition

Postby ronk » Sun Mar 05, 2006 1:45 pm

Jeff wrote:Pure Bilocation Chain - a chain with links that make strong inferences only to yield a deduction.

Is this meant to apply to both single-digit and multi-digit chains?

In the case of a pure bilocation loop with a discontinuity, is the purity requirement waived for the discontinuity?

Jeff wrote:Pure Bivalue Chain - a chain with strong nodes and links that make weak inferences to yield a deduction, eg, an xy-chain.

In the case of a pure bivalue loop with a discontinuity, is the purity requirement waived for the discontinuity?

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

Postby ravel » Sun Mar 05, 2006 2:11 pm

Jeff wrote:... The list is never meant to be a full description for teaching the technique of forcing chain. There are heaps of other threads which do teach various kinds of forcing chains, from easy to advanced levels. ... Any suggestions?

I see, so i would be happy, if some links to those threads would be given on the starting page.
ravel
 
Posts: 998
Joined: 21 February 2006

Re: Forcing chains: Terminology and Definition

Postby Jeff » Sun Mar 05, 2006 3:10 pm

ronk wrote:Is this meant to apply to both single-digit and multi-digit chains?

Pure bilocation chain applies only to multi-digit implication where all inferences are strong. An x-cycle is a single-digit implication, its inferences are alternatively strong and weak.

ronk wrote:In the case of a pure bilocation loop with a discontinuity, is the purity requirement waived for the discontinuity?

The purity requirement is not waived for the discontinuity. As such, the deduction of a discontinuous pure bilocation loop is in the form of an inclusion.

ronk wrote:In the case of a pure bivalue loop with a discontinuity, is the purity requirement waived for the discontinuity?

The purity requirement is not waived for the discontinuity. As such, the deduction of a discontinuous pure bivalue loop is in the form of an exclusion.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sun Mar 05, 2006 3:18 pm

ravel wrote:I see, so i would be happy, if some links to those threads would be given on the starting page.

Should links to these threads be added to the sticky post "Collection of solving techniques" or you would like to see them in both places.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ravel » Sun Mar 05, 2006 4:49 pm

A link to Mike Barker's post there would be fine enough for me (i did not see that there is such a collection, thanks). Ideally other good threads could be collected in a new post to the "Collection of solving techniques" thread for a "meta link". But the problem is that only the poster could edit it to insert new links.
ravel
 
Posts: 998
Joined: 21 February 2006

Re: Forcing chains: Terminology and Definition

Postby ronk » Mon Mar 06, 2006 6:13 am

Jeff wrote:
ronk wrote:
Jeff wrote:Pure Bilocation Chain - a chain with links that make strong inferences only to yield a deduction.

Is this meant to apply to both single-digit and multi-digit chains?
Pure bilocation chain applies only to multi-digit implication where all inferences are strong. An x-cycle is a single-digit implication, its inferences are alternatively strong and weak.

Since the name (title) belies the definition, I incorrectly took the definition to be incorrect.:)

Jeff wrote:... the deduction of a discontinuous pure bilocation loop is in the form of an inclusion.
...
... the deduction of a discontinuous pure bivalue loop is in the form of an exclusion.

Coincidentally, this same day tso uses both for an interesting observation here.

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

Re: Forcing chains: Terminology and Definition

Postby ronk » Wed Mar 08, 2006 7:19 pm

Jeff wrote:
ronk wrote:
Jeff wrote:Pure Bivalue Chain - a chain with strong nodes and links that make weak inferences to yield a deduction, eg, an xy-chain.

In the case of a pure bivalue loop with a discontinuity, is the purity requirement waived for the discontinuity?

The purity requirement is not waived for the discontinuity. As such, the deduction of a discontinuous pure bivalue loop is in the form of an exclusion.

In the case of a loop with a discontinuity, the same exclusion results even if the discontinuity has more than two candidates. Therefore, I plan to apply the term "chain" to that portion of the loop which excludes the discontinuity.

To be consistent, I guess I'll need to treat a "pure bilocation" loop with a discontinuity the same way.

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

PreviousNext

Return to Advanced solving techniques