## chains

Advanced methods and approaches for solving Sudoku puzzles

### chains

bennys

Posts: 156
Joined: 28 September 2005

I'm not sure I follow this. Can you go over the logic of the test in a little more detail?
Lummox JR

Posts: 125
Joined: 22 September 2005

Yes
in the example if any cell other then A, B, C,D in that row is 1
then A=2 and B=3 and C=4 and D=5 but we can't have that because then
r1c5 and r1c7 are both 7.
bennys

Posts: 156
Joined: 28 September 2005

Here's a concrete example that illustrates a Tabling technique similar to that discussed by bennys. (Unfortunately, my solver can't crack the puzzle without a guess at a later stage).

Code: Select all
` . 8 . | . . . | . . 7  . 9 . | 8 . 3 | . 1 2  . . 2 | . 6 . | 8 . . -------+-------+------  . . . | . . 5 | . 9 8  . . 8 | . . . | 4 . .  . 6 . | 1 . 8 | . . . -------+-------+------  . . 4 | . 8 . | 2 . .  8 1 . | 9 . . | . 5 .  3 2 . | . . . | . 8 . `

Standard and slightly advanced (such as Fishy cycles) techniques take us so far:

Code: Select all
`        5|6        8  1|3|5|6 |      2|4|5    1|2|5|9    2|4|9 |  3|5|6|9    3|4|6        7     4|5|6|7        9    5|6|7 |          8      4|5|7        3 |      5|6        1        2       1|5|7  3|4|5|7        2 |      4|5|7          6  1|4|7|9 |        8      3|4    3|5|9 ------------------------------+--------------------------------+---------------------------         2|7    3|4|7    1|3|7 |  2|3|4|6|7      2|3|7        5 |  1|3|6|7        9        8   1|2|5|7|9    3|5|7        8 |    2|3|6|7    2|3|7|9  2|6|7|9 |        4  2|3|6|7  1|3|5|6   2|4|5|7|9        6  3|5|7|9 |          1  2|3|4|7|9        8 |    3|5|7    2|3|7      3|5 ------------------------------+--------------------------------+---------------------------     5|6|7|9      5|7        4 |    3|5|6|7          8    1|6|7 |        2    3|6|7  1|3|6|9           8        1      6|7 |          9      2|3|7  2|4|6|7 |    3|6|7        5    3|4|6           3        2  5|6|7|9 |    4|5|6|7      1|5|7    4|6|7 |  1|6|7|9        8    4|6|9 `

whereupon the solver points out:

Consider the chains r3c6-9-r3c9-9-r1c7-9-r9c7-1-r9c5 and r1c5-1-r1c3-3-r3c2~3~r3c8~4~r3c6.
When the cell r3c6 contains the value 4, one chain states that the value 1 in Column 5 belongs in the cell r9c5 while the other says it doesn't - a contradiction.
Therefore, the cell r3c6 cannot contain the value 4.

NB Here '~' represents a weak link [more than two candidates] and '-' represents a strong link [precisely two candidates].

The technique discussed by bennys is similar to Tabling, but not quite the same because the manner in which we deduce that, say, B=3 if some unlabelled cell in Row 4 is 1 doesn't quite correspond to a forced chain. E.g.

r4c2=1 => r4c1<>1 => r4c2=2 => r4c3<>2

Of course, we know that r4c3<>1, so we must have r4c3=3, but as I understand, in order to qualify for a forced chain, we must be able to infer that r4c3=3 purely from the previous assertion in the chain (r4c3<>2), which we can't here.

I imagine that the highly-specific nature of the technique introduced here will make it difficult to construct a concrete illustrative example.
Sue De Coq

Posts: 93
Joined: 01 April 2005