Easy Proof of Tough Sudoku March 31,2008

The following illustrated proof for the Tough Sudoku of March 31, 2008 employs a small group of Sudoku techniques, tips and tricks: Hidden Pairs, Hidden Triplet, 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

Zero Unique Possibilities are available here. However, I can identify a Hidden Pair without considering the Possibility Matrix. Note:

  1. (5)e2,(9)h2
  2. (5)b8, (9)b7
  • => (5)a1=(5-9)c3=(9)a1.
  • => step 1a Hidden pair 59 at a1,c3
  • => a1,c3 are limited to only 5,9


Steps 1b & 1c - Locked Candidates 5 & 9


Some Locked Candidates


Above, two easy steps are illustrated:

  • step 1b Locked candidate 5 at df5 in box e5 (box 5) => ahi5≠5
  • step 1c Locked candidate 9 at eh6 in box e5 (box 5) => e139≠9
The symmetry of these eliminations, plus the already found Hidden Pair 59 in step 1a caused me to muse for a bit about Uniqueness of solution with this puzzle. What follows immediately below is basically a digression, but it helps to reveal how I quickly came to solve this puzzle.


A uniqueness digression

Once upon a time, I stayed away from Uniqueness of Solution as a solving technique. Eventually, I changed my mind. The main reason for changing my mind follows:

  • Every puzzle that I have tried to solve over the last few years had exactly one solution
  • My mind processes much about pattern recognition without my awareness
  • The process of knowing where to look is filtered by my experience
  • => My experience is inescapably prejudiced by uniqueness of solution
  • => I am using uniqueness of solution, whether I want to or not
  • If I cannot avoid using uniqueness of solution behind the scenes in my mind, I may as well use it explicitly.


Puzzle Mark-up


Below, find a typical puzzle Mark-up. Note that I include the eliminations from three more locked candidate steps. These steps are not required to solve this puzzle. However, they did help me locate where to look.

Puzzle Marks


While making the puzzle marks, I thought about a possible MUGgish deduction. Also, one could have viewed it as a BUG. However, what I found with very little thought was a long chain involving an Almost Unique Rectangle. Although I do not use the following chain in my solution, it quickly let me see how to proceed with this puzzle. There were several other chains that I uncovered during the process of marking the puzzle. Typically, a small amount of time investigating potential chains during the puzzle mark-up phase pays significant dividends later. The puzzle becomes burned into my brain. I can then manipulate chains with much greater ease. Here is what I found:

  • (Triplet 458)adf5=(3)a5-(3)a79=(hidden pair 36)b9c7-(2)b9=(2)b3-(2=9)d3-(9)c3=(Xwing 9)ce46
  • With an Xwing contained in two boxes, there may exist a hidden AUR deduction. Here I continued:
  • -(Xwing 8)ce46=[(8)af5=(hidden triplet 589)a146-(1)a46=(1-2)a2.....]
I did not make any eliminations, nor reach any certain conclusions. However, I exposed some potential puzzle weaknesses. This is often the case with musings. Now, the finished puzzle mark-up combined with that chain going nowhere focused my search. Specically, I know now that (1)box b2 determination will significantly unlock the puzzle. Fortunately, this is easily resolved. In fact, I did not need to complete the puzzle mark-up - but decided to do so for illustration purposes.

Do not worry if you cannot follow my logic above. It is the result of solving far too many Sudokus. What follows below can be located without the Uniqueness Digression. However, I wanted to include the digression, as often I am asked to explain how to determine where to look. The answer is not simple, nor always the same. However, in a general fashion it can be said to be exploring chain snippets.

Step 1d - A Hidden Y Wing Style


Y wing style merely refers to any chain that contains exactly three strong inferences. The logic below is exactly like a standard Y wing, except that in this case only hidden strengths are considered. The mark-up exposes hidden strengths, and their intersections. In practice, I see from the mark-up (1)b1%chain.

Hidden Y Wing style


Above, find:

  • (2)a2=(2-6)d2=(6-1)d1=(1)b1
  • => a2≠1
Thus, one cell is solved: (1)b1 %box.


step 2a - Hidden Triple 159


Hidden Triple 159

On the left, since candidates 1,5,9 are limited to three locations in column a, no other candidates can exist in cells a1,a4,a6. After making these eliminations, my previous musings ascertain that (8)a5=(8)f5. In fact, I actually conclude in my head (8)a5%chain. However, there is a short path to reach eventually most of the same conclusions. The musings merely focused my search, again. The result of this directed search can be seen in the next step.

step 2b - An easy depth 4 chain.


Depth 4 AIC

After eliminating (8)from a46, the relationship (8)a5=(8)a78 is created. This relationship has a clear continuation in every direction. On the left, I have illustrated one of these:

  • (8)a5=(8)a78-(8=4)c8-(4)d8=(4-5)d5=(5)f5
  • => f5≠8
From this point, a small cascade of cells can be solved:
  • (5)f5 %cell
  • (4)d5 %cell
  • (4)e9 %box,column
  • (8)f3 % column
  • (3)e1 %cell
  • (5)d7 %column, box
Thus, UP 30.


Step 3 - another easy depth 4 AIC


