Coloring is a moderately advanced technique used in solving Sudoku. But don't be daunted, I'll be gentle. First, allow me to introduce a new definition.
- conjugate: If only two cells in a group contain a particular candidate, the two cells are called conjugate to each other with respect to that candidate.
For example, the two cells marked with X in the following board are conjugates of eachother with respect to three.
*-----------*
|...|...|...|
|...|...|...|
|...|...|...|
|---+---+---|
|...|...|...|
|...|...|...|
|...|...|...|
|---+---+---|
|...|...|...|
|...|...|...|
|16X|572|4X8|
*-----------*
One of the two marked cells must contain the three, the other cannot. Furthermore, the cells are conjugates of eachother with respect to nine (though this is irrelevent for the purpose of this writeup); it is not necessarily the case that there are always a pair of conjugate pairs.
Coloring exploits conjugates of conjugates of conjugates of conjugates of..., to whatever depth necessary. Of course in the example above we cannot deduce anything because we have no further information. In the following diagram, those cells marked with a six are the cells that include six as a candidate.
*-----------*
|...|...|...|
|..6|...|6..|
|6..|...|.6.|
|---+---+---|
|.66|...|..6|
|...|6.6|...|
|.66|...|6..|
|---+---+---|
|.6.|6.6|..6|
|6..|6.6|6..|
|..6|...|.6.|
*-----------*
There are a lot of conjugates here. Every time you see two sixes (and only two sixes!) in a group, they are conjugates of eachother. Let's pick a six and call it 'A' (of course, this name is arbitrary; it could well be 'green' or whatever you'd like). Which six we select is arbitrary, as well. The method works no matter where you start (mostly). Once you learn the technique you'll be able to identify which cell is good-fer-pickin'.
*-----------*
|...|...|...|
|..A|...|6..|
|6..|...|.6.|
|---+---+---|
|.66|...|..6|
|...|6.6|...|
|.66|...|6..|
|---+---+---|
|.6.|6.6|..6|
|6..|6.6|6..|
|..6|...|.6.|
*-----------*
All the conjugates of 'A'? Let's call them 'a' (or 'cyan', or 'Goto Dengo').
*-----------*
|...|...|...|
|..A|...|a..|
|a..|...|.6.|
|---+---+---|
|.66|...|..6|
|...|6.6|...|
|.66|...|6..|
|---+---+---|
|.6.|6.6|..6|
|6..|6.6|6..|
|..6|...|.6.|
*-----------*
Note well that we didn't color anything in column three. This is because there are more than two sixes; we can only color conjugates. If there are three cells in a group, we cannot call any of them conjugates. Now let's color the conjugates of the two 'a's.
*-----------*
|...|...|...|
|..A|...|a..|
|a..|...|.A.|
|---+---+---|
|.66|...|..6|
|...|6.6|...|
|.66|...|6..|
|---+---+---|
|.6.|6.6|..6|
|A..|6.6|6..|
|..6|...|.6.|
*-----------*
We're almost done...
*-----------*
|...|...|...|
|..A|...|a..|
|a..|...|.A.|
|---+---+---|
|.66|...|..6|
|...|6.6|...|
|.66|...|6..|
|---+---+---|
|.6.|6.6|..6|
|A..|6.6|6..|
|..6|...|.a.|
*-----------*
*-----------*
|...|...|...|
|..A|...|a..|
|a..|...|.A.|
|---+---+---|
|.66|...|..6|
|...|6.6|...|
|.66|...|6..|
|---+---+---|
|.6.|6.6|..6|
|A..|6.6|6..|
|..A|...|.a.|
*-----------*
Now finally something interesting happens! Box seven has two 'A's in it! Remember that we're coloring possible candidates for sixes. Box seven cannot have two sixes in it, so we can exclude six from all of the cells marked with 'A'. This is all possible because we've only been dealing with conjugates; either every single 'A' is a six or every single 'a' is a six. But we just ruled out the possibility of 'A's being six. Since we're dealing with conjugates, that means all of the 'a' cells are actually the sixes. This allows us to skip a step; we need not notice that all the 'a's are sixes because hidden singles will do the job for us after we exclude sixes from the 'A's.
But wait, there's more! There are three types of coloring, this is just one of them (type-2 coloring). Type-1 coloring lets us exclude candidates when they are grouped with a cell from each color. That's because one of the conjugates has to be the true candidate, so if the cell is grouped with both conjugates, there's no way it can be the candidate in question. I like to think of the cell as orthogonal to the coloring. Using a step from our example board from above,
*-----------*
|...|...|...|
|..A|...|a..|
|a..|...|.A.|
|---+---+---|
|.66|...|..6|
|...|6.6|...|
|.66|...|6..|
|---+---+---|
|.6.|6.6|..6|
|A..|6.6|6..|
|..6|...|.a.|
*-----------*
There's no way that the hardlinked cell, R8C7, can be a six. If the 'A' cells are really the sixes (which from our reasoning above, they cannot be, but we don't know that just yet when we're looking at this step), then R8C7 cannot be six because then there'd be two sixes in row seven. Same for the 'a' in box nine. So we can exclude the six in R8C7. This leads to another conjugate pair in column seven, so we could have continued the process if our first foray hadn't panned out.
Like I mentioned earlier, there are three types of coloring. The type-3 coloring pattern is a bit obscure. Here's the board in which I independently discovered it.
*-----------*
|...|...|...|
|9..|...|.9.|
|..9|...|..9|
|---+---+---|
|..9|.9.|..9|
|9..|...|..9|
|9.9|.9.|.9.|
|---+---+---|
|...|...|...|
|...|...|...|
|...|...|...|
*-----------*
I trust you can color the conjugates easily enough. We eventually make it here:
*-----------*
|...|...|...|
|A..|...|.a.|
|..a|...|..A|
|---+---+---|
|..9|.9.|..9|
|9..|...|..9|
|9.9|.9.|.A.|
|---+---+---|
|...|...|...|
|...|...|...|
|...|...|...|
*-----------*
We can use type-one coloring to exclude the hardlinked cell and color a bit more.
*-----------*
|...|...|...|
|A..|...|.a.|
|..a|...|..A|
|---+---+---|
|..A|.9.|..9|
|9..|...|..9|
|9..|.9.|.A.|
|---+---+---|
|...|...|...|
|...|...|...|
|...|...|...|
*-----------*
Let's assume that 'A' is truly nine. This would leave us without a nine in box five! The only possible nines in box five are from rows four and six. Therefore, we can conclude that the 'A's are not nines and that 'a's are. From what I understand, most people would solve this bit with multicoloring, where you use multiple sets of conjugates (like a/A and b/B).
Simple Sudoku has two handy commands for coloring. After you filter for the candidate in question, you can use Ctrl+H to hide all the other candidates. This makes it easier to focus on what you're really doing. Secondly, it actually has coloring filters. Instead of 'A' and 'a', you could use green and cyan. So you don't need to try to remember what color something was.
So when do you know when to you use coloring? You don't, really. You just try it after all the easier techniques have been exhausted and see what happens. Usually, though, coloring comes on the tail end of a board. Naturally, this is because there is a higher propensity for conjugates in a nearly-solved board.
I mentioned early in the writeup that it really doesn't matter where you make the initial coloring (mostly). Clearly you wouldn't try to start with a cell with no (or very few) conjugates. Sometimes there are are multiple "valid" sets of conjugates. Again, that's where multicoloring comes into play.
And finally, some boards that require the use of coloring.
*-----------* *-----------* *-----------*
|6.2|.7.|.5.| |6.5|...|8.2| |.3.|9.8|.6.|
|.5.|..8|...| |...|.2.|1..| |..6|.4.|2.8|
|43.|1..|...| |7..|1..|..3| |.5.|.6.|...|
|---+---+---| |---+---+---| |---+---+---|
|5..|69.|4..| |5..|..2|...| |7..|3..|.8.|
|..7|5.2|9..| |.76|5.8|21.| |...|...|...|
|..6|.17|..5| |...|3..|..4| |.8.|..4|..3|
|---+---+---| |---+---+---| |---+---+---|
|...|..9|.28| |1..|..4|..8| |...|.7.|.2.|
|...|2..|.6.| |..7|.6.|...| |3.8|.2.|9..|
|.6.|.8.|5.9| |8.2|...|7.6| |.9.|6.5|.1.|
*-----------* *-----------* *-----------*