Nice loops for advanced level players - triple chain

Advanced methods and approaches for solving Sudoku puzzles

Nice loops for advanced level players - triple chain

Postby Jeff » Sat Dec 03, 2005 11:42 am

This thread describes the process that makes use of the bilocation/bivalue plot described in this thread to identify triple chains, short for triple implication chains.

A triple implication chain is a chain with 3 implication streams and each of these stream results in the same exclusion or inclusion outcome(s).

Each triple implication chain involves exactly one trivalue cell or three trilocation cells.

A Trivalue cell is a cell containing only three candidates. For each trivalue cell, a trivalue tripod is drawn on the cell using 3 links of weak inference (broken lines) as follows:
Image

Trilocation cells are cells with the same candidate appear exactly 3 times in a unit. For each set of trilocation cells, a trilocation triangle is drawn amongst the 3 cells using 3 links of stong inference (solid lines) as follows:
Image

With the bilocation/bivalue plot, 2 of the 3 links in a trilocation triangle or trivalue tripod are used at a time to make implications following the same set of nice loop propagation rules and theorems for candidate exclusion and inclusion.

Triple implication chains can be continuous or discontinuous. Since a continuous chain is extremely rare, we will concentrate on discontinuous triple chains. As a matter of interest, one of the 322 swordfish patterns is a good example of a continuous triple implication chain with the trilocation triangle shown in red.
Image

The diagram below shows a triple chain with a trivalue cell of discontinuous type. Since the chain is based upon a trivalue cell, the links in the trivalue node r6c2 form of a trivalue tripod (ie. 3 broken links shown in red diverge from node r6c2).
Image

Nice loop notation: This chain has 3 nice loops with a trivalue tripod at r6c2.
[r3c3]-2-[r1c2]-1-[r6c2]-9-[r3c2]=9=[r3c3]
[r3c3]=9=[r3c2]-9-[r6c2]-2-[r7c2]=2=[r7c3]-2-[r3c3]
[r3c3]-2-[r1c2]-1-[r6c2]-2-[r7c2]=2=[r7c3]-2-[r3c3]
All imply r3c3<>2

Note: There are 3 implication streams in a triple chain. Since each line of nice loop notation contains 2 implication streams, any of the 2 lines above would be sufficient to express the triple chain.

This triple chain can expressed as a multiple nice loop with a multiple inference as described here.
[r3c3]-2-[r1c2]-1-[r6c2](-9-[r3c2]=9=[r3c3])-2-[r7c2]=2=[r7c3]-2-[(r3c3)] => r3c3<>2

Proof:
r6c2=1 => r1c2<>1 => r1c2=2 => r3c3<>2
r6c2=2 => r6c2=2 => r7c2<>2 => r7c3=2 => r3c3<>2
r6c2=9 => r3c2<>9 => r3c3=9 => r3c3<>2

The diagram below shows a triple chain with 3 trilocation cells of discontinuous type. Since the chain is based upon 3 trilocation cells, the links in the trilocation cells r4c5, r5c6 and r6c5 form of a trilocation triangle (ie. 3 solid links shown in red joining nodes r4c5, r5c6 and r6c5 together).
Image

Nice loop notation: This chain has 3 nice loops with a trilocation triangle at r4c5, r5c6 and r6c5.
[r5c2]=9=[r5c6]-9-[r4c5]=9=[r8c5]-9-[r8c2]=9=[r5c2]
[r5c2]=9=[r5c6]-9-[r6c5]=9=[r8c5]-9-[r8c2]=9=[r5c2]
[r5c2]=9=[r5c6]-9-[r4c5]=9=[r6c5]-9-[r5c6]=9=[r5c2]
All imply r5c2=9

Note: There are 3 implication streams in a triple chain. Since each line of nice loop notation contains 2 implication streams, any of the 2 lines above would be sufficient to express the triple chain.

Multiple nice loop notation:
[r5c2]=9=[r5c6]-9-[r6c5](=9=[r4c5]-9-[r5c6]=9=[r5c2])=9=[r8c5]-9-[r8c2]=9=[(r5c2)] => r5c2=9

Proof:
r4c5=9 => r5c6<>9 => r5c2=9
r6c5=9 => r5c6<>9 => r5c2=9
r8c5=9 => r8c2<>9 => r5c2=9
Last edited by Jeff on Wed Mar 08, 2006 2:23 pm, edited 4 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby rubylips » Sun Dec 04, 2005 1:33 pm

