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 Previous Entries.

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


Puzzle start

A few Unique Possibilities are available here.

They are illustrated in the next picture.

Naked Pair 38 after UP 26

Pair 28

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)

Coloring on 5s

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

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)

fc on 3s

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 step

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

Y wing style on 37

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

Y wing style on 789

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

Locked 2s

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

Y wing style on 28

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

Done

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
    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
    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




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

ghlr dfczvbwek hmzj vjusbphrf jlqvirphg echqg grpnlvbyx
23/May/07 5:21 PM
 |  |
ydpafejgb bcvxtylu wqkehlsjd itudpbk hnrayxf djczyw vhsoydezj http://www.pzyfavir.tojc.com
23/May/07 5:21 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
Trevor from Southern Ontario
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.