How to Solve Diabolical Sudoku Puzzles - Part 2

The following is page two of an illustrated proof for the Tough Sudoku of February 20, 2007.

This is page two of a multi-page proof for this puzzle. The pages will come out gradually over the next few hours, as they are created. The general theme of each page will be slightly different, as the puzzle progresses through various degrees of technique difficulty.

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. Some of the Chains that are presented are complex forbidding chains - or advanced forbidding chains. Such chains merely use arguments that are Boolean variables (something that is either TRUE, or False). Some of these Booleans represent native puzzle conditions that are neither bivalue in a cell, nor candidates that are bilocation.

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

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. Some steps that are not required will be illustrated. The purpose of illustrating such steps is primarily to clue the potential solver on how to decide upon a plan of attack for truly diabolical puzzles.

Most of the eliminations justified on this page are superflous to the actual proof. Nevertheless, they form a foundation for understanding how and why this puzzle requires the steps taken on the following page(s).

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 lines = strong links
  • red lines = weak links
  • black circles connected with black lines = multi-part strong sets
  • candidates crossed out in red = candidates proven false

Puzzle Markings

Once one has exhausted the normal easy techniques:

  1. Unique Possibilities
  2. Locked Candidates
  3. N tuples (Hidden and Naked pairs, triples, quads...)
  4. Coloring (Forbidding Chains on just one candidate)
  5. Unique Rectangles (rarely helpful, and a bit controversial - as one cannot prove a unique solution once one assumes a Unique solution
If the puzzle is not solved, it is usually a good time to either:
  1. Guess
  2. Print out the puzzle and mark it up
The markings that I use are detailed at some length in the blog page Forbidding Chains 102 The Practice . For truly tough puzzles I enhance the markings a bit.
  1. If a candidate is limited to exactly two locations in a house, it is circled
  2. If a candidate, but for one location in a house, would exist only within a row or column of another house, it is underlined.
  3. If such a candidate being locked into that other house forces another cell to precisely one value, a pointing V is placed next to that candidate
  4. Candidate groups that are very strong are noted, usually mentally
  5. Possible remote naked pairs are circled (I use red for these)
  6. Possbile remote hidden pairs are circled (I use red for these also
Hopefully, through the following illustration of my puzzle mark-up for this puzzle, these markings will be clear.

Once the puzzle mark-up is finished, the hierarchy of attack generally proceeds as follows

  1. Y wing style eliminations, as they are generally obvious by inspection.
  2. Cells with multiple circles that are not part of Naked sets, unless they are circled for more reasons than just the result of being part of that naked set
  3. Cells circled red
  4. Cells with one or more circles that interact with Almost Locked Sets (this includes cells that are bivalue)
  5. Candidates that are part of a very strong group
  6. Tri-value by location candidate locations
  7. Almost Almost Locked Sets
  8. etc
I have never had to execute etc. Most puzzles quickly unlock considering only cells that are bivalue and sets that are bilocation.

This puzzle is not one that unlocks, in my humble opinion, without using some trilocation or trivalue analysis. Such analysis is often called Nets. It is also analagous to 3 D Medusa Chains. Many would consider any puzzle requiring such analysis as being too difficult, or even a bad puzzle, or as requiring guessing. I am not of that opinion. I do not consider the analysis that I will present even a faint shade of guessing. Moreover, each step except perhaps one, is clearly the logical result of just using the obvious information the puzzle presents.

Actual Puzzle Mark-up

PUzzle start

As I produced the puzzle mark up above, I noted the following:

  • There is some potential for an AUR with 5's at c5, d56.
  • All the sixes on the grid are circled - thus a very strong candidate group.
  • All but one of the sevens are circled
  • All but one of the eights are circled
  • All but one of the nines are circled
Usually, this many very strong candidate groups bodes well for some easy eliminations. However, this particular puzzle is configured so that the strong candidate groups interact rarely.

After making the puzzle markings, I noted the following:

  • Executing any AUR's with the 5s will likely not result in unlocking the puzzle
  • cell b6 and cell i1 are potential remote hidden pair-like
  • i7 = f4 = 19 are potential remote pair-like
  • Box h8 has three bivalue cells: i7, g8, g9
  • Box h8 has strong nines coming out of the box (towards i1) and strong sixes coming out of the box (direction is not important, as any one six solution solves all sixes
  • Column b has: An almost hidden pair 69 at b12, An almost locked naked set 123 at b37
  • Candidate 1 is not very strong, but it exists in many bivalue cells
I now can craft a plan of attack...

Y wing style

Easy Y wing style

Illustrated above is a typical Y wing style elimination that uses cell g8=29 as the vertex. As a forbidding chain, or AIC:

  • b7=2 == h7=2 -- g8=2 == g8=9 -- i7=9 == i7=1 => b7≠1
Another way to understand this elimination:
  • g8=2 => h7≠2 => b7=2
  • g8=9 => i7≠9 => i7=1
  • Therefor, b7≠1
This is an easy one, but sadly it does not advance the puzzle significantly.

One can, however, continue to use box h8 as a center for further investigation.

Forbidding Chain using 5 native strong sets and remote interaction between 6,9

69 remote interaction in box h8

Illustrated above is the following forbidding chain:

  • h8=6 == d8=6 -- d1=6 == b1=6 -- b1=9 == i1=9 -- i7=9 == i7=1 -- g9=1 == g9=5
  • => h8≠15
The two endpoints of the chain prove: h8=6 == g9=5 => h8≠5.

However, if one merely lops the last link off of the chain, one also has: h8=6 == i7=1 => h8≠1

Please remember that strong and weak need not be mutually exclusive properties, regardless of the opinions of other sites. Thus, the vertical red lines in columns d & i are not typos, but rather a reflection of the fact that this chain uses the forbidding nature of the sixes in column d and the nines in column i, not the affirming nature implied by strength.

Locked 5s

Locked 5s

An easy one here: 5s in box h8 are limited to row 9, thus b8≠5

Other approaches

At this point, if one wants to just solve the puzzle quickly, without regard to analysis depth, then a simultaneous and very deep analysis of the 19s at f4, i7 and 79s at i1, b6 will lead to a very deep, but very fruitful forcing net.

I submitted this puzzle at this point to the sudoku solver at Andrew Stuart's Scanraid site. The solver used Bowman's bingo repeatedly to unlock the puzzle. Bowman's bingo is really nothing more that a forcing net applied randomly until something gives. Such a trial and error approach is not what I intend to demonstrate.

The next step does not require anything approaching guessing to understand, nor to find.

Almost Locked Sets in a Chain

Almost Locked set with AIC

There are many ways to justify b8≠23. Illustrated to the left is:

  • b8=5 == c8=5 -- c8=1 == c12=1 -- b3=1 =={Pair 23 at b37}
  • => b8≠23
Also, one can use, not illustrated:
  • {pair 23 at b7a8} == a8=4 -- a9=4 == a9=7 -- b9=7 == b9=1 -- b3=1 == {pair 23 at b37}
  • => b8≠23
The way I first saw this elimination was:
  • {Hidden pair 15 at bc8} == b9=1 -- b3=1 =={pair 23 at b37}
  • => b8≠23
In my opinion, the latter version is easiest to see, and is immediately brought to fore after the previous step had eliminated b9=5.

It is expected that when a column, such as column b, has an almost hidden pair (69 at b12), that there will be Almost Locked set eliminations possible somewhere. This is especially the case as we also have in column b5 an almost locked hidden 79 at b6h4. Much experience at finding forbidding chains quickly clues one into such occurrences.

The elimination above can also be viewed as an Aligned Pair Exclusion or APE. All APEs are also Almost Locked Set (ALS) type exclusions.

If you have trouble with any elimination shown by any forbidding chain at any time, try a proof by contradiction to fully understand the workings of the chain. There will always be a contradiction that one can prove in every strong set and every weak set in the chain, dependent only upon which way one travels along the chain. For example, suppose:

  • b8=23
    • Since b7=23, => b3≠23 => b3=1
    • b3=1 => c12≠1 => c8=1 => c8≠5 =>
    • Box b8 has no fives (contradicting b8=5 == c8=5)
  • Let us go the other direction: b8=23
    • =>b8≠5 => c8=5 => c8≠1 =>
    • c12 contains 1 => b3≠1 => b3=23 =>
    • b378 are all limited to only 23 => impossible => contradicting the naked ALS b7=23
One can try it from both directions at the same time, and one will find that either a weak set is violated by having two or more of something in a house, or a strong set is violated by having nothing of something in a house (this includes cells that are empty or proven to be at least two candidates).

New Possibility Matrix

Locked 5s

The puzzle is still resistant to further cell solutions. Nevertheless, some progress has been made towards understanding what will unlock this puzzle. One can do another puzzle mark-up at this point, or alternatively just enhance the previous one. I generally just enhance the previous one with the new information until some significant cell solving occurs. Note above that the 1s have become stronger, and that they occur frequently in remote pair like configurations. Specifically:

  • i7 = f4 = 19
  • i5 = b9 = 17
  • b8 = g9 = 15
Nevertheless, my final proof will not actually require any of the steps taken on this page. However, there was no way for me to know that at the time that I found these steps. In fact, finding these steps was still valuable, as they paved the path for me to look for many of the steps that IMHO, are required to unlock this puzzle.

Please visit the next blog page on this puzzle to see the next steps!

Indicate which comments you would like to be able to see

todl qkpoufw nmcdtil emkzvc rolativ hdjpcofle ryjnflh
23/May/07 9:45 PM
eibptdyaw bngpv xdmitz ndxkear kjelsgvxa vaowfmy kvpabfqlg
23/May/07 9: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