Easy Proof of Tough Sudoku 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 Sudoku Techniques.

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

    Morgan  From NY
    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.
    Iain  From Sydney
    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!
    David PB  From UK
    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!
    Steve  From Ohio    Supporting Member
    Check out my page
    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 your comment until after posting the next blog page - which is even longer - and probably slower to load.
    I will, in the future, attempt to break such long pages into two parts, or alternatively insist more stringently that other pages be considered if required.
    David PB  From UK
    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.

    Join Now Login