After solving the cells indicated above, the following new information led me to find the chain below:

  • New Bivalue (2=7)e7
  • New Bilocation (4)a2=(4)a8

One last AIC


Above, find:

  • (2)b3=(2-4)a2=(4-7)a8=(7)f8-(7=2)e7
  • => e3≠2
This causes a cascade of mostly naked singles to puzzle completion.


Solution


Solution


Below, find the rating data that I think is still relevant for easy tough puzzles:

  • Strong inference sets considered: 2+1+1+3+4+4 = 15
  • Maximum depth: 4. Twice.
  • Rating: .42
A rating of .42, in my experience, means a pleasurable puzzle that will not consume too much time. However, it is also challenging enough to preclude boredom.

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

ttt  From vietnam
Check out my page
Hi Steve,
The best solution and too… fast!
You didnot get me a chance… . You wrote : “certainly not worthy of SE 8.3 rating!”, for me today puzzle easier to find and present as chains than Jan. 14-08
Thanks
31/Mar/08 2:03 AM
Steve  From Ohio    Supporting Member
Check out my page
Sorry about the speed, ttt. Gath lets me cheat occasionally and view a puzzle ahead of publish time. That helps produce a pertinent blog page, but does make things seem super fast. I am not that fast!

Jan14-08 I rated at .21. This one probably does seem easier, although I rated it .42. The ease or lack of ease for jan14 puzzle is entirely dependent upon finding the xyz wing-like chain. I suppose I just was lucky!

I also suppose that the a really good rating system is likely beyond reach. I like depth, as it can be measured precisely. However, it does not seem to quite put a fine enough point on difficulty. Also, it is arbitrary to consider how to weigh depth.

Suffice it to say that neither puzzle is too difficult.
31/Mar/08 5:29 AM
Neil  From UK-Hertfordshire
Check out my page
Hi Steve and ttt,

As a relative newcomer to these Tough Sudokus (I joined in January 2008), I would have thought that the variety of solution types (eg, naked pairs, locked sets, hidden pairs, X-Wings, XY-Wings, XYZ-Wings)was the clue to the difficulty - please note 'variety', as that is what I think is the key. Please advise me if you think that I am wrong.

Very best Regards,

Neil
~
31/Mar/08 10:45 PM
Steve  From Ohio    Supporting Member
Check out my page
Great comment Neil!

There really is no concensus regarding difficulty. I may be the only person on this planet that only considers depth. My reasons for this are rather simple: It is measurable.

Other concepts, such as variety of techniques, etc. may also be measurable. Depending on the skill level of the solver, these measures may seem more relevant.

In my opinion, eventually puzzle difficulty becomes a function of how hard one must look to find elminations. Unfortunately, that measure is entirely dependent on how one chooses to look.

The ratings I provide are therefor not universal, nor are they worth much. They can form a rough comparison. Emphasis on rough.
01/Apr/08 2:08 AM
darrylagsu  From Corona, CA
Check out my page
Hi Steve. How long did it take you to solve the puzzle? And how long on average for the 'Tough' puzzles? Thanks.
07/Apr/08 8:05 AM
Steve  From Ohio    Supporting Member
Check out my page
Hi Darrylagsu!
I do not time myself, so I have only a vague idea. I am not trying to solve quickly.
If I intend to publish a proof or solution, some time is spent tracking what I have done. I doubt that the numbers would mean much, unless they were compared with someone who also was tracing their steps.
I tend to study a puzzle and look for the shortest path to solve it. By shortest, I mean the least deep/complex path. This study is not time efficient.
This particular puzzle probably took me about 20-30 minutes to solve and track path. Blogging it adds about 4 hours.
The median time for tough puzzles is probably around 20 minutes. The average is much higher, as a puzzle such as November 28, 2007 would have been much longer. Guessing with a puzzle like that is clearly more time efficient. I do not use guesses.

07/Apr/08 9:03 AM
darrylagsu  From Corona, CA
Check out my page
Hi Steve,
I am starting to get the hang of forbidding chains, but it is not unusual for am elimination not to advance the puzzle very far at all (I'll find 5 chains, then one completely independent from the other eleminations that unlocks the puzzle). Do you target specific candidates for elimination, try a chain and then ignore it if the elimination is not important, or just know by experience which chains will be useful? Thanks.
12/Apr/08 12:55 PM
Steve  From Ohio    Supporting Member
Check out my page
Hi Darrylagsu,
I do not target specific candidates for elimination. However, I do begin my search in an area that I suspect will powerfully influence puzzle progress. Some of this general area targetting is based upon a puzzle mark-up. Mostly, it is just a general "feel" that I suspect is the result of solving too many sudokus.

In my blogged proofs, I delete the steps that did not further the puzzle. In general, about 30% of the chains that I find are very useful, and the balance are not very useful. I never, however, completely ignore an elimination, as the pattern that caused the elimination is in itself a clue as to where one should look. The exact nature of that clue is hard to describe. However, it can tell one much about which future chains will be valuable towards achieving a solution.
13/Apr/08 11:25 AM
ttt  From vietnam
Check out my page
Hi Steve,
I don't know why you are absent..., for me It's loong times. Something is good? I hope so...
09/May/08 2:46 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