Single's Chains, also known as Simple Colouring is a chaining strategy and part of a large family of such strategies. 'Simple' refers to the idea that one candidate number is considered - in contrast to 'multi-colouring' which is the basis of 3D Medusa. Single's Chains also related to X-Cycles.
A 'chain' is a series of links hopping from one candidate to another following very simple rules. A candidate can either be ON or OFF. That is, we either think it is a possible solution to that cell, or we do not. There are consequences to the rest of the board when we 'link' these two states. When we are starting out we don't know which will be ON or OFF so any two colours will do.
On this board I have clicked on 5 in C8 to highlight all the 5s in the puzzle. From this it is possible to map all the possible chains. These are between 5s where there are only two remaining 5s left in any row, column or box. The technical term for these are 'bi-location' links. Where there are three or more 5s - for example in box 1 and box 6, no links are possible within those boxes. But there are plenty about.
Now, the Colouring aspect which sometimes gives this strategy its name, is illustrated in the Rule 2 diagram below. Each end of each link can be assigned a colour. You can start in any position, taking any 5 on the board and give it a colour. If you follow each chain link, alternate the colours. The strategy is all about recognising that one of those colours will be the solution and the other not. The rules that follow identify the contradictions that allow us to eliminate candidates or decide which colour (which end of every link) is the solution.
Just a note on rule numbers: The solver uses the same search algorithm for both Singles Chains and 3D Medusa so I have synchronised the rule numbers that are returned. Rules 1 and 3 apply only to 3D Medusa (Multi-colouring) since they extend chains into multiple candidates. However, the solver needs to look for Singles Chains first because I deem it to be a simpler strategy that's easier to search for.
Taking the example we started with - and identifying all the chain links, we find that in three units there are 5s highlighted in the same colour. The top row has two yellow 5s in A2 and A4. Box 1 has yellow 5s in A2 and B1 and finally, column 1 has yellow fives in B1 and E1. This Rules says that if any unit has the same colour twice ALL those candidates which share that colour must be OFF. The alternative colour will be ON and the solution for that cell.
(Actually yellow is the colour I use to show eliminated candidates. The solver will return Green and Blue for the colouring but then switch one or other to yellow if the candidates are to be eliminated).
Rule 4 - Two colours in a unit
If we can eliminate "off chain" in a cell we can certainly do so off-chain in a unit. In this example I have mapped out the links between 4s. We are certain than ALL blues are the solution or ALL greens. Therefore where there are candidates that can see both colours they can be removed. By 'see' we mean any candidates that are in the same row, column or box as a green and blue candidate.
We can get just two links into box 3. They are from A2 to A8 (giving us a blue) and from G9 to C9. The other 4s cannot be linked but they can be removed.
Many thanks for Michael Wallis for the example. This rule is shared with 3D Medusa.
Having identified all the links for a candidate number, we can look elsewhere for 'off-chain' eliminations. Simply put, if you can spot a candidate X that can see an X of both colours - then it must be removed. In the same Sudoku puzzle as above, but one step before (if you run it through the solver), a Rule 5 example is to be found.
At this stage of the puzzle there are fewer links to be found on candidate 5. But if we colour them we find something interesting going on with the 5 in E3. It can see the blue 5 in E9 and the green 5 in G3. We know the either blue 5s will be the solution or the green 5s will be the solution - so that leaves no room for any other 5 that happens to see both colours.
If you have looked at X-Cycles you'll spot how these two strategies overlap - if your colouring happens to form a loop.
The three blue lines connect pairs of 9s - along columns and rows and within box 7. These are the only units with just two 9s left. As we connect them we alternate between green and blue colours. It doesn't matter where we start or which colour we start with. In this configuration we spot an uncoloured 9 in C7 which can 'see' both a green 9 (C2) and a blue 9 (G7). Since we know that either green or blue will be the solution this 9 in C7 can't be a solution.
I have connected C7 using red lines. You will notice that there are four 9s in total in row C and three 9s in column 7. Simple Colouring can't connect these 9s as only pairs can make a connection.
Article created on 29-January-2011. Views: 264410 This page was last modified on 28-February-2012. All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Syndicated Puzzles Inc, 2012