Nice loops for intermediate level players - Grouped x-cycle

Advanced methods and approaches for solving Sudoku puzzles

Postby Myth Jellies » Sun Mar 05, 2006 3:44 am

Jeff wrote:
Myth Jellies wrote:.....My issue is the "magic" conversion of the links along column 5 from an obvious pair weak link to a pair of strong links........Your magic conversion of the two weak links into two strong links is quite possibly legitimate as well.....

Hi MJ, In my deduction, there was only one strong link due to a multiple inference. Are you referring to the 2 end nodes and counting it two instead of one? The move may be regarded as a conversion, or a result of multiple inference.


Yes, my mistake on the assumption of two strong links. I thought you had a loop with two pathways instead of just a single loop. The comment is still valid for the one conversion though.

Jeff wrote:
Myth Jellies wrote:So, for your diagram, what I really want to know is what are the rules which allow you to convert weak links into strong links.

The simple rule of a strong inference applies: "if a candidate 'x' in the preceding nodes is false, then candidate 'x' in the following node is true".


Well, it seems the following set of starred cells would indicate that you do not have a strong link between r1c5 and r7c5.
Code: Select all
.  .  . | .  6  . | .  6  6*
.  .  . | .  .  6*| .  .  6 
.  .  6 | .  .  . | .  .  .
--------+---------+--------
.  6* . | 6  .  6 | .  .  6 
.  6  . | .  6* . | 6  6  .
.  .  . | 6  .  . | 6* .  .
--------+---------+--------
6* .  . | .  6  . | 6  .  6
6  .  . | 6* .  . | .  .  .
6  .  . | .  .  6 | .  6* .
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Sun Mar 05, 2006 6:02 am

Myth Jellies wrote:
Jeff wrote:The simple rule of a strong inference applies: "if a candidate 'x' in the preceding nodes is false, then candidate 'x' in the following node is true".

Well, it seems the following set of starred cells would indicate that you do not have a strong link between r1c5 and r7c5.
Code: Select all
.  .  . | .  6  . | .  6  6*
.  .  . | .  .  6*| .  .  6 
.  .  6 | .  .  . | .  .  .
--------+---------+--------
.  6* . | 6  .  6 | .  .  6 
.  6  . | .  6* . | 6  6  .
.  .  . | 6  .  . | 6* .  .
--------+---------+--------
6* .  . | .  6  . | 6  .  6
6  .  . | 6* .  . | .  .  .
6  .  . | .  .  6 | .  6* .

This link has 3 nodes, namely r1c5, r5c5 and r7c5, where the preceding nodes are r5c57 and the following node is r1c5 in the multiple inference net. However, if we make inferences in the opposite direction where the preceding node is r1c5 and the following nodes are r5c57, we will get a triple implication chain instead since r1c5<>6 implies r5c5=6 or r7c5=6, ie.

r2c6<>6 => r2c9=6 => r4c9<>6
r2c6=6 => r1c5<>6 => r5c5=6 => r6c4<>6 => r6c7=6 => r4c9<>6
r2c6=6 => r1c5<>6 => r7c5=6 => r7c7<>6 => r56c7=6 => r4c9<>6
Therefore, r4c9<>6

We know that the principle of the forcing chain technique is that when all implication streams force the same result, then that result must be valid, whether the implication streams are on the correct placement path or not. It happened that the implication streams of the multiple inference net are not on the correct placement path. Your diagram shows the correct placement path of digit 6 which is reflected by the triple chain above.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby ronk » Sun Mar 05, 2006 12:03 pm

Myth Jellies wrote:If you draw your picture like this...
Code: Select all
.  .  . | .  6d . | .  6  6
.  .  . | .  .  6c| .  .  6b
.  .  6 | .  .  . | .  .  .
--------+---------+--------
.  6  . | 6  .  6 | .  .  6a
.  6  . | .  6e . | 6h 6  .
.  .  . | 6f .  . | 6h .  .
--------+---------+--------
6  .  . | .  6e . | 6g .  6
6  .  . | 6  .  . | .  .  .
6  .  . | .  .  6 | .  6  .

...then you have...
Code: Select all
                  (row 5 e) - f
                 /             \
a - b = c - d = e                = h - a
                 \             /
                  (row 7 e) - g

I think "implication flow diagrams" can be very useful, but that one doesn't quite work. If 'd' is false, then only one of 'row 5 col 5 e' or 'row 7 col 5 e' can be true, which means either 'f' or 'g' is true. Consequently, the diagram implies 'h' would never be true.

A more logically correct diagram -- with most of the rXcX labels -- might be:
Code: Select all
                 r5c5 - r6c4 = r6c7
                //                  \
a - b = c - r1c5                     r4c9
                \\                  /
                 r7c5 - r7c7 = r56c7

Note the double '//' and '\\' (are meant to) illustrate multiple inference for a strong link. Left-to-right, if r1c5<>x then either r5c5=x or r7c5=x. Right-to-left, if r5c5<>x and r7c5<>x then r1c5=x.

Similarly, the single '/' and '\' illustrate multiple inference for a weak link. Left-to-right, if r6c7=x or r56c7=x then r4c9<>x. Right-to-left, if r4c9=x then r6c7<>x and r56c7<>x. Note the overlap of r6c7 and r56c7, while redundant for the right-to-left direction, is logically correct.

I won't attempt to illustrate the b/b plot for the above flow diagram.:)

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

