Forcing chains: Terminology and Definition

Advanced methods and approaches for solving Sudoku puzzles

Postby Jeff » Sat Jan 28, 2006 12:43 am

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

Hi Ronk, This is another type of implication network that should be addressed. I think the name would have to be more specific.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sat Jan 28, 2006 1:23 am

Jeff wrote:
ronk wrote:Implication Network - A network with

This is another type of implication network that should be addressed. I think the name would have to be more specific.

I took the adjective "Single" out of your title because I had no idea what you meant by it, and I still don't. Neither "single network" nor "single implication" made sense. "Single" candidate might, but "candidate" wasn't part of your title. To what were you referring?

I also stripped the word "open" from the definition ... mostly because "open" is used nowhere else in the definition post.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Sat Jan 28, 2006 1:40 am

ronk wrote:I took the adjective "Single" out of your title because I had no idea what you meant by it, and I still don't. Neither "single network" nor "single implication" made sense. "Single" candidate might, but "candidate" wasn't part of your title. To what were you referring?

I also stripped the word "open" from the definition ... mostly because "open" is used nowhere else in the definition post.

Double implication means 2 implication streams. Derived from this, Single implication means one implication stream.

All forcing networks in the definition list are loop type. Single implication network doesn't form a loop, thus I called it open type.

Consider the network posted by Carcul:

Code: Select all
 178   2789 3   | 4     158  1578| 6    12789 129   
 14678 5    1267| 167   1368 9   | 2348 12478 1234 
 14678 4789 1679| 2     1368 1678| 3489 14789 5   
----------------+----------------+-----------------
 2     6    8   | 59    7    45  | 1    3     49     
 134   34   15  | 8     149  12  | 2459 6     7     
 9     47   157 | 3     146  1246| 2458 2458  24     
----------------+----------------+-----------------
 5     2379 2679| 1679  1469 1467| 2349 1249  8     
 3678  3789 4   | 15679 2    1578| 359  159   1369   
 68    1    269 | 569   4589 3   | 7    2459  2469   

Now, we can write the following (complicated) Single Implication Network:

[r1c8](-1-[r1c156])-1-[r146c9]-2,4,9-[r9c9](-6-[r9c34])-6-[r9c1](-8-[r9c5]=8=[r8c6]-8-[r1c6])-8-[r1c1]-7-[r1c6]-5-[r4c6](-4-[r4c9]-9-[r1c9]-2-[r1c2])=5=[r4c4]-5-[r9c4]-9-[r9c3]-2-[r7c2]

and we have two weak links labelled "2" connected to both "2s" of column 2, which means that if r1c8=1 then column 2 would have no "2", which is a contradiction. So, r1c8<>1.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sat Jan 28, 2006 3:52 am

Jeff wrote:Double implication means 2 implication streams. Derived from this, Single implication means one implication stream.

I maintain that one implication stream does not a contradiction make.

Carcul wrote:Now, we can write the following (complicated) Single Implication Network:

[r1c8](-1-[r1c156])-1-[r146c9]-2,4,9-[r9c9](-6-[r9c34])-6-[r9c1](-8-[r9c5]=8=[r8c6]-8-[r1c6])-8-[r1c1]-7-[r1c6]-5-[r4c6](-4-[r4c9]-9-[r1c9]-2-[r1c2])=5=[r4c4]-5-[r9c4]-9-[r9c3]-2-[r7c2]

Holy (use your favorite Robin expression here), Batman! For that same puzzle, let's work with something simpler.
Carcul wrote:
Code: Select all
 178   2789 3   | 4     158  1578| 6    12789 129   
 14678 5    1267| 167   1368 9   | 2348 12478 1234 
 14678 4789 1679| 2     1368 1678| 3489 14789 5   
----------------+----------------+-----------------
 2     6    8   | 59    7    45  | 1    3     49     
 134   34   15  | 8     149  12  | 2459 6     7     
 9     47   157 | 3     146  1246| 2458 2458  24     
