Proof of Tough Sudoku for March 30, 2007


The following is an illustrated proof for the Tough Sudoku of March 30, 2007. This proof uses only Forbidding Chains, also called Alternating Inference Chains or AIC.

You may wish to refer to previous blog pages to properly understand this proof. Links to these pages are found to the right, under Previous Entries.

At many times during this illustration, there are other steps available. Some easy steps are not taken, nor illustrated. This page only illustrates steps that, taken together, unlock this puzzle.

The information on the following blog pages may be helpful:

The illustrations of forbidding chains used in this proof will share the same 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
  • candidates crossed out in red = candidates proven false
Strong and weak need not be mutually exclusive properties.


Puzzle at start


Puzzle start

A few Unique Possibilities are available here:

  • h7 = 7% box & column (hidden singleton both in box and column)
  • h8 = 4% box & column
  • c7 = 4% box & row


Hidden Pair 49, Hidden Triple 279, Locked Candidates 3, 5, & 7


A few steps at once

Quite often, Hidden sets are easier to find before entering the possibilities.

Illustrated to the left, g5=4 and c5=9 conspire to force only 49 at d4,f6.

Clearly, then, candidates 357 must be locked at def5, thus one has the eliminations noted in row 5.

It is rare that one will find a hidden triple without considering the possibilities.

While looking for Hidden Pairs, I noticed the almost Hidden Pair 27, illustrated in orange, at e23,f3. Since I can also see that the 9s are locked in box e2 because e23 are the only places left for 9 in column e, not only can I eliminate 9 from the rest of box e2, but I also can place the Hidden Triple at e23f3 as shown.

A few Unique Possibilities are available after a5≠357:

  • a5 = 2% cell (naked single)
  • c8 = 2% column & box
  • i4 = 2% row & box

An alternate approach to finding the Hidden Triple above:

  • Find the Locked 9s at e23 => d123f13≠9
  • Fill in the possibilities
  • Find the naked quad 1468 at d123f1 => e23,f2 are reduced as shown

There is some value to recognizing that one has the Hidden Triple indicated above based only upon the information cited: c5,a7,i8=9(thus locked 9s at e23); bi1=27; d68=27. Very rarely, one may use such a group of conditions within a chain to justify an Almost Hidden Triple, eliminating a key value from one of the Hidden Triple cells. Admittedly, that concept is advanced, and somewhat obscure. Fortunately, this puzzle does not require any sort of logic that advanced.


Locked candidate 9


Locked 9s

Above, the 9s at gh1 are the only 9s possible in row 1. Since gh1 are both in box h2, one can safely remove 9 from cells g2,h2,g3. I have chosen to illustrate this elimination as a forbidding chain:

  • g1=9 == h1=9 => gh2,g3≠9


Naked Pair 13


Pair 13

Above, the naked pair 13 at hi2 is illustrated as a continuous nice loop forbidding chain:

  • h2=1 == h2=3 -- i2=3 == i2=1 =>
    • h2=1 == i2=1 => bdg2, gh1, g3 ≠1
    • h2=3 == i2=3 => bcg2,g3 ≠3
One now can solve g2 = 2% cell.


Coloring with candidate 4


Coloring with 4s

The forbidding chain with candidate 4:

  • b2 == d2 -- d4 == f6 => b6≠4
is a typical coloring elimination. The logic can also be viewed as follows:
  • b2=4 => b6≠4
  • b2≠4 => d2=4 => d4≠4 => f6=4 => b6≠4
This step is a set up for the fist truly difficult step.


Forbidding chain using candidates 4,7,9


Depth 4 chain using 479


The elimination above can be written as the following forbidding chain:

  • b4=4 == b2=4 -- b2=9 == e2=9 -- e2=7 == bc2=7 -- a3=7 == a6=7 => a6≠4
The only difficult item about this chain is the grouped argument with the 7s in row 2. They are grouped according to their location at cell e2 versus box b2 (at cells bc2). Using Eureka notation, but maintaining the grid coordinate system that I use, the elimination could be written: (corrected later, many thanks to David!)
  • (7)a6 = (7)a3 - (7)bc2 = (7-9)e2 = (9-4)b2 = (4)b4 => a6≠4
Let me know if this notation is preferable here.

Regardless of the notation system, this elimination can also be understood as follows:

  • a6=7 => a6≠4
  • a6≠7 => a3=7 => bc2 do not contain 7 => e2=7 =>
  • e2≠9 => b2=9 => b2≠4 => b4=4 => a6≠4
After making this elimination, a few cells solve:
  • f6 = 4% row
  • d4 = 9% cell & box
  • f9 = 9% column & box


Forbidding chain using candidates 1, 2, 9


Depth 4 chain using 129


Illustrated above, once again the chain uses one grouped argument, this time involving candidate 1. As a forbidding chain:

  • e8=1 == e7=1 -- e7=2 == e3=2 -- e3=9 == b3=9 -- b3=1 == a13=1 => a8≠1
In my puzzle mark-up for this position, the 1 at b3 was underlined, with a V next to it, pointing at cell a8. This was a great clue that not only this chain existed, but also that it would at least solve one cell: c8=3% cell.

One may note above that I did not bother to eliminate the 1s from d79 caused by the locked 1s at e78. This elimination, and some other easy eliminations available here, are not significant, one way or the other, to this puzzle proof.


