When one considers deductions about a Sudoku that consider only one type of candidate at one time,
I call this Coloring. The previous post on coloring covered this idea and provided some examples,
but perhaps failed to detail how one finds eliminations using this technique. This page will
attempt to provide hints as to how to find Coloring. I will use the
Tough Sudoku of February 17, 2007
to illustrate and explain Coloring.
I recommend looking for coloring eliminations early. I also recommend that coloring be studied
well, as the logic for coloring and the logic for more complex forbidding chains is exactly the
same. However, since coloring only considers one candidate type it is easier both to grasp and to
find.
Some defintions
The following terms are employed in the explanations below:
- %
- is a singleton in
- strong set
- A set such that at least one of its members must be true
- weak set
- A set such that at most one if its members can be true
- If A & B are members of a weak set:
- A = true implies B = false
- B = true implies A = false
- native
- Naturally occurring in the current puzzle possibility matrix without
making any deductions
- House
- A cell, box, column, row
- Unique Possibilites
- A cell that is solved because it is uniquely defined in a house.
- UP
- Acronym for Unique Possibilities
- =>
- implies
Please note that a weak and strong need not be mutually exlusive properties. In other words,
a set that is strong may also be weak. More precise definitions are available on the
Definitions page of the blog.
Puzzle at start
A few Unique Possibilities:
- c6 = 5% row
- g2 = 6% row & box
- e6 = 6% row
- d7 = 6% box
Puzzle at UP 27
After finding the Unique Possibilities, Hidden Pairs are often easy to find. This process
is completely detailed in the last few blog pages as Easy Proofs.
The givens: d9=7, g9=4 and c1=7, c4=4 and a7=9, b8=5 force a Hidden Pair 47 at cells a8, b7.
The following illustrations will reflect that all other candidates have been exluded from those
cells.
Beginning of Coloring Tutorial
Again, it is wise to look for deductions made on just one type of candidate early. Obvious
benefits are:
- Finding all the locked candidate eliminations
- Finding other easy eliminations
- Perhaps locating Hidden Singles that one might have missed
- Learning the general concept of forbidding chains
- Can give one a feel for where to look for more complex deductions
Usually, I just stroll through the canididates in order from 1 through 9, as taking the time
to decide where to start does not seem very productive.
Finding Nothing of Consequence with the 1s
Oftentimes, there is nothing to deduce for a particular candidate. On the left, the possible
locations for 1's reveal no locked candidates except those at df5, which forbid nothing. One should
look for strong sets that are limited to two candidate locations. If there are few, there
is likely not much to do - unless there is some symmetry.
Locked Candidates with 2s
On the left, the 2s in column d are limited to two locations: d4,d5. Since both of these
locations are also in box e5, if f56=2, then there would be no place for 2's left in column d.
Thus, we can safely exclude 2 from f56.
One could also consider the 2's in box e8 are limited to
f789. Since f789 is in column f, these 2's also forbid f56=2.
Finned X wing on 2s
Because the 2s in row 6 are limited to bi6 and the 2s in row 2 are limited to i2,abc2 and
because abc2 are all in box b2:
- If there were any possible 2s at b13, they would be impossible
The configuration above is sometimes called a Finned X wing, as it is much like an X wing, except one
can make no eliminations in column i, nor in column b outside of box b2.
The black lines represent strong links between members of a native strong set. The red lines
are weak links between endpoints of the strong links.
- Suppose b6=2. Then b13≠2.
- Suppose b6≠2. Then
- i6=2, as there must be at least one 2 in row 6
- i2≠2, as there cannot be more than one 2 in column i
- abc2 must contain a 2, as there must abe at least one 2 in row e
- b13≠2, as there cannot be more than one 2 in box b2
- Thus, whether or not b6=2, b13≠2
- Of course, we already knew this... as e1=2 and b3=6.
Nevertheless, it is useful to be aware of this type of pattern, as sometimes it does forbid
something.
Finding nothing with the 3s
The 3s do not have any strong sets limited to just two locations. Furthermore, there
are no apparent useful groupings with the 3s as with the finned Xwing example
Dead ends
The 4s have many native strong sets limited to just two locations. But, they do not interact
with each other in a fruitful pattern. The two circled sets:
are dead ends.
By dead ends, I mean that one choice of the two hardly interacts with the
puzzle at all. For example,
- If i5=4, then
- But we cannot go any futher!
This would be ok, but if i5≠4, then although all the 4's are chosen on the puzzle grid,
none of these choices can ever produce a conflict with what is deduced from i5=4.
I prefer to see such a relationship like this:
- Both possible choices, hi5, interact with the puzzle in just one direction
- Both possible chioces, e78, interact with the puzzle in just one direction
- All the intermediate choices for 4 boxes h2, b2, b8 interact with the puzzle
in opposite directions
- None of the possible choices for 4 can ever conflict with each other, as they
never wrap back to one point
Hopefully, this is clearly put. Study the configuration above. There will never be useful
deductions that one can make from similar
dead ended configurations.
Perhaps the best way to view dead ends: All the possible interactions proceed
in just one way from each end. None of the intermediate interactions go anywhere but to
the dead ends.
Immediatley upon finding such a configuration, one can note two things:
- There are no forbidding chains available on just that candidate
- If another technique eliminates almost any 4, (except ah1=4), some Unique
Possibilities are certain, with a cascade of Unique Possibilities likely
Seperated regions
Although the 5s illustrated to the left are very strong, they are divided into two seperate
regions that cannot interact with each other without using another candidate type as a bridge.
For this reason, immediately upon seeing such a configuration, one can divide the possible
interactions into two distinct pieces. Here, since both regions are also dead ended,
there can be no one candidate dedudctions made.
However, the region formed by ad12 is a likely place for a Unique Rectangle to occur.
More Dead ends
The sixes are clearly dead ended. No need to linger here.
More Locked candidates
Because of the initial finding of the hidden pair at a8, b7 - there are some locked
candidate eliminations possible with the 8s. After making these, the 8s are almost interesting,
but essentially dead ended.
Interesting Configurations with 9s
The nines are not dead ended. They are not seperated into regions. They have some native
strong sets limited to two locations:
The 9s warrant some investigation.
Two String Kite
Illustrated to the left is a very common configuration. One need only recognize two
strong sets
- 9s in column c
- 9s in row 1
and then see that one endpoint of each share a house:
One way to view the elimination of 9 from d5:
- c5=9 => d5≠9, considering row 5
- c5≠9 =>
- c3=9, considering possible 9s in column c =>
- b1≠9, considering box b2 =>
- d1=9, considering possible 9s in row 1
- d5≠9, considering column d
- Conclude that d5 ≠9
Written as a forbidding chain on 9s:
- c5 == c3 -- b1 == d1 forbids d5=9
Using colors, one could do the following:
- c5=red
- c3=yellow
- b1=red
- d1=yellow
- d5 cannot be red or yellow, thus d5≠9
This elimination does not signficantly advance this particular puzzle. However, there is
another more complex elimination with 9s available.
Finned Swordfish - or an Almost X wing
Consider only these three strong sets:
- {fi9=9}
- {bfi6=9}
- {c35=9}
Partition set 2, {bfi6}, into two pieces: {b6, fi6}.
The logic illustrated above is as follows:
- X wing at fi69 would forbid f3=9
- No X wing at bi69 =>b6=9 => c5≠9 => c3=9, also forbidding f3=9
- Conclude: f3≠9
To convice yourself of the validity of such an elimination, try a proof by contradiction:
- Suppose f3=9
- f3=9 => c3≠9 => c5=9 =>b6≠9
- {f3=9 and c5=9} => b6,f6≠9 => i6=9 considering possible 9s in row 6
- i6=9 => i9≠9 => f9=9 considering possible 9s in row 9
- But, f9=9 and f3=9 cannot both occur! Thus, f3≠9
As a forbidding chain on 9s: (also called an
Alternating Inference Chain, or AIC)
- c3=9 == c5=9 -- b6=9 *==*{X wing on 9s at *fi6*, fi9} forbids f3=9
The asterisks in the chain denote the partitioning of the strong set bfi6=9 into three pieces.
The bracketed portion of the chain is a contained Boolean. Since both the X wing and c3=9 forbid
f3=9, f3≠9. Complex forbidding chains like this one, using contained Booleans, are briefly
explained in the blog page:
Advanced Forbidding Chains.
Another view
By considering the 9s in row 1 rather than the 9s in column c, the same elimination
of 9 from f3 looks almost like a swordfish. For this reason, it could be called a
finned swordfish. All the logic already shown previously applies in an
analagous fashion.
Still, this puzzle is not unlocked. I have saved the most promising elimination for last
Very Strong 7s
The 7s have numerous bilocation strong sets:
- {a8,b7}
- {b7.b5}
- {a4,e4}
- {e4,f5}
- {f5,f3}
- {e3,i2}
- {i2.h3}
- {h3,h8}
- {i7,b7}
There are no dead ends. There are no seperated regions. One can almost always find
fruitful patterns for eliminations in such a configuration. In fact, there are so many ways to
present essentially the same idea I best not take the time and space to present them all. Here,
one can pick any of the strong sets listed above and find that considering both ends will
prove an elimination.
Forbid some sevens
Explanation of graph at the left:
- b7=7 => a8,i7 ≠7
- b7≠7 =>
- b5=7 => f5≠7 => f3=7 => h3≠7 => h8=7 => a8,i7 ≠7
- conclude a8,i7 ≠7
As a forbidding chain on 7s:
- b7=7 == b5=7 -- f5=7 == f3=7 -- h3=7 == h8=7 forbids a8,i7=7
In a case such as this one, with so many strong links available, one can forgo proving an
elimination, and instead prove an existence
Prove b7=7
To the left we have the graphical illustration of a forbidding chain that
ends and starts with the same argument. Such a chain, once reduced to its endpoints,
proves existence. It requires one more strong set.
As a forbidding chain on 7s, the graph above would read:
- b7 == b5 -- a4 == e4 -- e2 == i2 -- i7 == b7
Such a forbidding chain, perhaps better called a proving chain, reduces logically to:
Power of Coloring
One way to illustrate the power of coloring is to consider the proof of this puzzle:
- Start at 23 filled - the given puzzle. Unique Possibilities to 27 filled. (UP 27).
- fc on 7's: b7 == i7 -- i2 == e2 -- e4 == a4 forbids a8,b5=7 UP 81
- Sets: 3
- Max depth 3
- Rating .07
Coloring reduces this tough puzzle an almost trivial exercise!
