The New Sudoku Players' Forum

[bradles]

Hi all,

I am trying to wrap my head around multiple coloring. I am trying to force the understanding of this technique into my head but am yet to be successful.

I was faced with a multiple coloring suggestion in simple sudoku on the number 5 (see below). I have put a . for all other candidates for the sake of keeping it simple.

Code: Select all

*-----------------------------------------------------------*
 | ..    ..    .     | .     .     ..    | ..    5     .     |
 | .     .     5.    | .     .5.   .5.   | ...   .     .     |
 | 5..   ..    .     | 5.    .     .     | ....  .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | .     .     5     |
 | .     .     .     | 5.    5.    .     | .     .     .     |
 | .     5     .     | .     .     .     | ..    .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | 5     .     .     |
 | .     .     5.    | .     .5    .     | .     .     ..    |
 | 5.    .     5..   | .     .     .5    | .     .     ..    |
 *-----------------------------------------------------------*

Can someone explain this to me in the hope that I can get another example that may hammer this technique into my brain?

Mainly I have trouble with where to start coloring.

Brad.

[Myth Jellies]

Start anywhere you have a row/column/box with only two candidates.

Code: Select all

*-----------------------------------------------------------*
 | ..    ..    .     | .     .     ..    | ..    5     .     |
 | .     .    a5.    | .     .5.  b.5.   | ...   .     .     |
 |A5..   ..    .     |a5.    .     .     | ....  .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | .     .     5     |
 | .     .     .     |A5.   a5.    .     | .     .     .     |
 | .     5     .     | .     .     .     | ..    .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | 5     .     .     |
 | .     .    B5.    | .    b.5    .     | .     .     ..    |
 |a5.    .     5..   | .     .    B.5    | .     .     ..    |
 *-----------------------------------------------------------*
(a, A) and (b, B) are the conjugate color pairs.
considering only the link between a and b along column 5
A = True => A = True,  a = False, b = ????,  B = ????.
a = True => A = False, a = True,  b = False, B = True.
b = True => A = True,  a = False, b = True,  B = False.
B = True => A = ????,  a = ????,  b = False, B = True.


In all possible cases, either A or B is true (these are the colors which do not see each other in my considered link). Thus, r2c3 which sees both an 'A' and a 'B' must be false.

I suppose you could have considered the link between 'a' and 'B' in column 3 instead and determined that any cell which sees both an 'A' and a 'b' (such as r5c5) would be false. It amounts to the same thing since all a's get tagged as false in either case.

[edited to improve my grammar]

[emm]

Code: Select all

*-----------------------------------------------------------*
 | ..    ..    .     | .     .     ..    | ..    5     .     |
 | .     .     5A    | .     .5.   .5b   | ...   .     .     |
 | 5a.   ..    .     | 5A    .     .     | ....  .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | .     .     5     |
 | .     .     .     | 5a    5A    .     | .     .     .     |
 | .     5     .     | .     .     .     | ..    .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | 5     .     .     |
 | .     .     5B.   | .     .5b    .    | .     .     ..    |
 | 5A   .     5..    | .     .     .5B   | .     .     ..    |
 *-----------------------------------------------------------*

Label the two chains differently eg Aa forms one conjugate chain and Bb another.

If A shares a group with both B and b (which are conjugates so one is true) as at r2c3 then A is false.

[Myth Jellies]

Em's point is correct, though it is not really multi-coloring. You really don't need multi-coloring for this layout. Just the b & B's are enough to eliminate the 5 in r2c3.

[emm]

Of course it is! I've been corrected before for 'overdoing' the colouring, too - maybe it's because the technique appeals to me, I get carried away and colour everything in sight!

Mainly I have trouble with where to start coloring.

Myth Jellies posted while I was 'overcolouring' - so my post is superfluous anyway - but maybe you can see how it answers this part of your question. We have coloured the numbers slightly differently which shows that it doesn't matter much where you start - as long as it's with one of a pair of conjugates. The second chain starts with another pair of conjugates that aren't engaged in the first chain.

[bradles]

You guys are probably going to think I'm stupid...but I'm still not getting it.
Is there any chance you could break it down as a step-by-step example? Eg., colour r3c1 blue, ..., ..., etc. Or label r3c1 "a", ..., ... either way.

Code: Select all

*-----------------------------------------------------------*
 | ..    ..    .     | .     .     ..    | ..    5     .     |
 | .     .     5A    | .     .5.   .5b   | ...   .     .     |
 | 5a.   ..    .     | 5A    .     .     | ....  .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | .     .     5     |
 | .     .     .     | 5a    5A    .     | .     .     .     |
 | .     5     .     | .     .     .     | ..    .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | 5     .     .     |
 | .     .     5B.   | .     .5b    .    | .     .     ..    |
 | 5A    .     5..   | .     .     .5B   | .     .     ..    |
 *-----------------------------------------------------------*

