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

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

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
 |  |
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 More...
08/Apr/07 8:32 PM
 |  |
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
 |  |
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 More...
09/Apr/07 2:18 AM
 |  |
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
 |  |
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 More...
09/Apr/07 5:52 PM
 |  |
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 More...
09/Apr/07 10:22 PM
 |  |
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
 |  |
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
 |  |
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
 |  |
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 More...
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.
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
Tatiana from Malacca
tannalo from Queensland
dgreen from canada
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.