Easy Proof for the Tough? 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 Previous Entries.

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


PUzzle 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


PUzzle at 25 cells solved before possibility matrix

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


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


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


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


Two string kite with 3's

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

Two string kite with 3's

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

Puzzle at 37 cells solved using only % cells

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

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

UP 81



Proof in my usual style, pared down

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




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

Clearly, this style of proof presentation is very long. When I return to more complex puzzle proofs, the details will become more sparse - out of necessity. Please feel free to suggest what type of details you would like to see on more complex proofs.

 |  |
Why do you have a red line (weak link) between the 3's in g2 and g4? Shouldn't this be a strong link (3 must exist in at least one of the endpoints)?
 |  |
Steve,

I have posted a proof for the tough puzzle of Feb. 10, 2007. When you have time, would appreciate your critique.
Thanks
 |  |
Hey buddy!. Ya know, I set my sudoku program to conform to the alignment used on this website. I had no idea I messed up on the row numbering. I fixed it. I doubt I'll make more sense, but at least I'll be correctly citing the cells now :P
my g8 in my startup help on the 2/13/tough page was More...
 |  |
Hi BD!
Although other sudoku sites try to make strong and weak mutually exclusive properties, there is no logical reason to do so.
The relationship, especially for the purposes of chaining, between two chain pieces is often both:
At least one of.... At most one of.... (therefor exactly one More...
 |  |
Hi Dave!
Thanks for the info. Detailed notes have been made on that page - probably too much detail!
 |  |
Hi Morgan!
Hopefully, the change in grid labels is not too much of a hindrance.
Moreover, hopefully the different point of view that I take towards sudoku in general will help in finding some things that perhaps were previously obscure for you. My general take on sudoku is, IMO, a general More...
 |  |
Thanks to your diagrams and explanations, I finally understood the fc on the 3's. Until I get better at this, I think I'll have to print out the tough puzzles, at the point where I get stuck, and draw lines. :)
 |  |
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
Brought to you by the same team that put the
Cheap Flights into IWantThatFlight.com.au
Check out all the Daily Horoscopes
Welcome our latest Members
Eureka52 from Skygardens
dkj08112007 from today
dutch sandgroper from carine
Member's Birthdays Today
Sandra from IN
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.