Personally, in the second example I find it easier to conceptualize the trilocation triangle as an extended link, i.e. to note immediately that, due to the action of r4c5 and r6c5, r5c6=9 if and only if r8c5=9. I appreciate that this is essentially a play on words and that other readers might not find it easier. I write the link r5c6=9=r8c5, whereupon the solution becomes:
Code: Select all
Consider the chain r8c2-9-r5c2-9-r5c6=9=r8c5.
When the cell r8c2 contains the value 9, so does the cell r8c5 - a contradiction.
Therefore, the cell r8c2 cannot contain the value 9.
When the cell r8c5 contains the value 9, so does the cell r8c2 - a contradiction.
Therefore, the cell r8c5 cannot contain the value 9.
- The moves r8c2:=9 and r8c5:=9 have been eliminated.
The cell r8c3 is the only candidate for the value 9 in Row 8.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Jeff » Sun Dec 04, 2005 2:23 pm

rubylips wrote:Personally, in the second example I find it easier to conceptualize the trilocation triangle as an extended link, i.e. to note immediately that, due to the action of r4c5 and r6c5, r5c6=9 if and only if r8c5=9. I appreciate that this is essentially a play on words and that other readers might not find it easier.

You are right, Rubylips. There are many ways to look at the same deduction and everyone has his own preference. The trivalue tripod and trilocation triangle are just links required to be drawn on the bilocation/bivalue plot so that triple implication chains can be identified. Personally, I don't find it easy at all because there are so many lines when the bilocation/bivalue plot is ready. Others may enjoy the process and find a lot of fun doing it.

xyz-wing, xyz-chain and empty cell contradiction are triple implication chain equivalences which I would explore before resorting to bilocation/bivalue plot.
Jeff
 
Posts: 708
Joined: 01 August 2005

the first

Postby bennys » Sun Dec 04, 2005 4:45 pm

Interesting
in the first example even if you unset R8C8 you can still make the same deduction.
bennys
 
Posts: 156
Joined: 28 September 2005

Re: the first

Postby Jeff » Mon Dec 05, 2005 2:31 am

bennys wrote:Interesting
in the first example even if you unset R8C8 you can still make the same deduction.
Sorry, don't get it.:?:
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby bennys » Mon Dec 05, 2005 3:43 am

Its nothing much jest that 2 as a candidat in R8C2 will not change anything
bennys
 
Posts: 156
Joined: 28 September 2005

Postby Jeff » Mon Dec 05, 2005 4:45 am

bennys wrote:Its nothing much jest that 2 as a candidat in R8C2 will not change anything

I think it will make a different since the implication [r7c2]=2=[r7c3] cannot be done. Have I missed something?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby bennys » Mon Dec 05, 2005 5:49 am

I dont know if you missed it but R5C6=R8C5
so if one of them is 9 the other is also and that eliminate the 9 from c2
so we get R5C2=9
bennys
 
Posts: 156
Joined: 28 September 2005

Postby Jeff » Mon Dec 05, 2005 10:33 am

So, you are talking about the second example , not the first. Yes, a 2 in R8C2 will not change anything. Your logic will solve the puzzle, bennys, excellent observation as usual.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Mon Mar 06, 2006 7:40 am

The first post has be edited with the following:

    Title changed

    Terminology revised in line with accepted definitions

To whom it may concern: Could this thread be added to the sticky post?
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Nice loops for advanced level players - triple chain

Postby aeb » Mon Mar 06, 2006 12:03 pm

Jeff wrote:Image

Chain notation: This chain has 3 nice loops with a trivalue tripod at r6c2.
[r3c3]-2-[r1c2]-1-[r6c2]-9-[r3c2]=9=[r3c3]
[r3c3]=9=[r3c2]-9-[r6c2]-2-[r7c2]=2=[r7c3]-2-[r3c3]
[r3c3]-2-[r1c2]-1-[r6c2]-2-[r7c2]=2=[r7c3]-2-[r3c3]
All imply r3c3<>2

Proof:
r6c2=1 => r1c2<>1 => r1c2=2 => r3c3<>2
r6c2=2 => r7c2<>2 => r7c3=2 => r3c3<>2
r6c2=9 => r3c2<>9 => r3c3=9 => r3c3<>2

(3,3)2 > (3,3)!9 > (3,2)9 > (16,2)12 > (7,2)!2 > (7,3)2 > (3,3)!2
Jeff wrote:Image

Chain notation: This chain has 3 nice loops with a trilocation triangle at r4c5, r5c6 and r6c5.
[r5c2]=9=[r5c6]-9-[r4c5]=9=[r8c5]-9-[r8c2]=9=[r5c2]
[r5c2]=9=[r5c6]-9-[r6c5]=9=[r8c5]-9-[r8c2]=9=[r5c2]
[r5c2]=9=[r5c6]-9-[r4c5]=9=[r6c5]-9-[r5c6]=9=[r5c2]
All imply r5c2=9

Proof:
r4c5=9 => r5c6<>9 => r5c2=9
r6c5=9 => r5c6<>9 => r5c2=9
r8c5=9 => r8c2<>9 => r5c2=9