----------------+----------------+-----------------
 5     2379 2679| 1679  1469 1467| 2349 1249  8     
 3678  3789 4   | 15679 2    1578| 359  159   1369   
 68    1    269 | 569   4589 3   | 7    2459  2469

Whatever its name, we can write ...

[r1c2](-7-[r6c2]-4-[r5c2]-3-[r5c1])-7-[r123c1]=7=[r8c1]=3=[r5c1]

... which is a contradiction, because r5c1<>3 and r5c1=3 cannot both be true. Therefore, r1c2<>7. (The contradiction might also be written as two 3s in row 5 ... or no candidates in a bivalue cell.)

There are two implication streams for the above expression:

r1c2=7 => r6c2<>7 => r6c2=4 => r5c2<>4 => r5c2=3 => r5c1<>3

r1c2=7 => r123c1<>7 => r8c1=7 => r8c1<>3 => r5c1=3
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Sat Jan 28, 2006 5:03 am

ronk wrote:[r1c2](-7-[r6c2]-4-[r5c2]-3-[r5c1])-7-[r123c1]=7=[r8c1]=3=[r5c1]

... which is a contradiction, because r5c1<>3 and r5c1=3 cannot both be true. Therefore, r1c2<>7. (The contradiction might also be written as two 3s in row 5 ... or no candidates in a bivalue cell.)

There are two implication streams for the above expression:

r1c2=7 => r6c2<>7 => r6c2=4 => r5c2<>4 => r5c2=3 => r5c1<>3

r1c2=7 => r123c1<>7 => r8c1=7 => r8c1<>3 => r5c1=3

This is just a non-preferred way to express a double implication chain:

[r1c2]-7-[r6c2]-4-[r5c2]-3-[r5c1]=3=[r8c1]=7=[r123c1]-7-[r1c2] => r1c2<>7

Can you give another example?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sat Jan 28, 2006 5:28 am

Jeff wrote:Can you give another example?

Can you provide the single implication stream for Carcul's example?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Sat Jan 28, 2006 6:36 am

ronk wrote:Can you provide the single implication stream for Carcul's example?

Here it is.

Single Implication Network:

[r1c8](-1-[r1c156])-1-[r146c9]-2,4,9-[r9c9](-6-[r9c34])-6-[r9c1](-8-[r9c5]=8=[r8c6]-8-[r1c6])-8-[r1c1]-7-[r1c6]-5-[r4c6](-4-[r4c9]-9-[r1c9]-2-[r1c2])=5=[r4c4]-5-[r9c4]-9-[r9c3]-2-[r7c2]
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Sat Jan 28, 2006 11:52 am

Hi Ronk.

Ronk wrote:For that same puzzle, let's work with something simpler.(...)Whatever its name, we can write ...

[r1c2](-7-[r6c2]-4-[r5c2]-3-[r5c1])-7-[r123c1]=7=[r8c1]=3=[r5c1]