Postby Myth Jellies » Sun Mar 05, 2006 9:50 pm

ronk wrote:
Myth Jellies wrote:
Code: Select all
                  (row 5 e) - f
                 /             \
a - b = c - d = e                = h - a
                 \             /
                  (row 7 e) - g

I think "implication flow diagrams" can be very useful, but that one doesn't quite work. If 'd' is false, then only one of 'row 5 col 5 e' or 'row 7 col 5 e' can be true


Yes, if 'd' is false, then the strong link between 'd' and grouping 'e' implies that 'e' is true. Only one of the components of group 'e' must be true.

ronk wrote:, which means either 'f' or 'g' is true. Consequently, the diagram implies 'h' would never be true.


:(I don't agree here. There are only weak links between the components of 'e' and either 'f' or 'g'. Thus, one of the components of 'e' being false in no way implies that either 'f' or 'g' is true. I don't think the diagram implies anything about 'h' never being true.

ronk wrote:A more logically correct diagram -- with most of the rXcX labels -- might be:
Code: Select all
                 r5c5 - r6c4 = r6c7
                //                  \
a - b = c - r1c5                     r4c9
                \\                  /
                 r7c5 - r7c7 = r56c7

Note the double '//' and '\\' (are meant to) illustrate multiple inference for a strong link. Left-to-right, if r1c5<>x then either r5c5=x or r7c5=x. Right-to-left, if r5c5<>x and r7c5<>x then r1c5=x.

Note that these equations are precisely what you would expect if you treated r57c5 as a group.

ronk wrote:Similarly, the single '/' and '\' illustrate multiple inference for a weak link. Left-to-right, if r6c7=x or r56c7=x then r4c9<>x. Right-to-left, if r4c9=x then r6c7<>x and r56c7<>x. Note the overlap of r6c7 and r56c7, while redundant for the right-to-left direction, is logically correct.

I don't think we have any issue over this part of the diagram.

Anyway, other than the disagreement over the validity of my diagram, I think we are practically on the same page. I'm just pointing out that I think you can consider the r57c5 grouping (which I understand) and avoid the whole multiple inference concept (which I don't really understand) here.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Sun Mar 05, 2006 10:28 pm

Myth Jellies wrote:
ronk wrote:, which means either 'f' or 'g' is true. Consequently, the diagram implies 'h' would never be true.


:(I don't agree here. There are only weak links between the components of 'e' and either 'f' or 'g'. Thus, one of the components of 'e' being false in no way implies that either 'f' or 'g' is true. I don't think the diagram implies anything about 'h' never being true.

OK, I think I see what you mean. For the strong inference ...

(row 7 e) - g

... if (row 7 e) is false, there is no true/false propagation to 'g'. Indeed, I suppose 'g' could be defined to be false in that case ... and then, 'f' and 'g' might as well be grouped too. That would really look weird on a b/b plot.

Maybe we're trying too hard to make a nice loop fit this scenario.

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

Postby Myth Jellies » Mon Mar 06, 2006 12:51 am

ronk wrote:Maybe we're trying too hard to make a nice loop fit this scenario.


Perhaps, but what else have we got to do. Maybe my diagram looks better with colors:)

Anyway, I think what you and Jeff mean by multiple inference is basically equivalent to what I mean when I treat a set of cells as a grouping from one direction and as individual cells from the other direction. Either way looks messy in a diagram.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Jeff » Mon Mar 06, 2006 4:46 am

Hi MJ and Ronk.

I have modified the nice loop notation in the original post to improve the expression of the logic. Basically a bracketed node (r5c5) is added to represent the grouped nodes (different to grouped cells which is just one single node) which enables the strong inference in question to take place. With this modification, the multiple inference of the nice loop notation is bi-directional. All you have to do is to link the same bracketed node when reading in either direction.

[r4c9]-6-[r56c7](=6=[r6c4]-6-[r5c5])=6=[r7c7]-6-[r7c5|(r5c5)]=6=[r1c5]-6-[r2c6]=6=[r2c9]-6-[r4c9] => r4c9<>6
Last edited by Jeff on Sat May 13, 2006 4:06 am, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby aeb » Mon Mar 06, 2006 6:00 am

Myth Jellies wrote:
ronk wrote:Maybe we're trying too hard to make a nice loop fit this scenario.

Perhaps, but what else have we got to do.

Jeff said: [r4c9]-6-[r56c7](=6=[r6c4]-6-[r5c5])=6=[r7c7]-6-[r7c5(r5c5)]=6=[r1c5]-6-[r2c6]=6=[r2c9]-6-[r4c9]
That is precisely equivalent to:
"Suppose (4,9)6. Then first of all (4,9)6 > (6,7)!6 > (6,4)6 > (5,5)!6.
And given that, (4,9)6 > (56,7)!6 > (7,7)6 > (7,5)!6 > (1,5)6 > (2,6)!6 > (2,9)6 > (4,9)!6."
It is not necessary to write the entire argument as a single impenetrable string.
The diagram is non-linear, the argument is non-linear, no need to write is as a single line.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby Jeff » Mon Mar 06, 2006 6:39 am

aeb wrote:It is not necessary to write the entire argument as a single impenetrable string.
The diagram is non-linear, the argument is non-linear, no need to write is as a single line.

This is the beauty of the nice loop notation because it can do what other notations can't. One line expression for 2 implication streams.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Previous

Return to Advanced solving techniques

cron