(5,2)!9 > (5,6)9 > (46,5)!9 > (8,5)9 > (8,2)!9 > (5,2)9

A philosophical question: we need to write down enough to show the steps of the solution. You do that here in the proof - it is completely clear. But then, what is the purpose of writing the less clear and longer chains above?

Some people will be happy to see Empty Rectangles here:
(8,5)3 > (4,5)!3 > (4,3)3 - no 3 in box 7. Hence (8,5)!3.
And another Empty Rectangle:
(8,5)9 > (8,2)!9 > (5,2)9 - no 9 in box 5. Hence (8,5)!9, that is, (8,5)6.
That solves the puzzle.
aeb
 
Posts: 83
Joined: 29 January 2006

Re: Nice loops for advanced level players - triple chain

Postby Jeff » Mon Mar 06, 2006 4:22 pm

aeb wrote:A philosophical question: we need to write down enough to show the steps of the solution. You do that here in the proof - it is completely clear. But then, what is the purpose of writing the less clear and longer chains above?

A philosophical answer: It is of academic interest. Don't forget this is an introductory thread for triple chain identification making use of nice loops. I have to show how the chain can be expressed in a nice loop notation. BTW, the chain didn't get longer. It is the nice loop notation which is longer than the proof. Being longer doesn't necessarily mean less clear.

aeb wrote:Some people will be happy to see Empty Rectangles here:
(8,5)3 > (4,5)!3 > (4,3)3 - no 3 in box 7. Hence (8,5)!3.
And another Empty Rectangle:
(8,5)9 > (8,2)!9 > (5,2)9 - no 9 in box 5. Hence (8,5)!9, that is, (8,5)6.
That solves the puzzle.

Would you be kind enough to stay on topic?
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Nice loops for advanced level players - triple chain

Postby aeb » Mon Mar 06, 2006 5:45 pm

Jeff wrote:
aeb wrote:A philosophical question: we need to write down enough to show the steps of the solution. You do that here in the proof - it is completely clear. But then, what is the purpose of writing the less clear and longer chains above?

A philosophical answer: It is of academic interest. Don't forget this is an introductory thread for triple chain identification making use of nice loops. I have to show how the chain can be expressed in a nice loop notation. BTW, the chain didn't get longer. It is the nice loop notation which is longer than the proof. Being longer doesn't necessarily mean less clear.

Why is it that the nice loop notation is twice as long as the proof? It is because you write down everything twice. The reasoning is a trifurcation: there are three possibilities: A,B,C. The proof says A>X, B>X, C>X hence X. Easy and simple. The "nice loop" notation is the equivalent of !X > !A > B > X and !X > !A > C > X and !X > !B > C > X where each of the chains is a false statement but the convention is that one has to read them together. Rather messy compared to the simple proof. Or, to say it in different words: the proof uses that there are three possibilities: A or B or C. The "nice loop" notation uses that there are three possibilities: "A or B", "A or C", "B or C". In cases where the proof would distinguish four cases, the same scheme would use six nice loops.
aeb
 
Posts: 83
Joined: 29 January 2006

Re: Nice loops for advanced level players - triple chain

Postby Jeff » Mon Mar 06, 2006 6:18 pm

aeb wrote:Why is it that the nice loop notation is twice as long as the proof? It is because you write down everything twice.

It appears that you like answering your own question. If your question were addressed to me, I would have answered:

    Again, it is of academic interest. There are 3 implication streams in a triple chain. Since each line of nice loop notation contains 2 implication streams, 2 lines would be sufficient to express the chain anyway. Again, I show all 3 lines for completeness so that people can learn all cases.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Nice loops for advanced level players - triple chain

Postby aeb » Mon Mar 06, 2006 7:35 pm

Jeff wrote:[There are 3 implication streams in a triple chain. Since each line of nice loop notation contains 2 implication streams, 2 lines would be sufficient to express the chain anyway.

Yes, indeed.
Jeff wrote:Again, I show all 3 lines for completeness so that people can learn all cases.

Let me do one more attempt at real communication. We like to play with sudokus. Some solve them by hand, some program. We need mechanisms to convey solution steps. There are many types of reasoning, and for some types of argument the nice loop notation is excellent. For other types it is lousy. Trying to force everything into this single notation is a bad idea. The present thread on triple chains shows how not to use nice loop notation.
Or maybe rather: the present thread proposes to extend nice loop notation in an unfortunate way. The proposed notation uses invalid chains (three chains of which two will be correct) and hides what is happening. Nice loops are not a religion (I hope) - the goal is to describe how a solution proceeds, in a clear and concise way.
aeb
 
Posts: 83
Joined: 29 January 2006

Next

Return to Advanced solving techniques