Y Wing Style and Coloring Proof April 5, 2007

The following is an illustrated proof for the Tough Sudoku of April 5, 2007. The main techniques that I used to solve this puzzle are Y Wing Styles and Coloring. By Coloring, I mean any technique that uses exactly one candidate to justify an elimination.

You may wish to refer to previous blog pages to properly understand this proof. Links to these pages are found to the right, under Sudoku Techniques.

This page illustrates only the deduced elimination steps that I choose to solve the puzzle. Although many other steps are possible, they are not shown, as to show every possible step is prohibitive in both time and space!

The information on the following blog pages may be helpful:

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(s) (not used)
  • 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:

  • b3 = 2% box & row (hidden single in both box & row)
  • g4 = 3% box & column
  • c6 = 7% box & column
Although there are many steps available at this point, such as the naked pair 12 at e46, the following sequence of steps will render most of them superfluous.


Coloring with Candidate 3 (skyscraper)


Skysraper with 3s

Above, the locations of the possible 3s conspire to make a very simple coloring elimination. As a forbidding chain on 3s:

  • a2 == a9 -- e9 == e3 => c3,df2≠3
As a proof by contradiction:
  • Any of c3,df2=3 => a2 & e3≠3 => a9 = e9 = 3,(singletons in columns), thus too many 3s in row 9
These eliminations do not directly solve any cells, but they are a set up for a short sequence of steps.


Hidden Pair 13


Hidden Pair 13

Since both candidates 1 & 3 are limited to the same two locations, a2,c2, in a house(s), no other candidates can exist in those two cells. I have illustrated the elimination as a short continuous nice loop forbidding chain, or Alternating Inference Chain (AIC).

One could alternatively use the naked quad 5689 at abc1,c3 to make the same eliminations. Also, if one does use the naked quad, then one can also make the next eliminations at the same time.


Locked candidate 5


Locked 5s

Illustrated above, the 5s in box b2 are limited to two locations, ab1. Since both of these locations exist in row 1, 5 cannot exist in row 1 outside of box b2.

If one had used the naked quad instead of the hidden pair 13, one could have made the elimination of these two 5s at the same time, as the naked quad locks the 5s into the same cells.

After eliminating the 5s from ei1, a cascade of Unique Possibilities (hidden and naked singles) occurs until 53 cells are solved. The cascade begins with e3 = 5% box & column, which then allows one to solve all the 3s on the puzzle grid. The cascade continues until one gets to the next illustration.

Again, a handful of easy steps are possible below. However, either one of the next steps illustrated, or something equivalent to one of them, is all that is required to unlock the puzzle.


Y Wing Style using candidates 4 & 5


Y wing Style

The Y wing Style illustrated above uses the cell i6=45 as the vertex:

  • i6=4 => i1≠4 => h2=4 => h2≠5
  • i6=5 => g6≠5 => g2=5 => h2≠5
As a forbidding chain, the step can be written:
  • h2=4 == i1=4 -- i6=4 == i6=5 -- g6=5 == g2=5 => h2≠5
As a strong inference set list, the step is also detailed:
  • g26=5, i6=54, i1h2=4 => h2≠5
In a strong inference set list, each set listed must meet only this requirement:
  • At least one of the items in the set must be true
Since the forbidding, or weak, links are universal, there is usually no need to detail them.


Alternate to the previous step - Y Wing using candidates 568


Y wing

Illustrated above, a standard Y Wing (also a subset of Y Wing Styles), justifies the same elimination. The Y wing considers cell h3=68 as the vertex:

  • h3=6 => h9≠6 => h9=5 => h2≠5
  • h3=8 => g2≠8 => g2=5 => h2≠5
As a forbidding chain, one could write:
  • g2=5 == g2=8 -- h3=8 == h3=6 -- h9=6 == h9=5 => h2≠5
As a strong inference set list:
  • g2=58, h3=86, h9=65 => h2≠5

No matter how one finds it, once 5 is forbidden from h2, the puzzle is reduced to a cascade of Unique Possibilities until all cells are solved. (UP 81).


Proof

  1. Start at 23 filled - the given puzzle. Unique Possibilities to 26 filled. (UP 26)
    1. fc on 3s: a2 == a9 -- e9 == e3 forbids c3,df2=3
    2. Hidden pair 13 at ac2 forbids a2=589, c2=89
    3. Locked 5s at ab1 forbids ei1=5 UP 53
  2. Y wing style: g2=5 == g6=5 -- i6=5 == i6=4 -- i1=4 == h2=4 forbids h2=5 UP 81
  • Sets: 2 + 2 + 1 + 3 = 8
  • Max depth 3 at step 3
  • Rating: 2(.03) + .01 + .07 = .14 (perhaps a bit easy for the tough label)


Notes

This puzzle is an excellent puzzle for study for someone who wants to tackle the tougher puzzles. It is not too difficult, but it does at least require some advanced steps.

Hopefully, the illustration of the last step as either a Y Wing Style or a standard Y Wing is a sufficient demonstration of the fact that both steps are completely equivalent in complexity. The logic for each is precisely the same. Only the nature of the strong inferences is slightly different. Personally, I find the Y Wing Style using only two candidates, 4 & 5, to be slightly easier than the standard Y wing using 3 candidates. No matter which one finds easier though, it is useful to have both in one's bag of tricks.

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

Norb  From Carlsbad, CA
Steve,

