Coloring

On the Sysudoku Advanced page you pass on your way here, there are descriptions of the coloring link and the coloring network. This page outlines the properties of the coloring network, then walks through the process of building one. Examples follow to illustrate how the network advances the solution.

Coloring Clusters

The coloring link is a link between two candidates, not necessarily of the same value, such that one candidate must be true and the other, false. A coloring link combines the logic of the strong and weak links. If one partner is false, the other is true – a strong link.  If one partner is true, the other is false – a weak link.

Coloring links exist between candidates of the same value in a box or line, when there are exactly two of that value. Also a coloring link exists between the two candidates of a bi-value cell, a bv. Some authors have limited coloring to the “two in unit” link, and consequently, coloring with bv, which generates changes in value along the chain, is sometimes called Medusa coloring. Here, “coloring” always means Medusa coloring.

Coloring links extend into chains, and chains into a connected coloring network, a cluster. The blue and green candidates here form a cluster, which is built by extending chains of coloring links in lines and boxes.

A coloring cluster has a remarkable property. In a coloring chain, every other candidate is true, candidates between them, false. Not knowing which set is true, we assign a distinct color to alternate candidates of a coloring chain. As coloring chains branch into a cluster, roughly half of the candidates in the network are given each color. One color is true, the other is false. That is, one color will be in the solution, and candidates of the other color will be eliminated. When we discover which color is true, we discard about half of the cluster and promote the other half to clues. A term for this cataclysmic conclusion is a wrap. It’s the removed color that is wrapped.

If you haven’t done so already, you should use the properties of the strong link and weak link to convince yourself  why clusters  have this useful property.

As clue confirmations and eliminations occur, clusters gain candidates and expand. Meanwhile the cluster itself causes eliminations, called traps. The blue diamonds above are traps by the current state of the blue/green cluster. Traps and expansions make clusters into solving accelerators. Since the presence of coloring does not interfere or obscure any other solving methods, coloring can be applied as soon as significant numbers of slinks appear.

Building the Cluster

Clusters are built link by link. Here is an advanced grid from World’s Hardest Sudoku, Very Hard 102, at a point strongly suggesting coloring.  There are many bv and unit slinks connecting them.

Coloring can start anywhere, but it’s best to start where slinks can spread the colors. I note the r7 naked pair 38 connecting the left side with a nest of slinks on the right.

I always use blue/green for my first cluster, and red/orange for my second. 8r7c2 will be blue. In the posts I talk about getting out the crayons, but if you’re working on paper, sharper colored pencils are better.  No doubt,  coloring is sufficient reason for going to (c)PowerPoint or equivalent templates. Just select the candidate’s letter box, and click the fill icon. Changing  colors or erasing requires two more clicks.

After turning 8r7c2 blue,  don’t fill 3r7c2 green immediately. Instead, note that 8r7c8 will be green and fill 3r7c8 blue. That’s keeping fill color changes to a minimum.

Unlike the SW region, the SE offers opportunities for blue to spread. Notice that green 3r7c2 winks at many, but has no slink partner other than the blue 3 in r7c8. Slinks are absolutely required.

You should confirm the connecting slink for every added blue fill. That is how a cluster is grown, one slink at a time.

Now we add green. The green pencil is set by selecting the first candidate and clicking the arrow head beside the fill icon to choose a color. Light green and light blue. As we add green, we sometimes  see blue connections we missed before.

Individual candidates are eliminated in cluster building, by traps. Since one of the two colors is true, a candidate seeing both colors must be false.  Here the victims see both colors along lines, but seeing a color in the same box also counts. And it  can happen that both cluster colors invade a cell, forcing other candidates out.

Sysudokies extend a cluster as far as possible before following up on traps, for two reasons. First, because coloring a cluster is easy and can be done quickly. Secondly, to have the conclusion apply to as many candidates as possible.

In the follow up trace, the blue/green cluster expands to wrap green.

The S2 placement reveals green to be false, and the S6 placement  confirms that blue is true. Either one is enough to finish Very Hard 102 with a wrap.

More Traps and Wraps

Here is a subtle form of trap that is often overlooked. It’s from World’s Hardest Sudoku Very Hard 25. Innocent bystander 2r1c7 is suddenly removed because it displeases both colors. If green is true, fair enough, but if blue, the candidate is just as unwelcome in r1c7.  Let’s call it the loser trap.

