The New Sudoku Players' Forum

[Scott H]

One techique for finding forcing chains is to identify a collection of nodes and edges that could be in a chain, then piece them together in a way that makes a useful deduction. This thread presents a method of labelling edges that helps to construct and recognize forcing chains, and discusses the common deductions.

In any forcing chain, two nodes A and B connected by an edge will share some common candidate (x, say). We will label the edge as "x", "-x", or "-x*", and give rules for when two labels from a node form part of a forcing chain. The form of label to use isn't uniquely determined by the edge, but depends on the larger context in which a forcing chain is being assembled. When the nodes share multiple common candidates, the candidate to use for labelling the edge also depends on the chain context.

Label "x" on an edge connecting nodes A and B represents the logical condition "A=x or B=x, but not both". Label "-x*" on the edge represents condition "A<>x or B<>x or both". Label "-x" represents condition "A<>x or B<>x, but not both".

Consider two edges, from nodes A to B and nodes B to C.
There are just 3 cases where edges entering and leaving B propagate a forcing chain implication. We write A=xy* to mean node A definitely has candidates x and y, and optionally has other candidates *.

Case 1: A=x*, B=xy, C=y*, AB label = -x*, BC label = -y*. This 2 edge chain guarantees condition "A<>x or C <>y or both". There are implications in both directions:
A=x -> B<>x -> B=y -> C<>y
and
C=y -> B<>y -> B=x -> A<>x.
Both implications are captured by condition "A<>x or C <>y or both".

Case 2: A=x*, B=xy*, C=y*, AB label = x, BC label = y (two strong edges). This chain guarantees condition "A=x or C=y or both", which also captures implications in both directions.

Case 3: A=x*, B=x*, C=x*, AB label = x, BC label = -x*. This chain guarantees condition "A=x or C<>x or both"

In all cases above, the * is optional in both nodes and edges. An edge A-B labelled -x* is a possibly weak edge -- i.e., the unit (row/column/box) containing A and B might have other nodes with candidate x. If there are no other x candidates in A-B's unit we can change weak edge labelled -x* to strong edge labelled -x. All deductions that work for -x* edges work just as well for -x edges.

If we extend Case 1 using only nodes with 2 candidates each, we get xy-chains. tso gave some excellent examples of how to find xy-chains here, and I first described (in this forum) an edge labelling idea for tracking which edges form a useful chain.

xy-chains (Case 1) are composed of weak edges and strong (doubleton) nodes. Case 2 is a sort of dual to case 1. If we extend case 2 we get chains where all the edges are strong, the nodes can be weak (have 3 or more candidates), and adjacent edges use different numbers.

Case 3 includes color chains, where all edges use the same number and weak negative edges are allowed. If we restrict case 3 to only strong negative edges we get simple coloring.

For any chain connecting nodes A-B- ... - Y-Z, if initial edge label is x, final edge label is y, and all interior node labels match one of the 3 cases above, then we have two implications "A<>x -> Z=y" and "Z<>y -> A=x", and both implications are captured by "A=x or Z=y or both".

There are two types of deductions commonly drawn from forcing chains. The first deduction requires a forcing chain that starts and ends with the same node A, and has the same initial and final label. If the label is x we can deduce A=x (this follows from the forcing chain constraint A=x or Z=x, where Z=A in this case). If the label is -x* (or -x) we can deduce A<>x from "A<>x or Z<>x with Z=a". Although this path might look like a loop, no implications cross node A, they just start and end at node A. So I consider this case a forcing chain whose end nodes happen to be the same node. This has been called a "double implication chain" if the implication is started in the middle of the chain and propagated both directions to the chain ends.

The second type of deduction requires a full closed loop of nodes and edges where all edge labels are from the above 3 cases. Such a loop contains many forcing chains, including chains that start and end at one node or that omit just one edge of the loop. These implications let us deduce that all weak edges in the loop must actually be strong edges in a sudoku solution, so we can eliminate extra candidates from units containing a weak edge in a closed forcing loop. X-wing is one example of this deduction using color chains (case 3 edge combinations). Naked pairs and xy-chain triples are this deduction using case 1 edge combinations. We can also eliminate extra candidates from connecting node B in case 2 edge combinations, since the forcing chain starting and ending at node B enforces "B=x or B=y". Hidden pairs is an example fo this deduction for case 2 edge combinations.

This message has gotten long and the hour is late, so I'll stop for now. I hope this edge labelling idea helps gel the various forcing chain notions for you. For me, it's a very useful bookkeeping technique for locally showing the relations forcing chains force, and combining this information in a standard format for every forcing chain (start node relation 1 or end node relation 2 or both).

[Jeff]

Is this the simplest you can put it. Rough rough going. Need to chew...over it. Thanks

[Scott H]

A suggestive notation would help to understand and use these ideas. Here's a proposal. Describe nodes (cells) by [...] and edges by <...> between the nodes they connect.

Node notation:

Code: Select all

[xy]      means exactly candidates x and y.
[xy*]     means candidates x and y, and optionally other candidates.
[A:xy]    gives name A to the node.
[rc:xy]   Says the node is row r, column c.
[A,rc:x*] gives the node's location, names it A, and says it has candidate x
             and other unspecified candidates.

Edge notation:

Code: Select all

[A:x*]  <x> [B:x*] means "A=x  or B=x"  in a forcing chain (strong edge).
[A:x*] <-x> [B:x*] means "A<>x or B<>x" in a forcing chain (weak edge). 

With this notation, a typical xy-chain can be written

Code: Select all

[U:ab] <-b> [bc] <-c> [cd] <-d> [V:de]

which enforces relation "U<>b or V<>d". Since U and V are doubleton nodes, this is equivalent to "U=a or V=e".

