Easy Proof of February 15, 2007


The following is an illustrated proof for the Tough Sudoku of February 15, 2007. This tough puzzle is well suited for the study of the limited techniques required:

  • Locked candidate
  • Hidden Pairs
  • Coloring
  • Y Wing Style
You may wish to refer to previous blog pages, although it probably is not required. Links to these pages are found to the right, under Previous Entries.

It is not the goal of this page to show every possible step.

By Coloring, I mean a forbidding chain on just one candidate. If one studies coloring, one can learn just about everything one really needs to know in order to perform forbidding chains on more than one type of candidate. Forbidding chains on just one type of candidate can get very complex. The examples today are very simple.

By Ywing style, I mean a forbidding chain that is logically analagous to a Ywing.

Some defintions

The following terms are employed in the explanations below:

%
is a singleton in
strong set
A set such that at least one of its members must be true
weak set
A set such that at most one if its members can be true
  • If A & B are members of a weak set:
    • A = true implies B = false
    • B = true implies A = false
native
Naturally occurring in the current puzzle possibility matrix without making any deductions
House
A cell, box, column, row
Unique Possibilites
A cell that is solved because it is uniquely defined in a house.
UP
Acronym for Unique Possibilities
=>
implies
Please note that a weak and strong need not be mutually exlusive properties. In other words, a set that is strong may also be weak. More precise definitions are available on the Definitions page of the blog.

Puzzle at start


PUzzle start

A few Unique Possibilities:

  • b3 = 3% box & row
  • b2 = 4% box
  • g3 = 4% box & row
  • i3 = 6% box and row
b3 = 3% box & row means b3=3 because it is the only possible place for 3 in box b2 and also in row 3. Of course, one need only find one of these two restrictions to place the 3.

Puzzle at UP 27


UP 27

After finding the intitial Unique Possibilities, but before entering the possibility matrix, it is often useful to look for Hidden Pairs. Also, it is useful to use Locked Candidates while filling in the possibility matrix.

Hidden Pair 69


Hidden Pair 69

Hidden pairs are easily found if one notices a symmetrical alignment of two candidates relative to a house. At the left, 6,9 at cells f1,f3 (f13 for short) and d79 limit both 6 & 9 to two cells in box e5. If something other than 69 were to go into those two cells, there would no longer be enough places for either 6 or 9 in box e5.

Locked Candidates with 1s


Locked 1s

Illustrated to the left, the 1 at c1 limits 1s in box h2 to ghi2. If e2=1, then there would be no places left for 1 in box e2. Thus, e2≠1. Since we already know e46 cannot contain 1, we now have e3 = 1% column.

Hidden Pair 23


Hidden Pair 23

A hidden pair 23 is revealed at h78 considering the 23's in column g and row 9 interacting with box h8. In this case, one can also now use the locked candidates property of both 2 & 3 at h78 to remove 3 from h45 and 2 from h12.

coloring on 7s

forbidding chain on 7s

Above, the possibility matrix is now considered. All the current possible locations for 7 are highlit green. The following key is used here and in the next few steps:

  • black circles = members of strong sets
  • blue lines = indicate in which house the strong sets reside
  • red lines = indicate a forbidding or weak link
    • endpoints of the red lines are members of a weak set, or weak subset
  • If two red lines point at a candidate, that candidate is eliminated.
