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:
- Unique Possibilities
- Locked Candidates
- N tuples (Hidden and Naked pairs, triples, quads...)
- Coloring (Forbidding Chains on just one candidate)
- 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:
- Guess
- 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.
- If a candidate is limited to exactly two locations in a house, it is circled
- If a candidate, but for one location in a house, would exist only within a row
or column of another house, it is underlined.
- 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
- Candidate groups that are very strong are noted, usually mentally
- Possible remote naked pairs are circled (I use red for these)
- 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
- Y wing style eliminations, as they are generally obvious by inspection.
- 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
- Cells circled red
- Cells with one or more circles that interact with Almost Locked Sets (this includes
cells that are bivalue)
- Candidates that are part of a very strong group
- Tri-value by location candidate locations
- Almost Almost Locked Sets
- 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
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
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
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
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
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
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!