[Jeff]

Thank you for the nice work, Scott.

I guess the example shown is a bivalue non-repetitive cycle. The xy-chain that has been described in this forum is of repetitive type with 2 consecutive edges.

Code: Select all

For a non-repetitive cycle, U always equal V:

      [U:ab] <-b> [bc] <-c> [cd] <-d> [de] <-e> [ea] <-a> [V:ab]

For a repetitive cycle (xy-chain from U to V):

      [W:a*] <-a> [U:ab] <-b> [bc] <-c> [cd] <-d> [V:da] <-a> [W:a*]



[emm]

You guys are awesome. Do you think if I look at the screen long enough some of it will rub off..... Naah, don't answer that - rhetorical question.

[Jeff]

For your consideration, I have an idea for the notation of forcing chains to reduce the amount of typing:

Since the edge label has already appeared in cells, we can omit the edge label altogether and make use of the candidate in the cells to show. Also, we could use '=' to represent strong links and "-" to represent weak links. Thus:

Code: Select all

[U:ab] <-b> [bc] <-c> [cd] <-d> [de] <-e> [ea] <-a> [V:ab]

would become

Code: Select all

[U:ab]-[bc]-[cd]-[de]-[ea]-[V:ab]

and

Code: Select all

[A,87:4*] <4> [88:4*] <-4> [48:43] <-3> [28:3*] <3> [27:34] <4> [B,87:4*]

would become

Code: Select all

[A,87:4*]=[88:4*]-[43]-[28:3*]=[34]=[B,87:4*]

[Jeff]

Scott

Having survived the Eppstein puzzle, I think we all deserve a break. Sorry to have to wait you up so soon. I would like to pursue your idea of edge labelling; great stuff mate.

Thank you for what you have done so far. Here is what I need to clear up. I am still not crystal clear on the difference between an edge with label '-x' and '-x*'. Correct me if I am wrong, '-x' label is used when there are bivalue nodes with weak links, and '-x*' label is used when there are multiple candidate nodes with weak links; and one place it can be used is at the conflicting chain of the bilocation path.

Further, I think we need a lot of examples to help us to consolidate the technique. How about listing examples based on the 6 Eppstein's cycles/paths and some existing techniques, like x-wing, angus' colours, turbot fish and xy-chain. One each will be helpful.

Only after we have absorbed all these, we should carry on with the combination chains.

Thank you in anticipation.

[Scott H]

Scott
Thank you for what you have done so far. Here is what I need to clear up. I am still not crystal clear on the difference between an edge with label '-x' and '-x*'. Correct me if I am wrong, '-x' label is used when there are bivalue nodes with weak links, and '-x*' label is used when there are multiple candidate nodes with weak links; and one place it can be used is at the conflicting chain of the bilocation path.

Jeff, the critical information in a negative edge label is that it makes a negative implication in a forcing chain, so

Code: Select all

[A:] <-x> [B:]

means A<>x or B<>x. It doesn't matter for the implication whether or not there are any other x's in the unit containing A and B. If yes, it's a "strictly weak" link and if not, it's a strong link.

So <-x> denotes an edge that makes a negative implication in a forcing chain. The edge could be either "strictly weak" or "strong". I think "weak" has been used ambiguously in this forum (and I count myself in the guilty parties). As I recall, the first uses of "weak" in describing forcing chains meant "either strictly weak, or strong". But "weak" has been used to mean "strictly weak" in some places.

Think of the "*" in "<-x*>" as optional. I've used the * to mean a strictly weak edge (there are other x's). But remember this is peripheral to the forcing chain implication. It's just an optional reminder in the notation the implication works for both strong and strictly weak edges. And for some chains it's a visible indicator that some candidates exist that can be excluded.

[Jeff]

Thanks Scott, I think I finally grasped the notion. Just need a few examples and practice for the idea to sink in. Please comment on correct use of notations.

1) Eppstein's paper Fig 8 - Conflicting bilocation path

[A,68:2*]<2>[27]<7>[79]<9>[86:9*]<-9>[82:9*]<9>[96]<6>[67]<7>[72]<2>[B,68:2*]
enforces A=2 or B=2. Since A=B, therefore r6c8=2.
Is the notation of the edge between the 9s correct?

2) x-wing
[A,x*]<x>[B,x*]<-x>[C,x*]<x>[D,x*]<-x>[E,x*]
enforces A=x or E<>x. Since A=E, ............need help here.

3) Turbot fish - case 4
[A,x*]<-x>[B,x*]<x>[C,x*]<-x>[D,x*]<x>[E,x*]<-x>[F,x*]
enforces A<>x or F<>x. Since A=F, therefore A<>x.

4) xy-chain - repetitve cycle
[U,b*]<-b>[bc]<-c>[cd]<-d>[db]<-b>[V,b*]
enforces U<>b or V<>b. Since U=V, therefore U<>b.
Is this a bivalue conflicting path in which node U can have multiple candidates (ie, more than 2 candidates)?

5) xy-chain - non-repetitive bivalue cycle
[U,ab]<-b>[bc]<-c>[cd]<-d>[da]<-a>[V,ab]
enforces U<>b or V<>a. Since U=V, ............need help here.

6) Combination cycle - a previous example posted by you

[A,87:4*]<4>[B,88:4*]<-4>[C,48:43]<-3>[D,28:3*]<3>[E,27:34]<4>[F,87:4*]
enforces A=4 or F=4. Since A=F, therefore r8c7=4.
I notice that the edge between C&D can be <3>, but why is it expressed as <-3>?
What are the rules governing the combination cycle?
What is the conflicting path of a combination cycle?

Cheers