SudokuWiki.org
Strategies for Popular Number Puzzles
Multi-Colouring Strategy
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.
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.
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.
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.
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 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.
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.
Comments
... by: Robert
-------------------------------
I get the impression these comments are not monitored very closely, and I'm responding to a comment that's more than six years old, so I'm not sure the author will even see it. But, here goes.
Responding to the comment by Sherman:
These strategies can be replaced by the "Nice Loops" strategy, together with some very basic strategies.
I will answer using the terminology of "strong" and "weak" links, which is used extensively in the description of the nice loops strategy. From that discussion, a "strong" link can always be treated as a "weak" link if it is advantageous to do so.
Consider type 1 - the "A" cells are all connected through strong links. The "B" cells are also connected using strong links. The link between an "A+" cell and the "B+" cell must be a weak link; if it were strong, then the "B" cells would be "A" cells instead. Similarly, the link between the "A+" cell and the "B-" cell is a weak link. There are two cases to consider.
First, suppose it is the *same* A+ cell that is connected to a "B+" and "B-" cells. Note that there must be a path from the "B+" cell to the "B-" cell that consists of an odd number of strong links. If there weren't a path using strong links only, then the "B+" and "B-" cells wouldn't be part of the same coloured chain. And if it were an even number of links, then we wouldn't have "B+" or "B-", we would have both "B+" cells or both "B-" cells. So there is a loop:
A+ --- weak link --- B+ ---
This is a "nice loop" with a discontinuity, with two weak links in a row, and the "A+" cell is between the two weak links. This is because we can treat some of the strong links on the path from B+ to B- as weak links. For example, if there were five links on this path, we would treat them like strong-weak-strong-weak-strong, even though they are all strong. Then they entire loop would be weak-strong-weak-strong-weak-strong-weak, so there are two weak links in a row (before and after A+), and the rest of the links alternate strong and weak. So by the nice loops rule, we can remove the candidate from the A+ cell. This removal then propagates through the rest off the A+ and A- colour chains, using very basic rules, removing the candidate from all A+ cells, and making it as the only candidate in the A- cells.
The second case is when one A+ cell is connected to B+, but a different A+ cell is connected to B-. There must be a path between the two A+ cells with an even number of strong links. So there is a loop that looks like this.
In the path from the second A+ cell back to the first, we take the links to be alternating strong/weak/strong/weak, even though they are all strong. This is also a nice loop, with the first A+ cell at the discontinuity between two weak links. The candidate can be removed from this A+ cell, and the removal propagates through the colour chain, using very basic techniques, ultimately removing the candidate from all A+ cells, and making it the only possibility in all A- cells.
So this shows the first type of rule for the multi colouring is actually a nice loop with a discontinuity, two consecutive weak links. For type 2 multi colouring, note that the path between A+ and A- cells has an odd number of strong links, as does the path from the B+ and B- cells. So there is a loop of this form.
So treat the links in the path from A- to A+ as alternating strong/weak/strong, and the links on the path from B+ to B- also as strong/weak/strong, then there is a nice loop with a discontinuity, two consecutive weak links, with
So both types of multi-colouring can be viewed as a case of a nice loop with two consecutive weak links, and in the case of type 1, some other basic logic is needed to make the change propagate through the entire A-chain. (The "other basic logic" is described in the "getting started" section.)
In fact, the simple colouring chain is also a special case of "nice loops" with two consecutive weak links. Even the "nice loops" with two consecutive strong links is a special case of two consecutive weak links, just by treating one of the strong links as a weak link - you get the same end result (using the "getting started" logic as well). And a nice loop with an even number of links, alternating strong/weak, can be treated as a special case of two consecutive weak links, by including the cell that is off the loop (the one where the candidate is to be eliminated) as part of the loop.
So in my opinion, not only does "nice loops" completely subsume the simple colouring strategy and also the multi-colouring strategy, the two-consecutive-weak-links version of "nice loops" completely subsumes the other two versions of "nice loops". So simple colouring plus multi-colouring are special cases of the weak-weak version of nice loops. I suspect that they might include all cases of nice loops, that is, we could deprecate nice loops and bring multi-colouring back to life, but I need to put pen to paper to prove that for sure. I'll think about it.
But even though simple colouring is a special case of "nice loops", I still use simple colouring, because I find it easier to keep straight in my head than nice loops. If simple colouring fails, then I move on to nice loops, but I actually use a strategy very similar to multi-colouring to identify nice loops.
... by: Sherman
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.
... by: Patrice
Nice explanations, thanks
I don't see where Multi-Coloring take place in the solver strategies
Is it merged with another strategy ?
... by: Howard
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
... by: Howard
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
... by: Mr Turner
... by: Dino Hsu