I need help with this forcing chain

Advanced methods and approaches for solving Sudoku puzzles

I need help with this forcing chain

Postby Jasper32 » Sun Mar 09, 2008 5:03 pm

I have just about everything written about them except in one area. To me, there seems to be some ambiguity in some of the writings. The enclosed puzzle has several forcing chains in the latter stages of this puzzle and I guess I just don’t understand why some seem to seem to work for me and some don't.The situations of very short forcing chains have me completely confused. I hope someone can explain what is the correct way of handling these very short chains.

1St
r2c2=2 r3c3=8 r3c8=2
I though that since both ends of the chain "see" both r2c7 and r2c8 that the (2's) could be eliminated. No so.

2nd
r6c3=2 r6c9=8 r4c2
Here I thought that (2) could be excluded from r4c2. Again. not so.

3rd
r4c7=1 r7c7=2 r7c8=1
Here you can eliminate (1) from r5c8

Now why in two of the three cases are different. Please , I hope someone can explain this to me. Is my assumption that a candidate can be excluded if it "sees" both ends of a chain. Yep, I need help.
Code: Select all
 *-----------*
 |139|258|476|
 |7.6|143|..9|
 |54.|976|3.1|
 |---+---+---|
 |6.3|.97|.4.|
 |9..|462|7.3|
 |47.|.31|69.|
 |---+---+---|
 |397|685|..4|
 |264|719|835|
 |851|324|967|
 *-----------*

 
 *--------------------------------------------------*
 | 1    3    9    | 2    5    8    | 4    7    6    |
 | 7    28   6    | 1    4    3    | 25   258  9    |
 | 5    4    28   | 9    7    6    | 3    28   1    |
 |----------------+----------------+----------------|
 | 6    12   3    | 58   9    7    | 15   4    28   |
 | 9    18   58   | 4    6    2    | 7    15   3    |
 | 4    7    25   | 58   3    1    | 6    9    28   |
 |----------------+----------------+----------------|
 | 3    9    7    | 6    8    5    | 12   12   4    |
 | 2    6    4    | 7    1    9    | 8    3    5    |
 | 8    5    1    | 3    2    4    | 9    6    7    |
 *--------------------------------------------------*

Jasper32
 
Posts: 60
Joined: 04 January 2008

Re: I need help with this forcing chain

Postby sudophil » Sun Mar 09, 2008 6:21 pm

Jasper32 wrote:1St
r2c2=2 r3c3=8 r3c8=2
I though that since both ends of the chain "see" both r2c7 and r2c8 that the (2's) could be eliminated. No so.

2nd
r6c3=2 r6c9=8 r4c2
Here I thought that (2) could be excluded from r4c2. Again. not so.

3rd
r4c7=1 r7c7=2 r7c8=1
Here you can eliminate (1) from r5c8

Now why in two of the three cases are different. Please , I hope someone can explain this to me. Is my assumption that a candidate can be excluded if it "sees" both ends of a chain. Yep, I need help.


All 3 are not correct assumptions because the chain needs to xor the ends. That way either way the chain works it will have a candidate locked up for the shared row col or box.

[edit]
The following is using your cells in the 3rd example
[/edit]

The chain you need for this elimination is
5(r4c7) 2(r2c7) 8(r2c2) 1(r5c2) -> (r5c8)<>1
1(r4c7) -> (r5c8)<>1
sudophil
 
Posts: 14
Joined: 24 May 2006

Re: I need help with this forcing chain

Postby daj95376 » Sun Mar 09, 2008 7:32 pm

Withdrawn: I was thinking of something else!!!
Last edited by daj95376 on Sun Mar 09, 2008 5:34 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: I need help with this forcing chain

Postby Sudtyro » Sun Mar 09, 2008 8:27 pm

Jasper32 wrote:...I though that since both ends of the chain "see"...

This expression generally refers to the exclusion candidate(s) being able to "see" (weakly link to) both ends of an Alternating Inference Chain (AIC) and not the ends of a single implication stream. For example, sudophil's elimination is equivalent to the following AIC (also an XY-chain):
(1=5)r4c7 - (5=2)r2c7 - (2=8)r2c2 - (8=1)r5c2 => r5c8 <> 1.
The chain shows that the two ends have a derived strong inference, meaning that at least one of them must be true. Hence, since (1)r5c8 can "see" both ends of the AIC, it must be false.
[Edit to add: The AIC reads:
if r4c7<>1 => r4c7=5 => r2c7<>5 ... => r5c2<>8 => r5c2=1.
You can also read the chain from the other end, starting with:
if r5c2<>1 => r5c2=8 ... => r4c7=1.
Both cases show at least one end as being true.]

The puzzle also solves quickly with a shorter AIC (also an XY-wing):
(2=1)r4c2 - (1=5)r4c7 - (5=2)r2c7 => r2c2 <> 2.

[edit: change "forcing chain" to "implication stream." Thanks, daj!]
Last edited by Sudtyro on Sun Mar 09, 2008 8:54 pm, edited 2 times in total.
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Postby Jasper32 » Sun Mar 09, 2008 9:40 pm

I was wrong on all accounts. Thanks for your replys.

Sudophil wrote the following.

I
All 3 are not correct assumptions because the chain needs to xor the ends


I don't understand is meant by "xor" the ends. Can someone explain that to me.

Again thanks for your help. I am rather a "Newbee" and your help is truly aqppreciated.
Jasper32
 
Posts: 60
Joined: 04 January 2008

Postby daj95376 » Sun Mar 09, 2008 10:14 pm

What I should have said earlier!

http://forum.enjoysudoku.com/viewtopic.php?t=2859 wrote:Forcing Chain - a chain that has 2 or more implication streams that start from one node and end in another node where the outcomes of inferences merge from the 2 implication streams. In a forcing chain, a node can only infer the next successive node downstream.

Mike Barker wrote:Based on Jeff's definition, A Forcing Chain is a chain that has two or more implication streams that start from one node and end in another node where the outcomes of inferences merge from the implication streams. In a Forcing Chain, a node can only infer the next successive node downstream. Nice Loops and AIC are essentially different ways of looking at double implication forcing chains which follow specific propagation rules. In the case of Nice Loops, these rules establish how strong links, bivalues, ALS, etc can be linked together to construct a valid eliminations. In the case of AIC, these rules establish how candidates in strong links, bivalues, ALS, etc can be linked together using alternating strong and weak links to construct valid eliminations.

1) Your chains are not Nice Loops.
2) Your chains are not AICs.
3) Your chains have only one implication stream.