According to Simple Sudoku, I can eliminate 5s at r9c1, r5c5, r3c4 and r2c3...but I still can't figure out why/how.

Brad

[Myth Jellies]

Code: Select all

*-----------------------------------------------------------*
 | ..    ..    .     | .     .     ..    | ..    5     .     |
 | .     .     5.    | .     .5.   .5.   | ...   .     .     |
 | 5..   ..    .     | 5.    .     .     | ....  .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | .     .     5     |
 | .     .     .     | 5.    5.    .     | .     .     .     |
 | .     5     .     | .     .     .     | ..    .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | 5     .     .     |
 | .     .     5.    | .     .5    .     | .     .     ..    |
 | 5.    .     5..   | .     .     .5    | .     .     ..    |
 *-----------------------------------------------------------*

Okay, this is not multi-coloring, it is just going to be two color coloring. Pick a candidate which appears in at least one group that has exactly two candidates in it. Let's start with r9c6. We will color it +.

Code: Select all

*-----------------------------------------------------------*
 | ..    ..    .     | .     .     ..    | ..    5     .     |
 | .     .     5.    | .     .5.   .5.   | ...   .     .     |
 | 5..   ..    .     | 5.    .     .     | ....  .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | .     .     5     |
 | .     .     .     | 5.    5.    .     | .     .     .     |
 | .     5     .     | .     .     .     | ..    .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | 5     .     .     |
 | .     .     5.    | .     .5    .     | .     .     ..    |
 | 5.    .     5..   | .     .     .5+   | .     .     ..    |
 *-----------------------------------------------------------*

Now we are going to color with a '-' any candidates which, all by themselves, share a group with only one previously colored '+' candidate. Here, r2c6 is the only other candidate in column 6, and r8c5 is the only other candidate in box 8, so color those candidates '-'.

Code: Select all

*-----------------------------------------------------------*
 | ..    ..    .     | .     .     ..    | ..    5     .     |
 | .     .     5.    | .     .5.   .5-   | ...   .     .     |
 | 5..   ..    .     | 5.    .     .     | ....  .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | .     .     5     |
 | .     .     .     | 5.    5.    .     | .     .     .     |
 | .     5     .     | .     .     .     | ..    .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | 5     .     .     |
 | .     .     5.    | .     .5-   .     | .     .     ..    |
 | 5.    .     5..   | .     .     .5+   | .     .     ..    |
 *-----------------------------------------------------------*

Now we are going to color with a '+' any candidates which, all by themselves, share a group with only one previously colored '-' candidate. Here, r8c3 is the only other candidate in row 8, so color it '+'.

Code: Select all

*-----------------------------------------------------------*
 | ..    ..    .     | .     .     ..    | ..    5     .     |
 | .     .     5.    | .     .5.   .5-   | ...   .     .     |
 | 5..   ..    .     | 5.    .     .     | ....  .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | .     .     5     |
 | .     .     .     | 5.    5.    .     | .     .     .     |
 | .     5     .     | .     .     .     | ..    .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | 5     .     .     |
 | .     .     5+    | .     .5-   .     | .     .     ..    |
 | 5.    .     5..   | .     .     .5+   | .     .     ..    |
 *-----------------------------------------------------------*

At this point there are no more conjugate pairings that can be made off of this starting point. Now it is time to see if any deductions can be made. We know that either the +'s are true and the -'s are false, or the +'s are false and the -'s are true.

If two +'s or -'s showed up in the same group then we could assign false to that color. But that is not the case here.

Instead, what we have is a candidate cell which sees both a + and a -.

Code: Select all

*-----------------------------------------------------------*
 | ..    ..    .     | .     .     ..    | ..    5     .     |
 | .     .    *5*    | .     .5.   .5-   | ...   .     .     |
 | 5..   ..    .     | 5.    .     .     | ....  .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | .     .     5     |
 | .     .     .     | 5.    5.    .     | .     .     .     |
 | .     5     .     | .     .     .     | ..    .     ..    |
 |-------------------+-------------------+-------------------|
 | .     .     .     | .     .     .     | 5     .     .     |
 | .     .     5+    | .     .5-   .     | .     .     ..    |
 | 5.    .     5..   | .     .     .5+   | .     .     ..    |
 *-----------------------------------------------------------*

Cell r2c3 can see a '-' along row 2, and can see a '+' along column 3. Since either '-' or '+' must be true, there is no way that the 5 in r2c3 can be true, thus we can remove it as a candidate. Then its just simple sudoku....r2c3 <> 5 => r3c1 = 5 => r3c4 & r9c1 <> 5 => r5c4 = 5 => r5c5 <> 5.