Very well spoted Ronk. I have to addmit that I didn't spot this deduction, however because later in the solving I have proved directly that r1c2 must be "2".
BTW, we could "group" r1c2 with r3c2 in your loop (or Jeff's) to make the deduction r1c2,r3c2<>7.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Sat Jan 28, 2006 4:03 pm

Jeff wrote:
ronk wrote:Can you provide the single implication stream for Carcul's example?

Here it is. Single Implication Network:

[r1c8](-1-[r1c156])-1-[r146c9]-2,4,9-[r9c9](-6-[r9c34])-6-[r9c1](-8-[r9c5]=8=[r8c6]-8-[r1c6])-8-[r1c1]-7-[r1c6]-5-[r4c6](-4-[r4c9]-9-[r1c9]-2-[r1c2])=5=[r4c4]-5-[r9c4]-9-[r9c3]-2-[r7c2]

I thought my request for the single implication stream was clear. You merely quoted Carcul's implication network. I certainly don't equate 'stream' and 'network'.

Let's graph that network, ala Myth Jellies.
Code: Select all
     >  >  >  >  > r1c8-1-r1c16
  ^                         +  +
  ^                         +    +
  ^                r9c1-8-r1c1-7-r1c6        r4c6-4-N-9-O-2-r1c2=2=r7c2
  ^                  ^              +          ^                     +
  ^                   ^               +       ^                        +
r1c8-1-B-2,4,9-r9c9-6-r9c1-8-E=8=F-8-r1c6-5-r4c6=5=I-5-r9c4-9-r9c3-2-r7c2
                 v                                      +     +
                 v                                    +    +
                   >  >  >  >  >  >  >  >  >  r9c9-6-r9c34

Key: '^', 'v', and '>' indicate diverging paths
     '+' indicates converging path

While the network has one starting cell (node) and one ending cell, implication paths diverge and converge in order to indicate a contradictory conclusion at the ending cell. I consider each possible path through the network as an implication stream. IOW divergences and convergences cannot exist in an implication stream IMO.

For Carcul's 'network', three sub-paths are required to eliminate three candidates (r1c6<>1, 7, 8) followed by two sub-paths to the contradiction (r7c2<>2 and r7c1<>2). Therefore, from my POV, there are six (3 x 2) implication streams ... not one.

[edit: Diagram modified to add missing path through r9c34. Box brackets deleted to minimize line wrap.]
Last edited by ronk on Sat Jan 28, 2006 2:39 pm, edited 3 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Sat Jan 28, 2006 4:31 pm

ronk wrote:I thought my request for the single implication stream was clear. You merely quoted Carcul's implication network. I certainly don't equate 'stream' and 'network'.

That's a very nice diagram that you have drawn, Ronk.

An implication steam for a chain is different from an implication stream for a net. Whereas the former is restricted to have inferences from one node to the next only, the latter would allow multiple inferences. Please refer to the definition of a forcing net. As such, Carcul's network can rightfully be regarded as one implication stream, as far as a forcing net is concerned.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sat Jan 28, 2006 4:57 pm

Jeff wrote:Please refer to the definition of a forcing net. As such, Carcul's network can rightfully be regarded as one implication stream, as far as a forcing net is concerned.

I looked and I see ...
Network - a collective term for forcing chain and forcing net.

Forcing Chain - a closed cycle that has 2 or more implication streams that start from one node and end in one node.

Forcing Net - a closed cycle that has 2 or more implication streams that start from one node and end in one node. In a forcing net, a node could infer 2 or more nodes downstream.

'Network' is equated to 'forcing chain' or 'forcing net', both of which are described as 'closed' cycle. Carcul's network is not closed. Also neither forcing chain nor forcing net allow for the possibility of 'one' implication stream.

... so I think some changes/additions to the definitions are in order.
Last edited by ronk on Sat Jan 28, 2006 2:17 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Sat Jan 28, 2006 5:04 pm

ronk wrote:['Network' is equated to 'forcing chain' or 'forcing net', both of which are described as 'closed' cycle. Carcul's network is not closed. Also neither forcing chain nor forcing net allow for the possibility of 'one' implication stream.

... so I think some changes/additions to the definitions are in order.

Absolutely. Some definitions ought to be adjusted to accommodate the definition of "Single Implication Network".
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sat Jan 28, 2006 5:10 pm

Jeff wrote:Some definitions ought to be adjusted to accommodate the definition of "Single Implication Network".

Then why refer me to a definition in need of adjustment?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jeff » Sat Jan 28, 2006 5:50 pm

ronk wrote:Then why refer me to a definition in need of adjustment?

I referred you to 'chain' and 'net' so that you can note their differences. 'Closed loop' and '2 or more implication streams' are same for both chain and net, and therefore is irrelevant to our discussion at hand.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Myth Jellies » Sun Jan 29, 2006 12:13 am

A few more things you might want to address in the opening post.

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

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

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.

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

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

6. 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.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

PreviousNext

Return to Advanced solving techniques