Proof of Tough Sudoku January 14, 2008


The following illustrated proof for the Tough Sudoku of January 14, 2008 employs a small group of Sudoku techniques, tips and tricks: Hidden Pairs, Almost Y Wing Style, Locked Candidates, and Alternating Inference Chains.

Previous blog pages may be helpful. Links to these pages are found to the right, under Previous Entries. This list is getting long, so specifically, one may want to refer to the following previous blog pages:

Many steps not illustrated are possible. To show every possible step is, well, just overkill. However, this page illustrates sufficient deduced elimination steps to both solve the puzzle, and also to prove a unique solution.

The illustrations of forbidding chains, also called Alternating Inference Chains (AIC), shown below will share this key:

  • black line = strong inference performed upon a set (strong link)
  • red line = weak inference performed upon a set (weak link)
  • black containers define a partioning of a strong set(s)
  • candidates crossed out in red = candidates proven false
Please be aware that, for me, strong and weak need not be mutually exclusive properties.

Style Change

Previously, I had abandoned using the chessboard algebraic notation in favor of the more common rc notation. However, since many people have begun again to post proofs on the tough pages, I am hereby returning to algebraic notation. I will retain some of the Eureka-like qualities of writing AICs, though. Hopefully, this does not create too much confusion for those from either group. Illustrations will include the cell descriptive labels to help with interpretation.


The Puzzle


Puzzle at Start

Three Unique Possibilities are available here:

  • (2)h3 %column & %box (hidden single in column and in box)
  • (5)c3 %box
  • (7)h2 %column & %box
  • Thus by Unique Possibilities, the puzzle is advanced to 25 cells filled, UP 25

Typically, at this point, and more so if I am solving the puzzle on paper, I prefer to search for Hidden Pairs before filling in the Possibility Matrix. There is 1 hidden pair immediately available based upon the givens.


Step 2 - Hidden Pair 15


Hidden Pair 15

Given candidates 1&5 highlit blue plus given candidates 247 in column i conspire to force candidates 1&5 into two locations in column i. Thus cells i4,i9 are limited to only 1&5. Otherwise, column i would lack one of 1,5. This forces a few more Unique Possibilities:

  • (9)e4 % row
  • (9)f3 % column & box
  • (9)i1 % row & box
  • (8)d1 % row
  • Thus, UP 29


Steps 3abc - Locked Candidates 8, 8, & 4


Some Locked Candidates


Above, the following three steps are taken:

  • 3a Locked 8's bc7 => gh7≠8
  • 3b Locked 8's bc5 => gh5≠8
  • 3c Locked 4's g23 => g56≠4

An AUR digression

Although I do not use this step, steps 3a, 3b make it hard to avoid seeing
  • (7)a6=(Hidden Pair 78)bc5-by AUR(Hidden Pair 78 bc7)=(7)a79
  • => a1≠7
  • => mental note, exactly one Hidden Pair 78 will exist at bc5, bc7
The logic: By AUR (Almost Unique Rectangle) we cannot have Hidden Pair 78 at both bc5 and bc7. Since there are no 7's possible at bc4689, (7) must exist in column a in at least one of boxes b5, b8. Of course, one can also make the same deduction using:
  • (7)b13=(Hidden Pair 78)b57-by AUR(Hidden Pair 78)c57=(7)c1
  • =>a1≠7
In my opinion, Almost Hidden Pair generated AUR deductions are more prevalent than Almost Naked Pair generated AUR deductions.

Sudoku Strategy: Puzzle Mark UP

Before marking up the puzzle, I also took the following steps that are not required:

  • Locked 1s b23 => b4578≠1
  • Locked 4s ac1 => e1≠4
  • Locked 6s g79 => g23≠6
I print out the current Possibility Matrix and mark the grid. My mark ups have evolved over time. Currently, I circle all the endpoints of bilocations sis - meaning I circle a candidate each time it has only one other location in a box, column, row. I also underline a candidate if within a row or column it has only one location in one box, but multiple locations in exacly one other box. Finally, I mark with a pointed v any deductions that I see immediately available if the underlined candidate conjugates are true.

In the mark up below, I aborted the mark up once I marked candidates 1, 2, & 3. There seemed little reason to continue!


Puzzle Mark-up