Your chains are not forcing chains.

BTW: I think Sudopedia dropped the ball with its restrictive definition and its example of a Forcing Chain.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Sudtyro » Sun Mar 09, 2008 11:34 pm

Jasper32 wrote:
All 3 are not correct assumptions because the chain needs to xor the ends


I don't understand is meant by "xor" the ends. Can someone explain that to me.

I'm not sure about this requirement either, but I believe that for a logical "A XOR B" to be true, then A or B, but not both, must be true.

However, in an AIC the derived strong inference between the two ends of the chain means that at least one must be true, and this doesn't exclude the case of both being true. For this puzzle, in fact, it turns out that both of the first AIC's 1s are true. For the second AIC, only (2)r4c2 turns out to be true. It doesn't matter, tho, since the exclusions hold in either strong-inference scenario.
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Postby sudophil » Mon Mar 10, 2008 2:19 am

I was wrong about the xor condition. Chains most often work one direction. What you do want to see is if you eliminate a candidate on one end then the other end will contain the candidate. But that isn't necessarily true the other way around like I implied with the xor statement.
sudophil
 
Posts: 14
Joined: 24 May 2006

re: forcing chains

Postby Pat » Mon Mar 10, 2008 8:31 am

Jasper32 wrote:To me, there seems to be some ambiguity in some of the writings [ on forcing chains ].


which writings ??
where's the ambiguity ??


