Coloring: How to Find


When one considers deductions about a Sudoku that consider only one type of candidate at one time, I call this Coloring. A previous blog page dealt with 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.

You may wish to refer to previous blog pages, although it probably is not required. Links to these pages are found to the right, under Previous Entries.

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


PUzzle start

A few Unique Possibilities:

  • c6 = 5% row
  • g2 = 6% row & box
  • e6 = 6% row
  • d7 = 6% box

Puzzle at UP 27


PUzzle we will analyze

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


Nothing exciting 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


Twos

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


Finned X wing

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


Threes

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


Fours

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:

  • hi5=4
  • e78=4
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
    • h5≠4
    • i1≠4
  • 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:

  1. There are no forbidding chains available on just that candidate
  2. If another technique eliminates almost any 4, (except ah1=4), some Unique Possibilities are certain, with a cascade of Unique Possibilities likely

Seperated regions


Fives

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


Sixes

The sixes are clearly dead ended. No need to linger here.

More Locked candidates


Eights

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


Fours

The nines are not dead ended. They are not seperated into regions. They have some native strong sets limited to two locations:

  • {fi9}
  • {bd1}
  • {b1c3}
  • {c35}
The 9s warrant some investigation.

Two String Kite


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:
  • b1, c3 in box b2

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


Almost X wing

Consider only these three strong sets:

  1. {fi9=9}
  2. {bfi6=9}
  3. {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


Other 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


Sevens

The 7s have numerous bilocation strong sets:

  1. {a8,b7}
  2. {b7.b5}
  3. {a4,e4}
  4. {e4,f5}
  5. {f5,f3}
  6. {e3,i2}
  7. {i2.h3}
  8. {h3,h8}
  9. {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


Forbidding

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


Affirmation

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
    • forbids b7≠7
    • thus b7=7
Such a forbidding chain, perhaps better called a proving chain, reduces logically to:
  • b7=7 == b7=7
  • Thus b7=7

Power of Coloring

One way to illustrate the power of coloring is to consider the proof of this puzzle:

  1. Start at 23 filled - the given puzzle. Unique Possibilities to 27 filled. (UP 27).
  2. 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!




10 Comments
Indicate which comments you would like to be able to see

I am sorry about the length of the page. It is unclear to me how to accomplish some competing goals:
Completeness
Simplicity

Use of just graphs and forbidding chain language would have shortened this page very much!

Is the added length worth it?

 |  |
Regarding the term: Coloring.
Although many sudoku sites have expanded this term to include more than one type of candidate at one time, this term renders Coloring meaningless, as every possible sudoku elimination can then be justified under such a broad use of the term. For this reason, I More...
 |  |
Hi Steve, another great page with really clear explanations. One puzzle though...when you say:
'* 9s in column d
* 9s in row 1'

shouldn't it be 9s in column c???

Or am I missing something.
Thanks again
 |  |
Hi Soozn!
Yes, it should be column c. I suppose I will never cease making typos! Thank-you for letting me know! The page has been corrected.
 |  |
Thanks again, Steve! Don't worry about the length of the presentation. For a reader at my level this was on the money. I wish I could recognize dead ends without trying them out!
 |  |
Wow - I don't understand but it is impressive. You must be a maths genius in your other life! I'm still trying to master the easy puzzle!
 |  |
thanks Steve for your patience in teaching.. i understand the logic in the two string kite illustrated above..but i was thinking that the 9s at b1 and c3 ahould be strong not weak as indicated in your chain.
 |  |
Hi billj!
Many places make strong and weak mutually exlusive properties.
There is no need for that.
Thus, it is perfectly ok for a relationship to be both strong and weak. Since the chain needs the forbidding quality of the relationship between b1 and c3, that is the one used.

BTW More...
 |  |
Hi STEVE,

For me, COLORING is COLORING ...! 2-sting kite, for what? Coloring (simple & multiple) is cover 2-string kite... I think you have to keep the name Coloring for that technicque.
Study your blog and a thread post on other site (identification of forcing chains - maybe JEFF), now More...
 |  |
Hi ttt!
I also perfer a shorter list of techniques, as proper understanding of them renders the hundreds of individual technqiues superflous.

I may blog forcing chains at some time, but forcing chains can be viewed entirely as a subset of forbidding chains. The information considered More...
 |  |
Please Log in to post a comment.

Not a member? Joining is quick and free.
As a member you get heaps of benefits.
Click Here to join.
You can also try the Chatroom (No one chatting right now - why not start something? )
Check out the Sudoku Blog     Subscribe
Members Get Goodies!
Become a member and get heaps of stuff, including: stand-alone sudoku game, online solving tools, save your times, smilies and more!
Previous Entries

07/Jan/07 Ywing Styles
06/Jan/07 Definitions
31/Dec/06 Y wings
27/Dec/06 Coloring
11/Dec/06 Beginner Tips
Check out all the Daily Horoscopes
Welcome our latest Members
sally from bankoi
neilehh from Anakie, Vic, Aussie
b33h1v3 from g3r0
Member's Birthdays Today
Suzanne from Seattle, Jack from Bayswater, Vic
Friends currently online
Want to see when your friends are online? Become a member for free.

Network Sites

Melbourne Bars Find the Hidden Bars of Melbourne
Free Crossword Puzzles Play online or print them out. 2 new crosswords daily.
Jigsaw Puzzles Play online jigsaw puzzles for free, with new pictures everyday
Sliding Puzzle Play online with your own photos
Flickr Sudoku Play sudoku with pictures from Flickr
Kakuro Play Kakuro online!
Wordoku Free Wordoku puzzles everyday.
30 Dollar Date Night - Date Ideas for Savvy Partners.
Pumpkin Carving Pattern Free halloween pumpkin carving patterns.