Uniqueness chains

A uniqueness chain is a chain of any number of non-given numberpairs, whose placings are only determined by other members of the chain, and therefore can be reversed without affecting the rest of the puzzle. The appearance of any such chain can, and must, safely be prevented from happening in any puzzle with one unique solution.

The chains can be built out of three different straight chains that can be combined with cornerblocks. The three different straight chains are:

A) Two pairs (also known as uniqueness squares):

- Code: Select all
`.. .. ab|ab .. ..`

.. .. ab|ab .. ..

.. .. ..|.. .. ..

B) Three pairs with three different numbers:

- Code: Select all
`.. .. ab|ac .. ..|.. bc ..`

.. .. ab|ac .. ..|.. bc ..

.. .. ..|.. .. ..|.. .. ..

C) Three pairs with two different numbers:

- Code: Select all
`.. .. ab|ab .. ..|.. .. ..`

.. .. ab|.. .. ..|.. ab ..

.. .. ..|ab .. ..|.. ab ..

The last applies to any situation where two numbers a and b are would be forced into the same column in each of three boxes next to each other or the same row in each of three boxes on top of each other:

[edit: in all my examples UPPER case letters represent GIVENS and lower case letters possible candidates.]

- Code: Select all
`*--------------------------*`

|.. .. ab|ab .. ..|.. ab ..|

|.. .. ab|ab .. ..|.. ab ..|

|.. .. ab|ab .. ..|.. ab ..|

|--------------------------*

| A .. ..|.. .. ..| B .. ..|

|.. B ..|.. A ..|.. .. ..|

|.. .. ..|.. .. B| A .. ..|

|--------------------------|

| B A ..|.. .. ..|.. .. ..|

|.. .. ..|.. B ..|.. .. A|

|.. .. ..|.. .. A|.. .. B|

*--------------------------*

Any placement of numbers a and b would eventually lead to a situation similar to C) => the situation cannot come up in any valid puzzle.

The cornerblock is a box that contains a diagonal pair that acts as a link in both chains.

D) Two 2-pair chains connected:

- Code: Select all
`ab .. ab|.. .. ..`

.. .. ..|.. .. ..

.. .. ..|.. .. ..

-----------------

ab .. ..|.. .. ab

.. .. ..|.. .. ..

.. .. ab|.. .. ab

E) Two 3-pair chains connected:

- Code: Select all
`*--------------------------*`

|ab .. ab|.. .. ..|.. .. ..|

|.. .. ..|.. .. ..|.. .. ..|

|.. .. ..|.. .. ..|.. .. ..|

|--------------------------*

|.. .. ..|.. .. ..|.. .. ..|

|.. .. ab|.. .. ac|bc .. ..|

|.. ab ..|.. .. ac|bc .. ..|

|--------------------------|

|.. .. ..|.. .. ..|.. .. ..|

|.. .. ..|.. .. ..|.. .. ..|

|ab ab ..|.. .. ..|.. .. ..|

*--------------------------*

As we can see from figure E), cornerblocks may connect chains of different types and may connect chains involving different numbers. We can also see that a cornerblock may exist in the middle of a chain.

What we are interested about as solvers are chains that are almost completed:

F)

- Code: Select all
`*--------------------------*`

|.. A ..|.. .. ..| B .. ..|

|.. B ..|.. .. ..|.. A ..|

|.. .. ..|.. A B|.. .. ..|

|--------------------------*

|ab .. ab|.. .. ..|.. .. ..|

| X .. X| A .. ..|.. .. ..|

|.. .. ..| B .. ..| A .. ..|

|--------------------------|

| X .. ab|.. .. ..|.. X ab|

|.. .. ..|.. B A|.. .. ..|

|ab .. X|.. .. ..|.. b ab|

*--------------------------*

In the example above (x stands for any number other than a or b) the uniqueness chain is only one step from forming. All members except one, the b in box 9, are already forced into position. In this case we can safely remove b as a candidate in (7,9)* and (9,9) as this is the only way to prevent the chain from forming.

