The following is an illustrated proof for the
Tough Sudoku of March 16, 2007.
This is an interesting puzzle.
There are many ways to tackle this one. The primary focus of this proof is to illustrate
using Forbidding Chains, also called Alternating Inference Chains or AIC.
You may need to refer to previous blog pages to 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. It is not the goal
of this page to show every possible step, but rather to illustrate steps that, taken together,
unlock this puzzle.
The information on the following blog pages is required to understand this page:
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
A few Unique Possibilities are available here.
They are illustrated in the next picture.
Naked Pair 38 after UP 26
Illustrated above is the naked pair 38, forbidding the indicated possibilities. After making
the eliminations, the puzzle advances to 33 cells solved using only Unique Possibilities
Coloring on 5s (Skyscraper)
Illustrated above is an easy Forbidding Chain using only candidate 5:
- b4 == b2 -- f2 == f5 => ac5,e4≠5
The colorful name
skyscraper is attached to this particular pattern. A proof by
contradiction, as always, is available. Suppose:
- Let any one of: ac5,e4=5 =>
- (b4 and f5)≠5 =>
- b2 = f2 = 5% column => contradiction
After making these elimination, two more cells solve: f5=5% row & box, then f6=6% column
Y wing
Illustrated above is a standard Y wing, presented as a forbidding chain:
- a7=5 == a7=6 -- a5=6 == a5=9 -- b4=9 == b4=5 => a4≠5
Here, clearly if a4=5, then b4=9 and a7=6, leaving a5 empty.
After a4≠5, b5=5% row and box, then b2=9% cell & column.
Coloring on 3s (Finned Xwing)
The forbidding chain on 3s illustrated above:
- e6 == c6 -- c2 == def2 => e13≠3
Again, if either of e13=3 => c2=c6=3% row, which is not allowed
Continuous Nice Loop (wrap around Forbidding Chain)
The forbidding chain illustrated above is strongly indicated by the standard puzzle marks
explained in some detail on previous blog pages, including
Forbidding Chains 102, The Practice
. I suppose one can write this chain in 10 different ways. Here is one:
a4=3 == a1=3 -- g1=3 == g3=3 -- g3=8 == i3=8 -- i6=8 == i6=7 -- c6=7 == c6=3
Since a4=3 is in conflict with c6=3, all the weak links in the chain are proven to
be strong sets. The proven strong sets are:
- a4=3 == c6=3 forbids nothing, as we already had that!
- a1=3 == g1=3 => cd1≠3
- g3=3 == g3=8 => g3≠29
- i3=8 == i6=8 => i59≠8
- i6=7 == c6=7 => h6≠7
If one wants to, a proof by contradiction can be made for each of the forbidden possibilities
considering only the strong sets used above:
- a14=3
- g13=3
- gi3=8
- i6=78
- c6=37
Although this step does not solve any cells, it facilitates the rest of the proof.
Y wing style
The last step opened up the Y wing style illustrated above:
- e6=3 == c6=3 -- c6=7 == i6=7 -- i9=7 == e9=7 => e9≠3
Again, one can convince oneself of the validity of the elimination with a proof by contradiction.
- Suppose e9=3 => c6=3% row and i9=7% row
- => There are no 7s in row 6, which violates the rules of the puzzle
Y wing style again
The Y wing style shown above is the hardest type to find. It has been available for quite some
time, though. As a forbidding chain:
- de7=8 == g7=8 -- g7=9 == i9=9 -- i9=7 == e9=7 => e9≠8
The compound argument of de7=8 is a typical trick, especially prevalent with
Y wing styles. One
can recognize the liklihood of such an argument being helpful by using the advanced puzzle marks
dicsussed in some of the diabolic proof pages in this blog.
Again, a proof by contradiction can be used to convince oneself that the elimination is valid:
- Suppose e9=8 => i9=7% row and g7=8% row
- => Box h8 has no 9s, which again violates the rules of the puzzle
Proofs by contradiction are a great tool for understanding a chain. Nevertheless, once one
understands the chains and how and why they can occur, proofs by contradiction become superflous.
Cascading Unique Possibilities now occur, beginning with b9=8% row. The puzzle does not quite
solve, though.
Locked 2s after UP 50
After exhausting the Unique Possibilities, some easy eliminations are available. Illustrated
above are Locked 2s at g78 (Locked in box h8) => g15≠2
Final Y wing style
The previous step allows one to now easily forbid i3=2, using:
- i5=2 == d5=2 -- d5=8 == e6=8 -- i6=8 == i3=8
Again, suppose:
- i3=2 => d5=2% row and i6=8% column
- => box 35 has no 8s!
After i3≠2, the puzzle is reduced to naked singles or % cells to the end.
Solved Puzzle
Proof
- Start at 23 filled - the given puzzle. Unique Possibilities to 26 filled. (UP 26).
- Pair 38 at b89 forbids a8,c9,b246=3 and forbids a78b2=8 UP 33
- fc on 5's: b4 == b2 -- f2 == f5 forbids ac5,e4=5 UP 35
- Y wing:a7=56, a5=69, b4=95 forbids a4=5 UP 37
- fc on 3's: e6 == c6 -- c2 == def2 forbids e13=3
- a1=3 == a4=3 -- c6=3 == c6=7 -- i6=7 == i6=8 -- i3=8 == g3=8 -- g3=3 == g1=3 forbids:
cd1=3, h6=7, i59=8,g3=29
- e6=3 == c6=3 -- c6=7 == i6=7 -- i9=7 == e9=7 forbids e9=3
- de7=8 == g7=8 -- g7=9 == i9=9 -- i9=7 == e9=7 forbids e9=8 UP 50
- Locked 2's at g78 forbids g15=2
- i5=2 == d5=2 -- d5=8 == d6=8 -- i6=8 ==i3=8 forbids i3=2 UP 81
- Sets: 1 + 3(2) + 4(3) + 5 = 24
- Max depth 4 at step 5.2
- Rating: .01 + 3(.03) + 4(.07) + .31 = .69