Easy Proof for the Tough Sudoku of February 13, 2007

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

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

Hidden Pair 58

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

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

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
  • g2≠3
• 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:

1. At least one of each candidate must appear in each row, column, box.
2. 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:

1. g4=3 == e4=3
2. e4=3 -- d5=3
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:

• g4=3 == d2=3

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

1. Start at 22 filled - the given puzzle. Unique Possibilities to 25 filled. (UP 25).
2. 1. Hidden pair 58 at g13 forbids g46=5, g789=8, g1=3479, g3=349
   2. fc on 3's: g4 == e4 -- d5 == d2 forbids g2=3 UP 48
3. 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)