Naked Pair 68


Pair 68





Illustrated to the left as a continuous nice loop forbidding chain, the naked pair 68 at f18 forbids 68 from f7.


Coloring with candidate 8


2 string kite with 8


Illustrated above as a forbidding chain using candidate 8:

  • g3 == d3 -- f1 == f8 => g8≠8
This elimination is a required set up for the final non-native elimination step.


Forbidding chain using candidates 6, 7, 8


Depth 4 chain using 678


The forbidding chain:

  • c2=6 == c1=6 -- f1=6 == f8=6 -- f8=8 == b2=8 -- c9=8 == c9=7 => c2≠7
causes a cascade of Unique Possibilities (mostly naked singles, a few hidden ones) until the puzzle is finished.


Proof

This proof is not the exact path that I illustrated, but functionally the same.

  1. Start at 22 filled - the given puzzle. Unique Possibilities to 25 filled. (UP 25).
  2. Naked triple 357 at def5 forbids abhi5,d5f6=3 & ahi5,d4=5 & ab5f6=7 UP 28
    1. Hidden triple 279 at e23f3 forbids e23=1,f3=8,d132f13=9
    2. Locked 9s at gh1 forbids h2g23=9
    3. Pair 13 at hi2 forbids bdg2,g13h1=1 & bc2,g23=3 UP 29
    1. fc on 4s:b2 == d2 -- d4 == f6 forbids b6=4
    2. b4=4 == b2=4 -- b2=9 == e2=9 -- e2=7 == bc2=7 --a3=7 == a6=7 forbids a6=4 UP 32
  3. e8=1 == e7=1 -- e7=2 == e3=2 -- e3=9 == b3=9 -- b3=1 == b89=1 forbids a8=1, d79=1 UP 33
    1. Pair 68 at f18 forbids f7=68
    2. fc on 8s: g3 == d3 -- f1 == f8 forbids g8=8
    3. c2=6 == c1=6 -- f1=6 == f8=6 -- f8=8 == b2=8 -- a9=8 == a9=7 forbids c2=7 UP 81
  • Sets: 3 + 3 + 1 + 2 + 2 + 4 + 4 + 2 + 2 + 4 = 27
  • Max depth 4, three times
  • Rating: .01 + 4(.03) + 2(.07) + 3(.15) = .72
This puzzle is quite tough, but not monstrous or diabolical.

One could fool around with the steps and achieve a rating of .70 by using the Hidden pair 49 and 3 locked candidate eliminations versus the naked triple 357. Since this took more space, I choose the latter. I suppose that now I have consumed the space saved!


Notes

This puzzle is standard forbidding chain fare. Nothing really exceptional about it. A workman-like approach to tackling this one will solve it.

If one prefers fewer steps of greater depth, there are quite a few other possible paths to take. I found a large number of depth 5 and depth 6, and even some depth 7 or 8, forbidding chains. In fact, an advanced forbidding chain of about depth 8 or 9 is possible at UP 29 that forbids c2=7 and reduces the puzzle to Unique Possibilities. My preference is more chains of lesser depth, but others may well prefer fewer chains of greater depth.

Please let me know of interesting alternative proofs to this one, as I strongly suspect many are possible. I feel that I missed something easy here, and that this particular proof does not represent my best work!




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

Hi Steve, Thanks for your answer about prioritising fcs. Funnily enough, just after I'd posted that comment, I saw in the archives (~Jan-06) a comment made by you about the same thing (cheered me no end!) To target the elimination of a certain number, I've tried working backwards usually to find More...
30/Mar/07 2:36 PM
 |  |
Steve, another quick question - as I understand it, any values (of the same value as starting off or end points) which can see both ends of the chain can be eliminated. Is this invariably so or are there exceptions? I have found this doesnt always work, and sometimes, when in doubt try the More...
30/Mar/07 2:58 PM
 |  |
Hi Giblet!
A forbidding chain that starts with f4=3, and ends with d5=6:
Given only that information, one could say that:
f4=3 == d5=6.
The only things one can say for sure that are thus eliminated then are: f4=6, d5=3.

A forbidding chain, if done correctly, cannot yield false More...
30/Mar/07 4:47 PM
 |  |
Hi Giblet!
I too wish that the exchange of ideas - especially sudoku ideas - at this site could return with the energy that once existed here.
Thank-you for posting a proof in an attempt to help that return.

Some comments on your chains, More...
30/Mar/07 5:02 PM
 |  |
Steve, Thanks for looking at the chains and your comments -they definitely need a bit more work! Cheers.
30/Mar/07 8:09 PM
 |  |
Steve the correct Eureka notation for that chain would be:
(7)a6 = (7)a3 - (7)bc2 = (7-9)e2 = (9-4)b2 = (4)b4 => a6 <> 4
Here
a) - & = show the weak and strong inferences used
b) (linking digits)CellAdress order is used
c) cell addresses containing internal links don't More...
30/Mar/07 8:34 PM
 |  |
Thanks David!
I shall endeavor to study better the Eureka notation, so that if I use it in the future, I use it correctly.
Also, I suppose I should correct the page!
30/Mar/07 10:44 PM
 |  |
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
PumpkinFace from PA
messipicane from Cameroon
Aurelia from La Mesa
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.