*I define squares (row,column), (7,9) = r7c9

Before we look at more complicated situations, we must make some further observations about the pairs in a chain.The pairs can be divided into strong links and weak links. A strong link is a link that cannot break the uniqueness chain, the candidates are already forced into place. A weak link has at least one optional solution. In example F) boxes 4 and 7 contained strong links, leaving only one weak link in box 9 => We solved it by breaking the chain at the weak link.

At the end of the chain or in the middle of a straight three pair chain a strong link occurs when the two digits involved are forced into a pair in the same column/row (or any three spaces within the same row/column if the chain is of type C)). This means that any pair within the same row/column inside a box is a potentional strong link in an uniqueness chain. The most common use of this technique is when we have one such pair formed and we can see that a inserting a number at some certain point of the puzzle would lead to another strong link of the same numbers forming against it, completing a two pair uniqueness chain => we can rule out that option.

In a cornerblock a strong link occurs when the two digits involved are forced into a 2x2 area that coinsides with the chains on both sides. To explain this I’ll bring back example F) but this time I’ll remove the X:s from boxes 7 and 9:

G)

- Code: Select all
`*--------------------------*`

|.. A ..|.. .. ..| B .. ..|

|.. B ..|.. .. ..|.. A ..|

|.. .. ..|.. A B|.. .. ..|

|--------------------------*

|ab .. ab|.. .. ..|.. .. ..|

| X .. X| A .. ..|.. .. b|

|.. .. ..| B .. ..| A .. ..|

|--------------------------|

|ab .. ab|.. .. ..|.. b ab|

|.. .. ..|.. B A|.. .. ..|

|ab .. ab|.. .. ..|.. b ab|

*--------------------------*

Now we have a number of different placements for a and b in box 7. First of all, the available candidates do not require them to be diagonal. But, placing them in the same row would complete a 2-pair uniqueness chain with the pair of row 4. Placing them in the same column is impossible, as that would force both numbers a and b into the same square of box 4. This leaves us with two possible diagonal placings, both of which would satisfy the uniqueness chain, if it was completed => the corner block is a strong link. Once again we only have one weak link, box 9. This time we can’t tell exactly where to place the b in box 9, but we can rule it out from (7,9) and (9,9), leaving (5,9) as the only available candidate b in column 9.

If the cornerblock links a chain of type C) to a chain of type A) or B), the strong link occurs if the candidates are forced into a 2x3 area that coincide with the two chains:

H)

- Code: Select all
`*--------------------------*`

|ab ab ab| C .. ..|.. .. ..|

|.. .. ..|.. A ..|.. .. B|

|.. .. ..| B .. ..|.. A C|

|--------------------------*

|.. .. ..|.. .. B| c .. A|

|ab ab ab|.. .. ac|bc .. ..|

|ab ab ab|.. .. ac|bc .. ..|

|--------------------------|

|.. .. ..| A .. ..|.. B ..|

|.. .. ..|.. B ..| A C ..|

|ab ab ab|.. C ..|.. .. ..|

*--------------------------*

In this example there is a lot of different possibilities for a and b in square 4. However, we can rule out the possibility of them being in the same column, as this would complete a 2-pair uniqueness-chain between boxes 1 and 7 (and a 3 pair uniqueness chain with boxes 4 and 5 if it was completed). We can also rule out the possibility of them being in the same row , as this would complete a type C) uniqueness chain with boxes 1 and 7. This leaves us with 6 different diagonal options, all of which would satisfy an uniqueness chain similar to figure E) if it was completed => box 4 is a strong link => there is only one weak link in the chain, which can only be broken by placing c in (4,7).

A cornerblock connecting two type C) chains is always a strong link, as it is enough that you get the 2 candidates forced into a 3x3 area of the box. This tells us that we have enough information here to solve b in box 9:

I)

- Code: Select all
`*-----------*`

|...|.A.|B..|

|...|...|...|

|...|..B|.A.|

|-----------|

|...|...|...|

|...|...|...|

|...|...|...|

|-----------|

|...|...|A.X|

|...|.BA|...|

|...|...|..X|

*-----------*

This is basically all I’ve found out so far about the techinque. There is of course still some special situations, like the uniqueness circle that basicly consists of 4 cornerblocks.

J)

- Code: Select all
`ab .. ab|ab .. ab`

.. .. ..|.. .. ..

ab .. ab|ab .. ab

-----------------

ab .. ab|ab .. ab

.. .. ..|.. .. ..

ab .. ab|ab .. ab

With this knowledge of strong and weak links we can tackle very long chains:

K)

- Code: Select all
`*-----------*`

|..X|..A|..X|

|..A|...|..X|

|B..|..D|A.C|

|-----------|

|...|X..|.AX|

|...|.B.|.C.|

|...|A..|..X|

|-----------|

|.B.|.A.|C.D|

|..X|DX.|...|

|...|XX.|...|

*-----------*

This looks hopeless, so let’s write in the candidates:

L)

- Code: Select all
`*--------------------------*`

|cd cd X|bc .. A|bd bd X|

|cd cd A|bc .. ..|bd bd X|

| B .. ..|.. .. D| A .. C|

|--------------------------*

| d d bc| X cd ..|bd A X|

|ad ad ..|.. B ..| d C ..|

| d d bc| A cd ..|bd bd X|

|--------------------------|

|.. B ..|.. A ..| C .. D|

|ac ac X| D X bc|.. .. ab|

|ac ac D| X X bc|.. .. ab|

*--------------------------*

This still looks hopeless, but let’s try to read it starting from box 9, going left. Here it is apparent that we have a type B) chain with one closed end and a cornerblock* at the other end. All links are strong. Looking up from box 7 tells us that we have another type B) chain with two strong cornerblocks at the end and one weak link in the middle. Now we are in box one and continue following the chain right. Here’s a third type B) chain starting and ending with a cornerblock, all links are strong. From box 3 we look down and see a weak cornerblock, which mean this is a type A) chain, both pairs are cornerblocks, one is weak. Going left again from box 6 we see a type B) chain that starts with this weak cornerblock and finally closes the chain at the end. Now we can conclude that we have a 10-pair uniqueness chain with eight strong links and two weak links.

Two weak links? How can we know where to break the chain? Well, in this case it is quite easy. First, remove candidate d from (6,7) as this would complete the bcd uniqueness chain in boxes 4-5-6. Now there is 3 possible squares left for d in box 7, two of which would make the link strong, (4,7) and (6,8). At this point we can see that placing d in any of those squares would, together with the d in box 5, also enforce the a-d link in box 4, thus completing the chain. Conclusion: If the link in box 6 is strong, all links in the chain are strong** => box 6 must be weak, we place d in (5,7). Quite a lot of work for one number, but that is still one number more than one could ever solve with any other technique.

* Of course, we don’t know yet that it is a cornerblock. It becomes a cornerblock only when we find that the chain continues. If we found that the chain doesn’t continue, it wouldn’t be a strong cornerblock, but a weak endingblock.

** The first step (removing d from (6,7)) was actually unnecessary, as it would also satisfy the final conclusion. We could have solved it directly by noticing that placing d in any square that satisfies the strong links in boxes 4 or 6, would force the d in the other of these boxes into the strong link as well. I removed the candidate only to focus your attention on one chain. In fact, placing d in (6,7) would lead to two completed uniqueness chains, one in boxes 4-5-6 and another in boxes 9-8-7-4-1-2-3.

That's it. Comments anybody?

I've made some related problems that can be found at http://www.sudoku.org.uk/discus/messages/1/679.html?1142353323 if anybody is interrested.