With a cluster in place, wings and chains can possibly wrap a cluster, unleashing a wound-up spring of logical energy. Take this example, at the finish of Worlds Hardest Sudoku Very Hard 134.

An XY chain slinks green 7r7c2 and  green 7r8c6. It is an ANL removing two blue 7’s. One would have been enough for the wrap. In fact, it’s not even necessary for the any blue 7 to see both terminal green 7’s. Think about it. Coloring says that the green 7’s are both true or both false. But the XY slink says if one is false the other is true, therefore the green 7’s are both true and blue is wrapped, wherever the blue 7’s happen to be.

When a cluster reaches its limit without conclusion, clusters can be added with different pairs of colors.

From a review of David Badger’s Sudoku 1001 Hard Puzzles, here in Hard 101 is a cascade of wraps, started with an unusual trap.  Orange 5r7c5 must be false, because it forces a second and third 16 bv in the C box. Then red forces green, and green forces purple to unravel the puzzle.

Nice Loop Coloring

The 8/27/13 Sysudoku post demonstrated that a nice loop and its extensions form a coloring cluster that takes on the coloring of any intersecting cluster.  Adjacent candidates in the loop are color linked.

Each candidate is slinked directly to one adjacent partner and winked directly to the other, but is winked to the first and slinked to the other by alternating inference chain. In this alphabetic nice loop, candidates a and b are slink partners by adjacency, and wink partners by AIC, while candidates b and c are wink partners by adjacency and slink partners by AIC.

From Antoine Alary’s More Extreme Sudoku, here is an example where a nice loop coloring enhances the power of the loop. Without coloring, the unaided nice loop More Extreme 44 removes the 4 and 6 candidates along r2, and 1 along c7.

The nice loop cluster then expands to remove three more candidates and N46 => N59.

Cluster Bridges and Mergers

Multiple clusters are often created to color link candidates that the first cluster doesn’t reach. When the clusters share values, they can cooperate to make traps and sometimes, to merge.

In this grid from puzzle 310 in A.D. Ardson’s Diabolical Sudoku, three clusters are in place, the colors being blue/green, red/orange and grape/grey.

A bridge between clusters is logic derived from conflicts. In c4, the presence of orange and grape 1’s shows that orange and grape can’t  see each other anywhere on the grid. But this implies that either red or grey is true, possibly both. For short, we write

not(orange and grape) => red or grey.

That’s a bridge. Any candidate seeing red and grey is removed. There are no grey 5’s, but we can look at the 1’s seeing the red 1.  No luck?  See any more bridges?

How about r7? It states: not (blue and orange).   Therefore is has to be one or both opposites must be true,  green or red.  No victim of that bridge, either.

That leaves, from cell r7c3,   not ( green and grey) => blue or grape,  and finally a bridge removal.

The removal brings another bridge,  not (grey and orange) => grape or red.  Can you combine it with a statement above to prove red.  In the S box that rejects grey.  Now you’re really into coloring logic.

A Different Bridge to a Merge

A merge of clusters occurs when a slink is found between colors of two clusters. Both colors on one cluster merge with corresponding opposing colors of the other. The merge creates more opportunities for traps and a wrap of the resulting cluster.

The two clusters we applied in Addict 138 merge into one, as a result of an unusual, but noteworthy bridge. The puzzle was pre-selected for the review of Paul Stephens’ Mastering Sudoku Week by Week and The Sudoku Addict’s Workbook.

The grid of the first coloring differs slightly from the snapshot in Stephen’s Extreme Snaps III (6/18130, because a simpler, more accurate cause is identified for the bridge described by

not(blue and red) =>

green or orange.

Instead of the usual conflict in a box, line or cell, blue and red conflict because, if both are true, they wipe out both candidates of r7c9.

The bridge makes a loser trap for3r9c7, which expands red/orange.

In the expansion, the green orange bridge traps 3r5c7, leaving a strong link between green 3 and orange 3. The slink merges the two clusters. If all green is true, all orange is false,  and if all green is false, all orange is true. So in fact orange is green and red is blue in the merged cluster, or you can paint the whole thing red/orange.

Going with a cool blue/green here in the Akron August, 9r7c2 is false for both green or blue, a loser trap. The trap springs a host of traps, among which is one that confirms SE1, wrapping green. It makes Addicts 138 very blue, but that’s Sudoku.

Other pages will explain the role of coloring in pattern analysis and in trials.