The elimination above is also called a two string kite. The logic for the elimination can be expressed in many ways. Here is one way:
  • If c3=7, then c7≠7
  • If c3≠7 then considering the possible 7's in row 3, d3=7
  • If d3=7, then e2≠7
  • If e2≠7 then considering the possible 7's in column e, e7=7
  • If e7=7 then c7≠7
  • Conclude: Whether c3=7 or c3≠7: c7≠7
  • In every case where such an elimination is justified, if one supposes that the eliminated candidate is true, then a contradiction will exist somewhere within the strong and weak sets considered - using only those strong and weak sets. In fact, depending on where one starts, one can prove a contradiction in any weak and strong set considered. For example, suppose c7=7:
    • c7=7 => e7≠7 => e2=7 => d3≠7 => c3=7, but: 2 7's in column c.
    • c7=7 => c3≠7 => d3=7 => e2≠7 => e7=7, but: 2 7's in row 7
    • c7=7 => (c3≠7 and e7≠7) => (d3=7 and e2=7), but: 2 7's in box e2
    All of these relationships, and the elimination, are succintly contained in the forbidding chain:
    • fc on 7's: c3=7 == d3=7 -- e2=7 == e7=7 forbids c7=7
    Please refer to a previous blog page if you want to understand forbidding chains.

    coloring on 8s

    forbidding chain on 8s

    Illustrated above is another two string kite, this time considering candidate 8. One can start the illustrated idea from any circled point above, or from d8=8 (which will then be proven false). Again, the real clue to finding such an elimination are the strong sets considered:

    • c3=8 OR c4=8
    • b1=8 OR b8=8
    Written as a forbidding chain:
    • d3=8 == c3=8 -- b1=8 == b8=8 forbids d8=8
    Clearly, after d8≠8, f7 = 8 %box.

    Finding the Y wing style pattern

    Puzzle at UP 29

    Illustrated above is all the information that one must notice to find a Y wing style pattern. I call the pattern found above very common, as it is very common. One needs to recognize:

    1. e2=57 (cell e2 is limited to 5 OR 7)
    2. a7=57 (cell a7 is limited to 5 OR 7)
    3. ad1=5 (Fives in row 1 are limited to cells a1,d1)
    4. a1 shares a house with a7 (column a)
    5. d1 shares a house with e2 (box e2)

    Graphical illustration of the Y wing style


    Very Common Y wing Style

    Illustrated to the left is the justification for removing 7 from e7. Again, there are many ways to interpret the relationships graphed. Here is one way:

    • a1=5 => a7≠5 => a7=7 => e7≠7
    • a1≠5 => c2=5 => e2≠5 => e2=7 => e7≠7
    • clearly, e7≠7
    As a forbidding chain:
    • a7=7 == a7=5 -- a1=5 == c2=5 -- e2=5 == e2=7 forbids e7=7

    Although the first representation may at first seem more clear to you, the forbidding chain representation, in my opinion, is better as it completely details why, for example, a1≠5 => c2=5. The reason being: {a1=5, c2=5} are a strong set.

    After eliminating the 7 from e7, the puzzle is solved using only Unique Possibilities. Most of these are %cell, but there a a few hidden singles one must find - such as e2=7% column and a7=7% row.

    Solved Puzzle

    UP 81

    Proof

    The following proof uses some, but not all of the steps detailed above. It also uses a step not detailed. Instead, this proof represents the lowest rated solution that I found.

    1. Start at 23 filled - the given puzzle. Unique Possibilities to 27 filled. (UP 27).
      1. Locked 1's at de3 forbids e2=1
      2. fc on 8's: d3 == c3 -- b1 == b8 forbids d8=8 UP 29
    2. e2=7 == e2=5 -- c2=5 == a1=5 -- a7=5 == a7=7 forbids e7=7 UP 36
    3. Locked 5's at e78 forbids e26=5 UP 81
    • sets: 1 + 2 + 3 + 1 = 7
    • max step depth: 3 at step 3
    • Rating: .01 + .03 + .07 + .01 = .12

    ICY

    Some ice February 14, 2007

    Perfect weather for Valentine's Day!




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

    I never knew about the symmetrical alignment for locating hidden pairs. I usually find them the hard way with naked reductions around them. As usual, looks like you had an easier time than I did. I hit a wall then found a jellyfish for 8, then some coloring did some 'forbidding' for me. Towards the end a Unique Pair 27 at c45 gave me the 7 at d4 and the rest unravelled. Fun puzzle.
     |  |
    Thanks Steve, wonderfully explained. Like you suggest, the first representation at the Y Wing step is easier for me to understand, and I can pick up the logic easily. My difficulty in following your proofs on the main pages has always been understanding the fc strings. I have some more study to do here! Certainly the graphical bits help lots!
     |  |
    Steve, Could you add your definition of the strength value of a candidate to your definitions page please? This site is takes so long to trawl at my connection speed!
     |  |
    Hi David!
    Thanks for letting me know that. I do have those items on the definitions page.
    I know that the pages are getting too long.
    It seems, though, that oftentimes people do not refer to the previous pages, so I feel that I must over-explain things.
    Unfortunately, I did not see More...
     |  |
    Steve! back again. Don't worry too much about the length of you postings - it's much the same time to load a short page as a long one. It's mainly the the animated adds etc that causes the slow loads.
     |  |
    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
    Check out all the Daily Horoscopes
    Welcome our latest Members
    GRD from Sydney
    Laineyrb52 from MI
    tyrion from Milan
    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.
    Purely Facts Test your General Knowledge.
    Pumpkin Carving Pattern Free halloween pumpkin carving patterns.