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 Sudoku Techniques. 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

ttt  From vietnam
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
Jeff  From Maryland
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 me in the past. I will go back now and reread the pages concerning y-wings/y-wing styles, and all concerning finding chains. I hope Joanne from Fairview sees this proof, I know she put some effort into looking for a proof. Thanks again Steve.
09/Feb/08 7:29 PM
Thomas Kimble  From USA
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 really call this method pure logic? It seems to me that the distinction is arbitrary. Pattern Overlay is usually considered 'deductive' while table conflict is 'trial and error.' I think matrices fit somewhere in between. Personally, I think ALL of these methods should be deemed trial and error methods.
10/Feb/08 6:39 AM
Steve  From Ohio    Supporting Member
Check out my page
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 have been trying to use what I think to be a non-assumptive and non-trial and error method to find deductions which are expressed best with matrices.

I think that merely counting links works - and just keeping track of matrix rows versus matrix columns. In fact, one does not even need to have a target. In my current solution for 1/15, I found several matrix type steps that were located with no target in mind. Thus, only after knowing the grid was constricted did the target even become known. I do not find such a search to be trial and error. This, however, may not be the opinion of others.

In any event, there really is nothing illogical about even trial and error. Trial and error is logical - and even purely logical. It is not, however, very elegant.

That lack of elegance can also be ascribed to my counting method. Perhaps after some practice, it will feel more elegant. The need for counting is so rare, that I have not practiced with it sufficiently to really use it well.
10/Feb/08 1:16 PM
Steve  From Ohio    Supporting Member
Check out my page
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
ttt  From vietnam
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.

Join Now Login