I'm still struggling but: Doesn't the locked pair 4,6 at bc7 eliminate the 6 at h7 and thus the link from h9 to h3 is strong?
08/Apr/07 8:22 AM
Steve  From Ohio    Supporting Member
Check out my page
Hi Norb!
Indeed, one can make that elimination, and then the link would be strong. I am not sure why, at many sudoku sites, the word strong has come to mean 'exactly two'. Nevertheless, the inference one can use, in that situation, is both or either of the strong inference, or the weak inference. In this case, the chain uses the weak inference - the forbidding link.
For this reason, almost every one of my web pages declares that for my usage of the terms, that strong and weak need not me mutually exclusive properties.

This is especially convenient, as the endpoints of a chain prove that at least one of two items are true. In does not typically, though, mean that exactly one of the two endpoints are true. Thus, to my way of thinking, the convention of describing strong and weak at most sudoku sites creates much confusion.
For this reason, I have started to add the very cumbersome wording - strong inference set and weak inference set - as regardless of what one calls the darn sets, it must be clear that for the purposes of forbidding chains, or AIC:
The strong inference and the weak inference are independent properties. A set can have one, both, or neither. This is especially important with derived sets.
The confusion occurs becuase with Native sets, all strong sets are also weak.
Hopefully, this clears things up.

In any event, for this particular puzzle, if the elimination is valid before one eliminates that 6, it is clear that it must be valid after eliminating that 6! This also reveals the absolute disregard for mathematical precision in the common usage of the terms strong and weak!

Since I will never successfully buck the trend, and since many are convinced for some unknown reason that what they call strong only chains have special import, I am destined to continue to specify the word inference when describing sets.
08/Apr/07 8:32 PM
Norb  From Calrsbad, CA
Maybe I have to go back to basic definitions and theorems, but if 'strong' implies 'at least' one must be true, and if, in a given container, no more than one CAN be true, does that not define the set population as 'two'?
09/Apr/07 12:56 AM
Steve  From Ohio    Supporting Member
Check out my page
Hi Norb!

One can partition the set anyway one pleases. Thus, the number of items in the set, is not limited to two, but in fact can be any integer greater than one, including one.

So, for example, if I know that a1=1, it is still true that at least one of a1=1, and that no more than one of a1=1.

In any event, the weak inference still exists in a set containing exactly two members.

There is, as I said, very little value in thinking of strong as being exactly one is true. Especially since the conclusions one must make in a chain rely upon non-native sets, about which one often can prove at least one is true, and all may very well be true. (In other words, the endpoints of an AIC only prove mutual weakness in the special case of continuous loops).

09/Apr/07 2:18 AM
Norb  From CA
Steve,

Although I do understand your last statement about the unitary set, I'm afraid I still lack a solid understanding and competency in the AIC process. I'll review your basic stuff and try again.
Thanks for taking the time trying to educate me.

Norb
09/Apr/07 6:06 AM
Steve  From Ohio    Supporting Member
Check out my page
Hi Norb!
At first, the language of 'at most one' and 'at least one' had me confused. I found it much easier to think:
A == B means A OR B
noting OR is not exclusive or, but rather UNION.

A -- B means ~A OR ~B.

Perhaps thinking that way can help you too.

Dave has suggested also to think:

A -- B means A forbids B, and also B forbids A.

The word forbids is pretty good, but perhaps some will think it has some order to it....

Using OR, for me, clearly shows that everything is bidirectional.
09/Apr/07 5:52 PM
Norb  From CA
Steve,
(If you have the time)

Your definition A--B implies ~A or ~B helps a lot, but doesnt the weak link I tried in the following case satisfy that definition but not Dave's?

let a1=9, b1=68, c1=7,d1=4 e1=16,f1=3, g1=1268, h1=5 and i1=26. I had a link h3=8==g1=8 and would have liked to say g1=8--b1=6. The resultant b1=6==b1=8 awould have allowed me to eliminate two 8s from large cell b2 and as a result row 1 will contain (left to right) 9,8,7,4,16,3,126,5,26, satisfying your view g1=8--b1=6 implies ~(g1=8)+~(b1=6)but contradicting Dave's view?

(I actually didn't trust my logic , discarded that approach and solved the puzzle in a different manner.)
09/Apr/07 10:22 PM
Steve  From Ohio    Supporting Member
Check out my page
Hi Norb!
I cannot follow what you have posted. Perhaps let me know the puzzle state from which the logic comes. Also, it is almost certain that some typos have occurred.
10/Apr/07 6:55 PM
Norb  From CA
Steve, I appreciate your spending all this time with me. Let me reduce this to the basic question.

If the bottom row of the puzzle is configured as follows:

a1=9, b1=68, c1=7, d1= 4, e1=16, f1=3, g1=1268, h1=5 and i1=26
Is the weak link g1=8--b1=6 valid?

If I have still screwed this up, don't waste your time any further and thanks again.

Norb
11/Apr/07 3:14 AM
Norb  From CA
Steve,

Don't bother. I think the light has partially dawned, the answer is YES, and you have helped a lot! You were correct. My definitions of strong and weak were totally too restrictive. See my comment / question on the 1 Feb Proof if you have time.

Thanks again.

Norb
11/Apr/07 6:34 AM
Norb  From CA
Actually upon further analysis, the answer is NO, because if g1=8 then b1=6 and both are true, so the link is strong. So I guess I was correct in discarding that approach and solving it another way. However, the whole exercise has been beneficial in expanding my uunderstanding of AICs and I have since breezed through three or four toughs. (Which I could not do three days ago.)

Thanks again,

Norb
11/Apr/07 7:46 PM
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