The following is an illustrated proof for the
Tough Sudoku of February 13, 2007.
Since this is an easy tough puzzle, it is perfectly well suited for study of the limited
techniques required.
Since this proof uses a Locked candidate, some
Hidden Pairs, and 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 Sudoku Techniques.
At many times during this illustration, there are other steps available. It is not the goal
of this page to show every possible step, but rather to illustrate steps that, taken together,
unlock this puzzle
Of great importance, in my opinion, is the coloring step. By coloring, I mean a forbidding
chain on just one candidate. If one studies coloring, one can learn just about everything one
really needs to know in order to perform forbidding chains on more than one type of candidate.
Forbidding chains on just one type of candidate can get very complex. The example today is very
simple.
Puzzle at start
A few Unique Possibilities:
- i7 = 2% column
- c6 = 6% box & row
- a5 = 9% box
i7 = 2% column means i7=2 because it is the only possible place for 2 in column i.
c6 = 6% box & row means that c6=6 because it is the only possible place for 6 in
both box b5 and row 6. Of course, recognition of just one of those two constraints is sufficient
to solve cell c6=6. a5 = 9% box occurs only after the previous assignment of c6=6.
Singletons in a container (house) are also called Unique Possibilities.
Puzzle at UP 25
UP 25 means that by unique possibilities the puzzle has been advanced to 25 cells solved.
At this point, before enteriing the possibilities, I like to look for Hidden Sets. Of these,
Hidden Pairs are the easiest to find. To find Hidden Pairs before entering the possibilities,
look for symmetry in the placement of two different candidates relative to a single large
container (box, row, column).
Hidden Pair 58
Note the following:
- In row 2, both 5 & 8 are excluded in box h2, row 2 (cells ghi2)
- In column i, both 5 & 8 are excluded in box h2, column i (cells i123)
- Therefor, g1 and g3 are the only two places left in box h2 for both 5 & 8
If something other than 58 were to exist in cell g1 or cell g3, there would not be enough places
left in box h2 for either 5 or 8. Therefor, one can safely limit g13 to being only 58. Also,
one now has both 5's and 8's locked in column g. Thus, 58 cannot exist at g46789.
The alignment of 58 in row 2 and column i relative to box h2 is what I mean by relative
symmetry of those two candidates regarding a large container.
At this point, one could immediately make the step that serves to unlock this puzzle. Instead
of immediately doing that, I will first illustrate some more hidden pairs.
Hidden Pair 15
Note the following:
- e8=1 and i8=5 excludes 15 from cell f8
- d1=1 and e2=5 excludes 15 from cells f123
- Thus, in column f, the only two places remaining for 15 are cells f45
Here the symmetry is a bit different, but the concept is exactly the same. Once again, one can
also use the locked candidates property of the 15's. Here, though, 15 is locked into column f
and thus forbidden from the rest of the box e5. (d56≠5).
Hidden Pair 23
The Hidden Pair 23 illustrated to the left is just a bit more complex to see. To find it,
one needs to recognize three symmetrical locations for 23 relative to row 4.
The next plan of attack
At this point, since the three hidden pairs that have been found have not led to any more
Unique Possibilities, it is generally time to consider the possibility matrix. While filling in
the possibility matrix, I would look for locked canididate eliminations and not fill in candidates
already forbidden by that technique. After completing the possibility matrix, naked sets are
generally obvious, so the eliminations provided by considering naked pairs, triples, etc. would
be next.
However, with this particular puzzle, the search for Hidden Pairs also helps to uncover
a coloring elimination before even entering the possibilities. Even if
one does not see the coloring, (forbidding chain on just one type of candidate), elimination
at this time, I highly recommend a coloring search before looking for other forbidding chains.
Why? Because forbidding chains on just one type of candidate are fairly easy to find. Also, they
occur with relative frequency.
Please note that the term coloring has been expanded at many sudoku sites to include just about
everything, and is no longer limited to just one type of candidate. I am not sure why this is done,
but it serves to make the term almost meaningless - since with coloring generalized to this extent,
one could justify any elimination - if it is taken to the logical extreme.
For this reason, when I say coloring, I mean that I am considering only one type
of candidate.
Coloring with Candidate 3
Key:
- Highlit cells = all possible locations for 3 in all boxes except b2, b8.
- * = important possible locations for 3 in this step
- black lines = strong links
- candidate 3 must exist at at least one of the endpoints of the black lines
- red lines = weak links
- candidate 3 cannot exist at both of the endoints of the red lines
- White X = cell from which 3 is excluded
There are many ways one can interpret the information above. Although I prefer a forbidding
chain type of interpretation, (primarily because once one understands forbidding chains, almost
all techniques are also understandable), here is another way to look at the graph above
(also called a two string kite):
- Suppose g4=3, then clearly
- Suppose g4≠3, then
- e4=3, as e4 is the only place left for 3 in row 4
- e4=3 prevents d5=3
- d5≠3 forces d2=3, as d2 is the only place left for 3 in column d
- d2=3 also means g2≠3
- Conclude whether g4=3 or g4≠3, g2≠3.
Another way to look at the graph above:
- Suppose g2=3, then
- g4≠3 and d2≠3 thus
- both d5=3% column and e4=3% row
- But, this leaves two 3's in box e5
- thus g2=3 must be false
There are still other ways to prove the same elimination given the information graphed above.
All of them, however, will involve the interplay between two sudoku rules:
- At least one of each candidate must appear in each row, column, box.
- At most one of each candidate can appear in each row, column, box.
For this reason, I prefer the language of forbidding chains, as it specifically uses the
interplay between the rules of
At least one of.... and
At most one of.....
A forbidding chain (also called Alternating Inference Chain, or AIC) writing of this step is
a bit more efficient:
- fc on 3's: g4=3 == e4=3 -- d5=3 == d2=3 forbids g2=3
Here, == merely means at least one of the endpoints must be true. -- merely means at most one
of the endpoints can be true. One interprets the chain as three statements:
- g4=3 == e4=3
- e4=3 -- d5=3
- d5=3 == d2=3
The endpoints of an alternating weak and strong link chain like this one are proven, by theorem,
to be strong. In other words, from the chain:
- fc on 3's: g4=3 == e4=3 -- d5=3 == d2=3
One can conclude:
This conclusion means that at least one of g4=3, d2=3 must be true. Therefor, anything
that would force both g4≠3 and d2≠3 must be false. In this case, since g2=3 would do
precisely that, it cannot occur.
Probably, until one practices much, finding such an elimination before entering the
possibilities will be problematic.
Possibility matrix after the hidden pairs, but before the forbidding chain
Above, all the possible locations for candidate 3 are higlit. The precise pattern illustrated
previously exists. I have chosen, however, to illustrate the same elimination using one different
strong set. Key:
- Black circles = endpoints of strong sets (At least one of the endpoints is true
- Green lines = strong links between these endpoints
- Red lines = weak links. (no more than one of the two endpoints of a weak link can be
true)
- Very highlit cell = focus of chain endpoints => g2≠3
The logic here is the same, bascially, as before, except this graph uses the strong relationship
between g4=3 and i5=3 in box h5. It is very common that there is more than one way to perform the
exact same elimination. To find such an elimination, look for strong endpoints that share a house.
In the case illustrated above, both d5=3 and i5=3 are strong endpoints in row 5. However, they
are not strong with each other. This type of relationship is a common marker for many
forbidding chains. That is why my puzzle mark-up circles such endpoints.
Obviously, there are other eliminations above (such as naked pair 57 at h46). Again, it is
not the goal here to illustrate every possibly elimination.
After g2≠3, %cells advance the puzzle to 37 filled. In other words, the puzzle will have
singletons in a cell until 37 cells are solved.
Puzzle at 37 cells solved
Here one needs to find some hidden singles to continue a bit further: Some of these are:
- f8 = 7% column & box
- c2 = 1% row & box
- e9 = 9% box (only after f8=7, of course)
- etc
A combination of Hidden singles (singles in a box, row, column) and naked singles (singles in
a cell), get the puzzle to 48 cells solved. (UP 48)
Puzzle at UP 48
After the Unique Possibilities are exhausted, the Locked candidates elimination with 9's
illustrated above is sufficient to unlock the puzzle. Above, since the 9's in box h2 are limited to cells
g2 and h2, no 9's can exist in the rest of row 2 outside of box h2. If they did, then there
would be no place for 9's in box h2. Thus, f2≠9. The puzzle will now solve with
%cells to the end. (UP 81)
A step such as this last one can also be written as a forbidding chain - a very short chain:
- g2=9 == h2=9 forbids f2=9
Alternatively, I would usually write:
- Locked 9's at gh2 forbids f2=9
Solved Puzzle
Proof in my usual style, pared down
- Start at 22 filled - the given puzzle. Unique Possibilities to 25 filled. (UP 25).
- Hidden pair 58 at g13 forbids g46=5, g789=8, g1=3479, g3=349
- fc on 3's: g4 == e4 -- d5 == d2 forbids g2=3 UP 48
- Locked 9's at gh2 forbids f2=9 UP 81
- Sets: 2+2+1 = 5
- Max depth 2
- Rating: .03 + .03 +.01 = .07 (not tough)