Jasper32 wrote:The enclosed puzzle has several forcing chains in the later stages of this puzzle and I just don’t understand why some seem to seem to work and some don't.

  1. r2c2=2 r3c3=8 r3c8=2
    I thought that since both ends of the chain "see" both r2c7 and r2c8 that the (2's) could be eliminated. No so.
  2. r6c3=2 r6c9=8 r4c2
    Here I thought that (2) could be excluded from r4c2. Again. not so.
  3. r4c7=1 r7c7=2 r7c8=1
    Here you can eliminate (1) from r5c8
Now why in two of the three cases are different.

Code: Select all
 *--------------------------------------------------*
 | 1    3    9    | 2    5    8    | 4    7    6    |
 | 7    28   6    | 1    4    3    | 25   258  9    |
 | 5    4    28   | 9    7    6    | 3    28   1    |
 |----------------+----------------+----------------|
 | 6    12   3    | 58   9    7    | 15   4    28   |
 | 9    18   58   | 4    6    2    | 7    15   3    |
 | 4    7    25   | 58   3    1    | 6    9    28   |
 |----------------+----------------+----------------|
 | 3    9    7    | 6    8    5    | 12   12   4    |
 | 2    6    4    | 7    1    9    | 8    3    5    |
 | 8    5    1    | 3    2    4    | 9    6    7    |
 *--------------------------------------------------*



none of the 3 examples work,
they have no logical basis.
User avatar
Pat
 
Posts: 3441
Joined: 18 July 2005

Re: re: forcing chains

Postby daj95376 » Mon Mar 10, 2008 4:19 pm

Pat wrote:
Jasper32 wrote:To me, there seems to be some ambiguity in some of the writings [ on forcing chains ].

which writings ??
where's the ambiguity ??

Jasper32 wrote:The enclosed puzzle has several forcing chains in the later stages of this
  1. r2c2=2 r3c3=8 r3c8=2
    I thought that since both ends of the chain "see" both r2c7 and r2c8 that the (2's) could be eliminated. No so.
  2. r6c3=2 r6c9=8 r4c2
    Here I thought that (2) could be excluded from r4c2. Again. not so.
  3. r4c7=1 r7c7=2 r7c8=1
    Here you can eliminate (1) from r5c8
Now why in two of the three cases are different.

none of the 3 examples work,
they have no logical basis.

Pat, as you pointed out, none of Jasper32's chains are forcing chains. Have you taken a look at the properties and example in Sudopedia for a forcing chain. The example looks just like Jasper32's chains. Ambiguity?

Jeff wrote:Node - a cell or a group of cells joining 2 links in a chain propagation. A node is multi-valued and may contain any number of candidates. Each node has a weak inference that implies the labelled candidate(s) of the preceding link in the node is/are true; along the flow of an implication stream. (Refer definitions for "link" below)

Jeff says that each node has a weak inference, but Mike Barker says that a Nice Loop and an AIC represent double implication forcing chains. In general, Nice Loops and AICs have strong links that are used as strong inference. Ambiguity?

Since there are ten pages of comments in Jeff's thread alone, I have no idea what's the final definition of Forcing Chains once other threads and other sources than this forum are considered.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

re: forcing chains

Postby Pat » Mon Mar 10, 2008 5:19 pm

daj95376 wrote:Pat, as you pointed out, none of Jasper32's chains are forcing chains. Have you taken a look at the properties and example in Sudopedia for a forcing chain. The example looks just like Jasper32's chains. Maybe now you know where some ambiguity exists.


he didn't say where it was he was reading

and no i hadn't checked the SuDoPedia

but looking at it now,
i see that the article on Forcing Chains -- trying to be very generic -- merely gives an example of an implication-stream which provides no exclusions
    nor did it claim to provide any exclusions in this example !!
    no ambiguity

    but i suppose that's what you had meant, in your earlier post,
    about dropping the ball
User avatar
Pat
 
Posts: 3441
Joined: 18 July 2005

re: "forcing chains"

Postby Pat » Tue Mar 11, 2008 3:09 pm

daj95376 wrote:
Jeff (last edited 2006.Jul.30) wrote:Node - a cell or a group of cells joining 2 links in a chain propagation. A node is multi-valued and may contain any number of candidates. Each node has a weak inference that implies the labelled candidate(s) of the preceding link in the node is/are true; along the flow of an implication stream. (Refer definitions for "link" below)


Jeff says that each node has a weak inference, but Mike Barker says that a Nice Loop and an AIC represent double implication forcing chains. In general, Nice Loops and AICs have strong links that are used as strong inference. Ambiguity?


hey daj95376,

each "node" has at least a "weak inference". that's the general case.

some specific cases have additional requirements.
    a "strong link" is stronger than a "(weak) link"
    a "strong link" is a special case of a "(weak) link"
no ambiguity

~ Pat
User avatar
Pat
 
Posts: 3441
Joined: 18 July 2005


Return to Advanced solving techniques

cron