This strategy has been deprecated and is not in the solver as in all tested cases a simpler strategy can be used to by-pass this one. There is some mileage in considering the interaction of two X-chains (ie chains on just one candidate number) but the complexity of doing so pushes this approach way down the priority list. It is retained here as an acedemic exercise.
There are two major types of Multi-colouring and neither are for the faint hearted. You'll need four coloured pencils ;-) Fortunately we are only scanning the board for single numbers in conjugate pairs. These occur where a candidate exists only twice in any row, colum or box (unit). We can chain these togther if there are sufficient numbers of them just as we did for simple colouring above. In Multi-Colouring we are looking for two or more chains. It is important they don't link up - three or more appearances of the candidate number in an intervening unit prevent the 'link up' of two chains.
Given two chains we can label them A and B. A+ and A- will indicate the alternating states so that EITHER all of A+ are true OR all of A- are true. We don't know which way round yet. Similarly B+ and B- indicate alternating true/false for that chain. C+ and C- continues the theme if there are more chains on the same candidate number. Give A+, A-, B+ and B- we can colour them on the board to see the patterns.
Type 1 Multi-Colouring The Rule is as follows: If A+ shares a unit with B+ and B- then A+ must be the false candidate since either B+ or B- must be true.
Multi-Colouring Type 1 eg 1
: Load Example
or : From the Start
In this Sudoku we've looking at number 7 and labelled two chains A and B and settled on the plus and minus symbols. I have labelled them so that they match the rule. (Don't make a category mistake and think the rule applies just because you've assigned the lables!).
Now, the yellow cell marked A- does not share a unit with any of B cells. However, all three cells marked A+ can see a B+ or a B- in one or more shared units. Since the solution cannot be both B+ and B- but must be at least all of B+ or all of B- every cell in A+ must be false and number 7 can be removed from all A+ cells.
Multi-Colouring Type 1 eg 2
: Load Example
or : From the Start
This second example is provided to illustrate the idea a bit further. A+ is again the victim and all the labels are the same as the first example. It also shows that the chains can be quite short.
Interestingly, although B can be a chain of just two cells A must be a longer chain. Otherwise we'd be in a situation where the Sudoku has two solutions or multi-colouring can be reduced to a Unique Rectangle.
Type 2 Multi-Colouring
If A+ shares a unit with B+ then any cell with the given candidate and sharing a unit with both A- and B- can have that candidate excluded. The Reason: Since A+ and B+ can't both be true, then either one or both of A- and B- must be true. Therefore any cell sharing a unit with both A- and B- can safely have that candidate excluded.
Multi-Colouring Type 2, Example 1
: Load Example
or : From the Start
This is a bit of a mouthful. What we're looking at are cells marked A+ which can see B+ cells but A- cells cannot see B- cells. A+ and B+ both can't be true since they share units in two cases. One or perhaps both of the units marked A- and B- must be true. All cells that can see an A- and a B- can't contain the candidate, in this example number 8. In R3C5 an 8 can see R2C4 AND R8C5. Similarly the 8 in R7C4 can see R2C4 and R8C5/R7C9.
Multi-Colouring Type 2 eg 2
: Load Example
or : From the Start
This smaller example might be more easy to understand. The labels are the same so that one A+ can see a B+. There is just one place where a 7 is at the overlap of an A- and a B-.
Multi-Colouring with 3+ chains
I don't have an example of a Sudoku requiring a multi-colouring solution using three or more chains. I'd be very grateful for an example.
You say simpler strategies can be used in place of multi-coloring, but you do not mention what those strategies are. I loaded the second example into your solver and it ended up using an X-cycle on 9 to solve cell R6C5. Personally, I find multi-coloring on such short chains easier than hunting for a suitable X-cycle, as there is only one way to form all the colored chains for a number but many possible X-cycles on that number.
Sherman
P.S. I love this web site. I just stumbled across it a few weeks ago. It is a great companion to your book that I read way back in 2007.
Tuesday 19-Nov-2013
... by: Patrice
Hi Andrew, Nice explanations, thanks I don't see where Multi-Coloring take place in the solver strategies Is it merged with another strategy ?
Andrew Stuart writes:
Hi Patrice, I should have put a notice up when I stopped using thi strategy, I have now done so.
Tuesday 29-Jan-2013
... by: Howard
Thank you for your lectures on Sudoku. I think, in para. 2 under Type 1 Multi-Coloring, the number 7 can only be removed from the A+ square that can see both B+ and B- squares. We shoulld not remove 7 from other A+ squares that can see only B+ or B- squares but not both. Am I right?
Howard
Tuesday 29-Jan-2013
... by: Howard
Thank you for your lectures on Sudoku. I think, in para. 2 under Type 1 Multi-Coloring, the number 7 can only be removed from the A+ square that can see both B+ and B- squares. We shoulld not remove 7 from other A+ squares that can see only B+ or B- squares but not both. Am I right?
Howard
Friday 27-Jul-2012
... by: Mr Turner
For an excellent discussion of the issue and the example you seek, take a look at http://www.geometer.org/mathcircles/sudoku.pdf. In particular, look at Section 9, Coloring and Multi-Coloring.
Monday 23-Apr-2012
... by: Dino Hsu
Both type I and type II tecniques are about the interactions between one chan and another, why calling it multi-coloring instead of multi-chain?
Andrew Stuart writes:
For historical reasons, thats the name the community coined way back when. Colouring emphasises that it is easier to mark the chains with colours.
Comments
Comments TalkTuesday 25-Mar-2014
... by: Sherman
Andrew -You say simpler strategies can be used in place of multi-coloring, but you do not mention what those strategies are. I loaded the second example into your solver and it ended up using an X-cycle on 9 to solve cell R6C5. Personally, I find multi-coloring on such short chains easier than hunting for a suitable X-cycle, as there is only one way to form all the colored chains for a number but many possible X-cycles on that number.
Sherman
P.S. I love this web site. I just stumbled across it a few weeks ago. It is a great companion to your book that I read way back in 2007.
Tuesday 19-Nov-2013
... by: Patrice
Hi Andrew,Nice explanations, thanks
I don't see where Multi-Coloring take place in the solver strategies
Is it merged with another strategy ?
Tuesday 29-Jan-2013
... by: Howard
Thank you for your lectures on Sudoku.I think, in para. 2 under Type 1 Multi-Coloring, the number 7 can only be removed from the A+ square that can see both B+ and B- squares.
We shoulld not remove 7 from other A+ squares that can see only B+ or B- squares but not both.
Am I right?
Howard
Tuesday 29-Jan-2013
... by: Howard
Thank you for your lectures on Sudoku.I think, in para. 2 under Type 1 Multi-Coloring, the number 7 can only be removed from the A+ square that can see both B+ and B- squares.
We shoulld not remove 7 from other A+ squares that can see only B+ or B- squares but not both.
Am I right?
Howard
Friday 27-Jul-2012
... by: Mr Turner
For an excellent discussion of the issue and the example you seek, take a look at http://www.geometer.org/mathcircles/sudoku.pdf. In particular, look at Section 9, Coloring and Multi-Coloring.Monday 23-Apr-2012
... by: Dino Hsu
Both type I and type II tecniques are about the interactions between one chan and another, why calling it multi-coloring instead of multi-chain?