Sudoku Players' Forum (clone)

To give back some credibility to the name "double forcing chains" here is a (very hard) problem that requires, among the other things, the use of three implication chains to prove a possibility.

Code: Select all

..8.2.7.1
.346.....
9........
.....5...
..2.1.8..
...4.....
........5
.....742.
7.1.8.3..

I can't solve this without recourse to Nishio - please explain.

Nick, can you clarify your terminology? I believe a "double implication chain" and a plain forcing chain are the same thing, from slightly different points of view. If they mean different things to you, what are they?

I think I understand what a "triple implication chain" is from other postings. Is your "double forcing chain" the same thing as a triple implication chain? If not, what is it? (And if so, why the name? ) Thanks.

This is the triple forcing chain required:

Code: Select all

56     56     8       | 39     2      349     | 7      349    1     
12     3      4       | 6      7      19      | 5      8      29     
9      12     7       | 8      5      134     | 26     346    234   
----------------------+-----------------------+----------------------
148    178    369     | 2      369    5       | 69     14     47     
3456   569    2       | 7      1      369     | 8      3456   346   
1356   17     3569    | 4      369    8       | 269    1356   2367   
----------------------+-----------------------+----------------------
28     28     369     | 39     4      369     | 1      7      5     
356    569    3569    | 1      369    7       | 4      2      8     
7      4      1       | 5      8      2       | 3      69     69     

r4c5=9 => r5c6<>9 => r5c2=9
r6c5=9 => r5c6<>9 => r5c2=9
r8c5=9 => r8c2<>9 => r5c2=9
  - Put 9 in r5c2

About forcing chains and double forcing chains, I posted here a proof that they are the same thing.

Nick70 wrote:About forcing chains and double forcing chains, I posted here a proof that they are the same thing.

Righto. Calling a forcing chain a "double implication chain" (when you start from the middle and follow 2 exhaustive implications) is reasonable. But calling it "double forcing chain" is a misnomer and confusing terminology. There's a double implicaiton if you dice it from the middle, but there's no double forcing, just one thing being forced.

In your example here (thanks!), I'd recommend a name like "triple implication chain" or "forcing net". No single "chain" in this example forces a useful deduction by itself, it just makes an implication. It requires the "triple implication" from 3 exhaustive possibilities, a type of "net", to combine the pieces and force a deduction.

Here is a sligtly alternative argument, based on Simple Colouring:

Filter on 9s and colour the conjugate chain: r8c2(Green)-r5c2(Red)-r5c6(Green).

Observe the weak links:
r4c5-r5c6(Green), r6c5-r5c6(Green), r8c5-r8c2(Green).
(Weak link: If one is true, the other is false)

Conjecture: Since all cells with candidate 9 in c5 are weakly linked to green cells in the conjugate chain, green can not represent 9, and all red cells can safely be set to 9.

More generally:

Conjecture: If all cells with candidate x in a unit are (weakly) linked to same-coloured cells in a conjugate chain (for the same candidate x), this color represents the false cells for x.

Ocean wrote:Conjecture: Since all cells with candidate 9 in c5 are weakly linked to green cells in the conjugate chain, green can not represent 9, and all red cells can safely be set to 9.

Excellent observation!

Seconded

Thank you!
I wonder if the second (general) conjecture is true. To me it seems rather obvious, but I havent't seen it described explicitly. Or is it plain trivial and in fact a subset of other common solving methods or algorithms?

Ocean wrote:I wonder if the second (general) conjecture is true.

Yes, I'm confident it is true, though I'd express it a little differently. I'd avoid using the term 'weak link' as it needs its own definition.

Ocean wrote:To me it seems rather obvious, but I havent't seen it described explicitly. Or is it plain trivial and in fact a subset of other common solving methods or algorithms?

No, it's not trivial. It's certainly a subset of the more general coloring technique but I haven't this particular method documented before.

Ocean wrote:More generally:

Conjecture: If all cells with candidate x in a unit are (weakly) linked to same-coloured cells in a conjugate chain (for the same candidate x), this color represents the false cells for x.

Yes, true conjecture. If that color were the true cells in the coloring it would exlude all x's from the unit, leaving no solution possible. Nice observation!

angusj wrote:I'd avoid using the term 'weak link' as it needs its own definition.

What would you suggest as substitutions for the terms 'strong link' and 'weak link'?

BTW, another alternative argument can be established using a double implication colour chain of 9s.

r5c2=9 => r4c3 & r6c3 <>9
r5c6=9 => r4c5 & r6c5 <>9 => r8c5=9 => r7c4 & r7c6 <>9 => r7c3=9 => r4c3 & r6c3 <>9
Therefore, r4c3 & r6c3 <>9

Jeff wrote:What would you suggest as substitutions for the terms 'strong link' and 'weak link'?

I have nothing against these terms but they do need to be clearly defined if they're used as they may mean different things to different people.

I think there is growing agreement though that 'weak link' refers to two cells which have a common candidate - the logical implication being that if that candidate is assigned to one cell it can be excluded from the other.

...where the trilocation graph method actually does work. (Although only in retrospect, since I know Nick70's solution)

All you need is two triangles and two additional edges from the bilocation graph.

I'll try to draw it in ASCII

o--9--o-----o
|.........\. 3.. |.\
|..........\.6.. |...\
9...........\.9.|..3.\
|...............o...6.\
|.................\..9.|
o..................\ o

The dots should actually be just spaces.

Since this looks very ugly let me explain:

the vertex in the upper left corner is just the cell r5c2

the two edges are from the bilocation graph, with label 9

the two, er, triangles are from the trilocation graph, meaning that at the three vertices only the numbers in its area may be placed (in the particular case always the three numbers 369)

now you have an example for conflicting paths:

start in r5c2 - if 9 is NOT placed there the bilocation path that leads downwards pushes the 9 into r8; the other path pushes the 9 to the tip of the triangle - but that means its other two vertices must be 3 and 6; but these two vertices are also vertcies of the second triangle; therefore, the third vertex of the second triangle must be a 9 - but this 9 is also located in r8, which establishes conflicting paths, and thus the 9 must be placed in r5c2

but I assume that I am just rephrasing geometrically in a roundabout manner what Nick70's multiple forcing chain establishes... or the mysterious colouring method

still, for solving by hand (and if you are good with pictures both in terms of drawing and looking at them) the trilocation methods might be useful

but this is where I draw the line - no quadrilocation graphs with tetraeders for me, please - I am already struggling with 2 dimensions...

angusj wrote:I think there is growing agreement though that 'weak link' refers to two cells which have a common candidate - the logical implication being that if that candidate is assigned to one cell it can be excluded from the other.

In other words, a weak link between 2 cells simply means that the 2 cells are in the same unit. Therefore,

Code: Select all

..............is weakly linked to the other cell ...........

can be expressed as

Code: Select all

..............is in the same unit with the other cell...........

And, a strong link between 2 cells simply means that the 2 cells are in the same unit and have a conjugate relationship. Therefore,

Code: Select all

..............is strongely linked to the other cell ...........

can be expressed as

Code: Select all

..............is in the same unit and has a conjugate relationship with the other cell...........

Thus, avoiding the use of 'weak' and 'strong'