Above, once I started to mark-up candidate 3, I noted and marked:

  • (3)e6=(3)ghi6-(3=5)g5
    • Thus (3)e6 is underlined with a pointing v5 towards g5
    • I could not miss the continuation: -(5)i4=(5)d4
    • => I found a Y Wing Style35 => d4≠3
    • Thus the (3) at d4 is also crossed out.
  • (3)e9=(3)gh9, thus (3)e9 is underlined. However, an almost Y wing style struck me:
    • [(3)g9=(3-8)h9=(8)h6-(8=3)i6] -(3=5)g5
    • => (3)e9=(5)g5
    • Thus, I also placed v5 by (3)e9 pointing at g5.
  • Since (3)e6-(3)e9, and since both are marked with the same strong inference: =(5)g5,
    • (5)g5 was a certainty.
    • (5)g5 seemed likely to advance the puzzle quite far, and the deduction was only depth 4
  • 'Twas time to stop and record the advances

The idea of the mark-up that I use is to bring to fore hidden strengths. Thus, circled candidates are noted, but generally not v'd because this would over populate the grid. The Possibility Matrix is already biased to expose Naked strengths (cells). The most difficult essentially bivalue strengths to find for me are those derived from the underlined candidates. Thus, if they seem to be easily linked, they get the v's. However, if the mark-up starts to get too populated with marks, I generally retain the v's, but make notes instead of marking the possibility matrix. Thus, for this puzzle, my notes would have already included a1≠7 by AUR. Note also that the mark-up was updated not only with d4≠3 but also with the immediate locked candidate deduction that followed, and the stronger 3's in columns bcd underlined at d5, bc4.

There are many ways to get hidden information out of the Possibility Matrix. I believe one should toy with which manner works well for the individual. Oftentimes, I change my mark-up technique slightly to suit the particular puzzle.


Step 3d - Basically a partially hidden xyz chain


Z type chain


The elimination graphed above has many interpretations possible. The way I found it would be written:

  • (3)ghi6=(3)e6-(3*)e9=[(3)g9=*(3-8)h9=(8)h6-(8=3)i6 =>
    • (3)ghi6=[(3)g9=(3)i6] => g5≠3
  • However, one may prefer:
  • (3=8)i6-(8)h6=(8-3*)h9=[Finned X wing candidate 3: g9=*e9-e6=ghi6]
    • => g5≠3
    • This latter representation is more likely to be found if one is counting, or actively looking for almost coloring steps.
Probably, the latter representation is more acceptable to some, as it uses well-defined AIC fragments. However, the Almost Y Wing Style is a favorite fragment of mine. If one uses counting, then no knowledge of any fragments is required - but - I think fragment recognition speeds the process tremendously.

After making the elimination, (5)g5 % cell causes a cascade of hidden and then naked singles to the end.


Solution


Done


Notes

Puzzle spectrum:

  • Sets: (3)1+(2)+(4) = 9
  • Max depth 4 at step 3d.
  • Rating: (3).01 + .03 + .15 = .21 - certainly not worthy of SE 8.3 rating!
Probably, this is one of those puzzles that just happened to have the type of chain available that is easy for me to stumble upon.

This puzzle may be about right for a tough. It cannot be solved without resorting to something beyond the standard pairs, triples, locked candidates. As is often the case, the awareness of Y wing Styles, and techniques much like them, quickly keys the solution.




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

Hi Steve,

Thanks for your works again!
I posted my way to solve puzzles on tough page, but sometime solution's too long...Can you give other way better in those case?
09/Feb/08 3:14 PM
 |  |
Thank you Steve, I wanted very much to see a solution to this particular puzzle. Some of us had a discussion of it and I was determined to keep at this one till someone found a proof. It was also very helpful to read exactly how you did the markup. This was something that had not been clear to More...
09/Feb/08 7:29 PM
 |  |
Steve,

Thanks for the solution. I had been able to work this one on my own, but your solution is shorter and cleaner. Now that the blog is back, I have a lot to catch up on.

One question: now that some of the puzzles apparently require matrices (11/28/07 for example), can we More...
10/Feb/08 6:39 AM
 |  |
Hi Thomas!
I think that the label "trial and error" is dependent much upon how an elimination is found.

If one never actually plugs in a candidate, but instead using some other way to analyze, then probably one can dodge the t&e label.

Since my struggles with EM, I More...
10/Feb/08 1:16 PM
 |  |
Jeff and ttt!
You are both most welcome.

ttt - most of your proofs seem quite excellent. I am not sure what you would like for me to do?

Sometimes, a puzzle requires a long proof. One can often trade number of steps for depth of steps. I have preferred shorter steps, but some prefer less steps.
10/Feb/08 1:18 PM
 |  |
Hi Steve,

Before I post my way to solve puzzle I try to find the best way but sometime... as Dave's solution on Feb. 04/08. If you have time you can correct me to the best way, that is what I mean.
Thanks
11/Feb/08 12:47 AM
 |  |
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
efuimaono from ELISAPETA FUIMAONO
NewVision from South Florida
supremechemicalsltd from Dr.Michael Paul
Member's Birthdays Today
None Today.
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.