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

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

giblet  From victoria
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 that you have to get rid of something else first and to get rid of that one etc etc unto the fourth generation, (Is this worth doing at all?)

Here is a 'proof' of today's puzzle. It's the first proof I've tried to write out, and is probably a bit dodgy although I'm not sure where, so feel free to tear it to shreds.

After setting up but before entering all possibilities:
h9=4, h8=7, c8=2, a5=2, i4=2. A naked triple @def5, and pairs of 49s @ d4 and f6.
After entering possibilities-
fc g8=5==e8=5--e5=5==e5=7--f5=7==f5=3 eliminates 3 from f8
g8=5==e8=5--e5=5==e5=7--f5=7==f5=3--d5=3==d5=5--d9=5 Therefore e8=5??
Quad 4689 at f489 elininations cause f7 (or is it f1? can'tead my writing) to =2
Pair 29 at e23 eliminates from box e2
b3=9==b2=9--e2=9==e2=2--e3=2==e3=9 elims 9 from g3
b2=4==d2=4--d4=4==d4=9--f6=9==f6=4 elims 4 from b6
f6=4, f8=9, d4=9
Quad 1239 @ eghi2 elims from row.
g8=6==f8=6--f1=6==f1=8--d3=8==d3=1 elims 1 from g3
b3=9, e3=2
Pair 13 @ hi2 elims from row and box. g2=2
Quad 1358 @ h2456 gives h1=9, g6=9.
Pair 58 at g13 elims from the col, to give triplet 136 at g789 which elims from the box (h8)
i9=5, i7=8, h6=5, a8=3.
b5=6==b6=6--i6=6==i6=3--h4=3==h4=8 elims 8 from b4
h4=8==h5=8--b5=8==b5=6--b6=6==b6=3 elims 3 from i6
i6=6, i5=1, h5=8
d1=1==d3=1--a1=1==a1=5--c1=5==c1=6 elims 6 from df1.
From there it was UPs all the way. Hope I haven't made too many typos here.
I think your blogs are structured admirably - you show all the possible techniques and the underlying logic, but have also made it clear that there are various approaches to each puzzle which I think emphasises the flexibility needed for solving - as you say practice and experience will undoubtedly give the solver a feel for the puzzle, and what to choose where. (well I hope so)
One thing I did notice in the archives was that there was a very thriving interchange of ideas about the day's puzzle with people comparing approaches and how they got certain values as well as posting proofs. These days there seems more chat about the ensuing photo! Cheers.
30/Mar/07 2:36 PM
giblet  From victoria
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 elimination with the red light button on just to see. Thought it could have been due to having a wrong possibility in, but I check these very carefully now (espy when I'm tired). If you arrive at a situation where the start and end of the chain happen to be in the same box - say the chain starts at f4 which a value of 346, and you start with f4=3, go off out of the box and end up back in with d5=6, and the whole rest of the box has a mass of sixes do you eliminate all those other 6s? Cheers.
30/Mar/07 2:58 PM
Steve  From Ohio    Supporting Member
Check out my page
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 eliminations. This is proven by theorem.
If you can give a specific example of one that you thought had done so, I would not mind helping to find the flaw - which - as you indicate - is either in the possibility matrix, or in the chain construction.
30/Mar/07 4:47 PM
Steve  From Ohio    Supporting Member
Check out my page
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, though......
g8=5==e8=5--e5=5==e5=7--f5=7==f5=3 eliminates 3 from f8
This chain starts with g8=5, ends with f5=3, and thus does not quite eliminate 3 from f8. However, perhaps you have only not written one set of links in the chain:
f8=6 == g8=6 -- g8=5==e8=5--e5=5==e5=7--f5=7==f5=3
does eliminate that 3.

The next chain, if one adjusts it so that it ends and starts with a strong link:
g8=5==e8=5--e5=5==e5=7--f5=7==f5=3--d5=3==d5=5--d9=5 == e8=5
Merely says g8=5 == e8=5, which we already knew. Nothing regarding the 5s can be eliminated by this chain.

If you are an archive reader, last year in February and March, I often posted proofs that, well, needed some polish. Do not be disheartened, proof writing takes some practice!
30/Mar/07 5:02 PM
giblet  From victoria
Steve, Thanks for looking at the chains and your comments -they definitely need a bit more work! Cheers.
30/Mar/07 8:09 PM
David PB  From UK
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 have to be repeated

For Giblet: Sometimes an alternative form of wording can help!
If you keep strictly to alternating strong and weak inferences then the resulting inference depends on the two end links:
Two strong (7)a6 = [….] = (4)b4 the two end conditions cannot both be false (they could both be true)
Two weak (7)a3 - […] - (4)b2 the two end conditions cannot both be true (they could both be false)
Mixed (7)a6 = […] - (4)b2 the two end conditions are true or false together (they are equivalent)
The first of these usually provides the exclusions but the others can be useful particularly while you are tracking a new chain.
If you can complete a loop, the chain can be broken at any weak inference to find exclusions all the way round it!
30/Mar/07 8:34 PM
Steve  From Ohio    Supporting Member
Check out my page
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.

Join Now Login