Chains and Link are fundamental to many solving strategies and in this article I hope to draw together the ideas from all chaining strategies to show how chains and links can be identified and used. From chains we can deduce eliminations - but to build chains we need some logical building blocks to get us from one point on the board to another so we can say 'ah ha!' that IS connected to that, therefore....
We have a number of ways to build chains from different types of links. These vary in sophistication and define the difference between strategies. The goal is to discover a pattern on the board which leads to a contradiction or a positive or negative confirmation of a candidate.
So lets dive in
Bi-Location Links
In the first diagram I show a distribution of the candidates for number 3.
Drawn in blue and green are the possible links between certain candidates. The commonality is that some of these rows, columns and boxes there are only two candidates left. This means that one or other of these candidates will be the solution. We don't know which but each link described an EITHER / OR relationship. I've shown in green the links within a box, but often the link could be in a row or column AND a box, but it's not relevant which type of unit if the link is in both.
Links of this type are called Bi-location links, because the link is across two cells.
Bi-Value Links
In the next diagram I have picked a random Sudoku from my solver examples and highlighted all the cells with two remaining candidates. These cells are extremely useful and will play a huge part in most chaining strategies. Because each yellow cell has only two candidates left, we know one or other will be the solution and exactly the same EITHER / OR relationship is present.
Such cells are known as Bi-value links. (Both bi-value and bi-location candidate pairs are also known as conjugate pairs (or complementary pairs) but these are term I am moving away from).
I don't need to draw a link between each pair value in each cell, it is implied by the nature of the two candidates in each cell.
Either / Or
The beauty of a chain is that it will resolve into one of two states. In this diagram I have a simple 5 cell chain. The links could be across rows, columns, boxes (bi-location) or within a cell (bi-value), it doesn't matter. The point, that when we get to the solution either the bottom left part of the diagram will come true or the bottom right: that is, one set of cells will be ON (the solution) and set will be OFF (not the solution). Note that the ON/OFF alternates. Pretending to set the state of any of the chain candidates to ON or OFF automatically sets the state of the rest of the chain.
Chains, Loops and Nets
Chaining strategies can be divided into two types: whether they use a linear chain or a spreading network-like pattern. Linear chains have a start and end and do not branch out. A 'net'-like strategy such as 3D Medusa takes advantage of all the chains possible on the board. Obviously a net of chains contains lots of small linear chains in many combinations.
At any stage of the puzzle there should be several if not many possible chains. Only a few of them will be useful. Chains may not be connected, that is there is no bi-value or bi-location connection between two chains. Multi-Colouring takes advantage of two isolated chain nets. Forcing Chains take advantage of two or more linear chains to make an elimination.
Loops are linear chains with no start or end, or at least the start and end are arbitrary. The top left most candidate is used to express a definition of a Loop, which you will see as part of the solver output.
The Chaining Strategy Family
The table below groups the strategy according to the use of bi-value and bi-location links and whether linear or net-like chains are used. I also introduce Strong and Weak links in the next section.
The strategies listed to the right use only bi-location links. Effectively that means they stick to one number and ignore all other numbers. You can think of them as working within one plane or dimension.
These strategies use bi-value AND bi-location links. Whereas the strategies before stick to one number these can move between number plains using bi-value cells and are hence 'two dimensional'.
Bi-value and Bi-Location links are not the end of the story. Chains that stick to only conjugate pairs are rather limited - but they are much easier to spot. You will be making good use of X-Wings, Y-Wings, XY-Chains and simple colouring to defeat moderately difficult puzzles. But to get the most out of chains we need to understand Alternating Inference Chains. These are well documented but first you should read the continuing article on Strong and Weak links.
When I enter the puzzle and the solver enters the possibles some of them are shown in red, whilst the majority are black. Is there some significance to this ? I have looked but cannot see an explanation anywhere.
Dave
Andrew Stuart writes:
No significance. I think what you did was enter a number and then delete it. Clues use a red font and it merely retained the red when it drww the candidates. It will go black if refreshed.
Thursday 4-Jul-2013
... by: Y.Sato
Please explain, why the cell C2 (1,4), and E2 (4,6) have been highlighted in the write-up for Bi-Value links. Thanks.
Andrew Stuart writes:
This diagram merely highlights all bi-value cells, and C1 and E2 are example of such
Monday 18-Mar-2013
... by: Monty
Just a question regarding these links. The first diagram on this page with the threes, should the top pair of threes and the bottom left pair of threes have green lines between them rather than blue, based on your statement that you use green links within a box?
I had a Sudoku which the solver marked two numbers in a row each of which had two other of that number in their respective columns as well as their respective boxes, but did not color either end of the link. Should the link have actually been drawn or do they only count if they contain three or more connections?
Would it be correct to say a link must always change direction from cell to cell, ie if the first link is horizontal (row) the next must be vertical (column) or diagonal (box)?
Comments
Comments TalkThursday 5-Sep-2013
... by:
AndrewCongratulations on your excellent site.
When I enter the puzzle and the solver enters the possibles some of them are shown in red, whilst the majority are black. Is there some significance to this ? I have looked but cannot see an explanation anywhere.
Dave
Thursday 4-Jul-2013
... by: Y.Sato
Please explain, why the cell C2 (1,4), and E2 (4,6) have been highlighted in the write-up for Bi-Value links. Thanks.Monday 18-Mar-2013
... by: Monty
Just a question regarding these links. The first diagram on this page with the threes, should the top pair of threes and the bottom left pair of threes have green lines between them rather than blue, based on your statement that you use green links within a box?I had a Sudoku which the solver marked two numbers in a row each of which had two other of that number in their respective columns as well as their respective boxes, but did not color either end of the link. Should the link have actually been drawn or do they only count if they contain three or more connections?
Would it be correct to say a link must always change direction from cell to cell, ie if the first link is horizontal (row) the next must be vertical (column) or diagonal (box)?