## weak chains

Advanced methods and approaches for solving Sudoku puzzles

### weak chains

What i call a weak chain now, is a generalization of both Nick70's turbot fish and simple colouring, in the sense that the technique solves all what both can solve (but of course its not that "user friendly").
In another thread i already posted that what turbot fish can solve, can be reduced to what a chain A-B~C-D for one colour can solve, where A-B and C-D are conjugated pairs (strong sides) and B~C is a weak (or like) link (that meens, they are in the same row/col/box). If you have this chain, you can eliminate the colour from all "intersections" of A and D (cells which have both a common row/col/box with A and a common row/col/box with D, i.e. have a weak link to both A and D), because either A and D must have the color (if not, both B and C would have, but they share a row/col/box).
The generalization is simply that you can build longer chains with alternate strong and weak links and can eliminate the colours that intersect the first and last cell. It's easy to see that this holds: If you add 2 nodes for a chain A-B~C-D~E-F and F would not have the colour, then E must have it and not D, which is the situation above.
Obviously this solves turbot fish patterns, because A-B~C-D is a weak chain. It solves colouring patterns, because if you have a "strong" chain A1 to An and can eliminate a colour, because a cell is intersecting Ai and Aj, then Ai through Aj also is a weak chain.

So far i dont have a sample, that is not solvable with other techniques, but i think the following puzzle is interesting for its own:

39.|..4|7..
...|..8|...
.5.|.9.|.2.
-----------
.12|75.|.9.
7..|.1.|5..
9..|..2|6..
-----------
...|6..|8..
...|.8.|.51
..4|..5|..3

With a turbot fish in 1 you can put 3 in (3,4) and you come to here:

3___9__16____12__26_4____7__8_5_
2___4__67____5___67_8____19_3_69
18__5__678___3___9__17___14_2_46

4___1__2_____7___5__6____3__9_8_
7___6__38____89__1__39___5__4_2_
9___38_5_____48__34_2____6__1_7_

5___2__139___6___34_139__8__7_49
6___37_39____24__8__379__24_5_1_
18__78_4_____129_27_5____29_6_3_

You can solve it now with the xy wing in (2,7),(2,9),(3,7),(3,9)

The solution with a weak chain in 1 needs a long way:
(2,7)-(3,7)~(3,6)-(7,6)~(7,3)-(1,3)~(1,4)-(9,4)~(9,1)-(3,1)
(only the second side is really weak)
So you can eliminate 1 from (3,7)
Last edited by Wolfgang on Mon Aug 08, 2005 5:28 am, edited 3 times in total.
Wolfgang

Posts: 208
Joined: 22 June 2005

sorry Nick70 - turbot fish
Wolfgang

Posts: 208
Joined: 22 June 2005

### Re: weak chains

This is solvable using multiple colors too:

Looking at 1s ...
Code: Select all
`..C|D..|... A..|...|... ...|...|... -----------...|...|... ...|...|... ...|...|... -----------..A|...|... ...|...|... B..|A..|... `

AB are conjugates as are CD. Since either C or D must be 1 and both C & D also share a group with A - A must be the 'false' conjugate.

Edit: Here's another way of reaching the same conclusion ...

Code: Select all
`...|...|... A..|...|C.. ...|..A|D.. -----------...|...|... ...|...|... ...|...|... -----------..A|..B|... ...|...|... B..|A..|...`
angusj

Posts: 306
Joined: 12 June 2005

### Re: weak chains

angusj wrote:This is solvable using multiple colors too:

Looking at 1s ...
Code: Select all
`..C|D..|... A..|...|... ...|...|... -----------...|...|... ...|...|... ...|...|... -----------..A|...|... ...|...|... B..|A..|... `

Of course, because this is a turbot:

Code: Select all
`..C|D..|... A..|...|... ...|...|... -----------...|...|... ...|...|... ...|...|... -----------...|...|... ...|...|... B..|A..|... `

the other one, however, isn't.
Nick70

Posts: 156
Joined: 16 June 2005

### Re: weak chains

Wolfgang wrote:The generalization is simply that you can build longer chains with alternate strong and weak links and can eliminate the colours that intersect the first and last cell.

One thing that perhaps I haven't made very clear when talking about forcing chains, is that the alternation of strong and weak links is the fundament of its power. In fact, I always write chains with this notation:

Code: Select all
`(6,8)=5 => (6,8)<>2 => (6,5)=2 => (1,5)<>2 => (1,3)=2(2,8)=5 => (2,5)<>5 => (2,5)=2 => (1,5)<>2 => (1,3)=2`

Each transition from = to <> is a weak link, each transition from <> to = is a strong link. It is of course not necessary for weak links to be weak, they could also be strong but their strongness is not needed for the chain to work.

I posted a description of an algorithm to find forcing chains here.

What you are describing, if I'm not mistaken, is a subset of forcing chains where you are limiting to a single number. I studied that, by adding the limitation to the forcing chains algorithm, but I wasn't satisfied with the results because usually you could find a long single-number chain but also a much shorter unconstrained chain, and the latter just seemed simpler.

It's true, however, that you can get to the single-colored chain by using simple coloring (assigning a color to whole cells), while to use coloring for the more general chains you need to color the single pencilmarks - that's the reason I've been hassling AngusJ to add that feature to Simple Sudoku
Nick70

Posts: 156
Joined: 16 June 2005

### Re: weak chains

Nick70 wrote:What you are describing, if I'm not mistaken, is a subset of forcing chains where you are limiting to a single number.

After i had a look to your link now, i would agree, although it is rather hard to read that out of it.

Anyway there is another puzzle for weak chains or forcing chains:
090|007|500
800|000|020
045|020|709
-----------
020|004|300
016|530|800
000|800|000
-----------
039|001|070
060|300|205
000|470|000

There is a closed chain in 4, so the starting and end point must be 4.
Wolfgang

Posts: 208
Joined: 22 June 2005

I have to know (not being piscatorially-minded in any way) - is there such a thing as a Talbot fish?

Would it live on the Horizon?!

AHAHAHAHHAAAAHAAHAAAAHAHAHAhhahhaahaaaa......hahaa....ha.....

Sorry. Stella 'gain.
Karyobin

Posts: 396
Joined: 18 June 2005

Karyobin wrote:..is there such a thing as a Talbot fish?

there was, it lived on morbid brain cells, but it was an evolutionary mistake and died out again
Wolfgang

Posts: 208
Joined: 22 June 2005

Wolfgang wrote:... died out again:)

again?!
Last edited by simes on Sun Dec 11, 2011 9:26 am, edited 1 time in total.
simes

Posts: 324
Joined: 11 March 2005
Location: UK

I'm gonna get all interleckshully superior now...

Wolfgang wrote:it was an evolutionary mistake and died out again

There's no such thing as an evolutionary mistake. That would be to suppose all stages of evolution are striving toward some goal and, well, they're just not.

"All creatures that have ever existed have been perfectly adapted to their environment" - Henry Gee, Deep Time (Paraphrased slightly).

But you don't have to listen to me, I'm just an ex-maths teacher. I quit last week 'coz I wasn't perfectly adapted to it.
Karyobin

Posts: 396
Joined: 18 June 2005