If there were no deductions, then you could try a different, uncolored, start point.

[bradles]

Myth Jellies,

Thank you so much for taking the time to explain in detail...i really appreciate it.

I went through my example step by step following your advice and was able to do the problem. It is still somewhat parrot fashion to me but I believe, with time and experience, I will develop a better understanding of this technique.

I will keep an eye out for my next multi-coloring problem.

Thanks again,

Brad

[bradles]

Here's another one that I'm a little stuck understanding.

Code: Select all

 *--------------------------------------------------------------------*
 |                      |                      |        1             |
 | 1      1             | 1                    |                      |
 |        1      1      | 1             1      |                      |
 |----------------------+----------------------+----------------------|
 |               1B     |                      | 1b                   |
 |                      |        1             |                      |
 |        1      1      |                      | 1             1a     |
 |----------------------+----------------------+----------------------|
 | 1                    | 1             1      | 1                    |
 | 1             *1*    |               1      |               1A     |
 | 1             1      | 1                    | 1                    |
 *--------------------------------------------------------------------*

I've used "A" and "a" and "B" and "b" instead of the colors that Simple Sudoku recommended. According to Simple Sudoku, the *1* can be eliminated. I'm still a little perplexed by this one. Any thoughts?

Brad

[vidarino]

I've used "A" and "a" and "B" and "b" instead of the colors that Simple Sudoku recommended. According to Simple Sudoku, the *1* can be eliminated. I'm still a little perplexed by this one. Any thoughts?

Since a and b share a unit (box 6), it means both of them can't be true. That means either A or B must be true. And the cell R8C3 (the one marked for elimination) can "see" a candidate in both of these groups, so no matter which it is (A or B), that cell can't be 1.

Vidar

[bradles]

Since a and b share a unit (box 6), it means both of them can't be true. That means either A or B must be true. And the cell R8C3 (the one marked for elimination) can "see" a candidate in both of these groups, so no matter which it is (A or B), that cell can't be 1.
Vidar

Probably a silly question, but does that mean if there was a case where A and B shared a unit box that neither of them could be true so "a" or "b" would be true?

What about if "a" and "B" shared a unit box? Sorry...trying wrap my head around the mathematics of it and why it works.

Brad

[vidarino]

If two colors share a unit, at most one of them is true. (Otherwise we'd have more than one 1 in the unit.) So, thanks to box 6 we know that 'a' or 'b' are mutually exclusive. (It might be that none of them is the correct one, though, since there is an extra uncolored 1 in that box.)

If the two colors are the only two in the unit, exactly one of them is true. (Otherwise we'd have a unit without any 1s.)

if there was a case where A and B shared a unit box that neither of them could be true so "a" or "b" would be true?

Correct. Since we know that one of each pair is true (A or a, and B or b), and both A and B are in conflict, we know that one uppercase and one lowercase color is true. In that case, we could eliminate the extra 1 in box 6 (since a or b would be true).

What about if "a" and "B" shared a unit box?

In that case, we'd have the following situation (in the order mentioned here);
a <> b
A <> B
a <> B

Now, we know that either B or b is true. And *both* of these exclude a. Therefore, A must be true, and all 'a' can be eliminated.

Hope that made sense.

Vidar

[TKiel]

Bradles,

Go to the 'Colouring with three conjugate chains, I mean four now' thread for a good explanation of coloring with mulitple chains, if you haven't already.

Tracy

[ronk]

When learning coloring, I found this description by Lummox JR on the Programmers Forum most helpful. Perhaps it will be helpful to others as well.

Here's the algorithm as I initially read and understood it:

1) Search all rows for conjugates. Label the first pair a and A, the second b and B, and so on.
2) Search all columns for conjugates.

2a) If neither cell is colored, use the next color set.
2b) If only one cell is colored, color the other with its conjugate.
2c) If both cells are colored, replace the higher color with the lower one's conjugate. Make this replacement everywhere. E.g., if you see A and B together as conjugates, then make all B's into a's and all b's A's.

3) Search all boxes for conjugates, using the methods in step 2.

Now in the basic form, you can do the following: 1) If the same color appears twice in a box/column/row, it is false and you can eliminate it. 2) If two conjugates intersect at another choice, eliminate it.

Ron

[yasmin]

I have 2 questions regarding the last explanation (the "algorithm"):

1. Doesn't it matter which of the two conjugates I call "a" and which "A", which "b" and which "B" and so on?

2. IN the final paragraph of the last reply, "eliminate IT" - does that mean eliminate the colour or the candidate?

thanks
Yasmin