Interesting Proof for March 16, 2007

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:

• Locked Candidates
• Pairs, Triples, Quads.
• Forbidding Chains 101 The Theory
• Finding Coloring
• Finding Y wing styles
• A study in continuous nice loops
• Definitions: If a term is used on this page that you do not understand, the definition is likely here!

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

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:

1. a4=3 == c6=3 forbids nothing, as we already had that!
2. a1=3 == g1=3 => cd1≠3
3. g3=3 == g3=8 => g3≠29
4. i3=8 == i6=8 => i59≠8
5. 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:

1. a14=3
2. g13=3
3. gi3=8
4. i6=78
5. 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

1. Start at 23 filled - the given puzzle. Unique Possibilities to 26 filled. (UP 26).
2. Pair 38 at b89 forbids a8,c9,b246=3 and forbids a78b2=8 UP 33
3. fc on 5's: b4 == b2 -- f2 == f5 forbids ac5,e4=5 UP 35
4. Y wing:a7=56, a5=69, b4=95 forbids a4=5 UP 37
5. 1. fc on 3's: e6 == c6 -- c2 == def2 forbids e13=3
   2. 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
   3. e6=3 == c6=3 -- c6=7 == i6=7 -- i9=7 == e9=7 forbids e9=3
   4. de7=8 == g7=8 -- g7=9 == i9=9 -- i9=7 == e9=7 forbids e9=8 UP 50
6. 1. Locked 2's at g78 forbids g15=2
   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