Steps to Solve Tough Sudoku of 26-Jan-2007 with Proof
The following is an illustrated proof for the
Tough Sudoku of 01/26/07.
Since this proof uses forbidding chains, you may need to refer to previous blog pages to
understand this proof. Links to these pages, including Forbidding Chains 101, The
Theory, and Forbidding Chains 102, The Practice, are found to the right, under
Sudoku Techniques.
Puzzle at start
A few Unique Possibilities:
- g3 = 2% box
- f5 = 2% box & row
- d5 = 6% box & row
Unique Possibilities get the puzzle to 26 cells solved. (UP 26)
Puzzle at UP 26
Hidden pairs are often easier to find before entering possibilities onto the puzzle grid. Here,
the highlit 4's and 6's in columns g and h reveal:
Thus i12 can contain only 46. This gives us a few more
Unique Possibilities:
- h3 = 3% box
- a2 = 3% box & row
- i5 = 3% row
- a1 = 7% box
Unique Possibilities have now advanced the puzzle to 30 cells solved. (UP 30)
Puzzle at UP 30
Once again a hidden pair can be located without entering the possibilities.
This does not immediately solve any cells. There are a few locked candidate eliminations, but
they also do not solve any cells. It probably is a good time to consider the possibility matrix.
Possibility matrix at 30 cells solved
Here one can find the following:
- Locked 1's at f12 forbids f46=1
- Locked 4's at de4 forbids a4=4
- Locked 6's at ef7 forbids b7=6
- Locked 9's at a46 forbids a389=9
- Triple 579 at d789 forbids:
- d46,f7 = 5
- d46,ef7 = 7
- d3,f7 = 9
Also, AUR 46 at bi12 forces b1=9 == b2=9 forbidding 9 from c3. This solves only one cell, so
I am ignoring it, as I really prefer to avoid AUR's when possible.
Now, a program such as Simple Sudoku is stuck. I look for easy coloring eliminations next.
Since I fail to locate any, I print out the puzzle and mark it up.
Refer to the page,
Forbidding Chains 102 The Practice for an in depth explanation of
my puzzle markings at this stage.
Puzzle markings at 30 cells filled
I typically add some V's to my markup if I see some candidates that I forsee as
being possibly interesting relative to the puzzle grid. These markings have a direction to them.
The cell c3 has 3 endpoints of bivalue sets strong by location within it. This makes that
cell the first place that I look. Here I find a short chain
Y wing style chain at 30 cells filled
Key:
- Black boxes, circles = strong set endpoints
- Blue lines = strong links
- Red lines = weak links
- Green marks candidate eliminations
This Y wing style forbidding chain uses only strength in location. Also, it uses groupings
of candidates within a container. This occurs twice:
- 5's in box b5
- 4's in column b
The forbidding chain representation of this step is
- c3=5 == a3=5 -- a456=5 == b5=5 -- b5=4 == b12=4 forbids c3=4
We know that since we have eliminated a
strong 4, that there must be at least one
Unique Possibility. In fact, there are many:
- c8 = 4% row, c7 = 3% box, f7 = 6% cell, e7 = 2% cell, e8 = 3% cell, f6 = 3% column
- f3 = 9% cell, f1 = 1% cell, f2 = 7% cell, f4 = 5% cell, c3 = 5% cell, c9 = 9% cell
- g2 = 1% row, b2 = 9% row
We have thus arrived by Unique Possibilities to 44 cells solved (UP 44).
Puzzle at UP 44
Here there are a few easy eliminations:
- Hidden pair 59 at ai6 forbids a6=8, i6=18
- Locked 8's at de6 forbids de4=8
One could do another puzzle mark up here, but when this many cells have been solved, the
puzzle will have many, many marks. Generally, at this point, I look first for things I noted
at the original puzzle mark-up. If this fails, I usually try to look for interesting new
relationships.
Using new strength at previous points of interest, I find a depth 4 chain.
Depth 4 chain at 44 cells filled
Key:
- Black boxes = endpoints of strong links
- Purplish blue lines = strong links
- Red lines = weak links
- Green circle = elimination target
This chain uses only strength in location. There are probably many forbidding chains available
here. It is likely that some other advanced techniques could also be fruitful. Eventually, I
will get around to treating those specifically. Know for now that if you understand
Advanced Forbidding Chains, most of those advanced techniques can be derived.
The forbidding chain:
- d8=9 == d7=9 -- d7=7 == d9=7 -- h9=7 == h5=7 -- h5=1 == h8=1 forbids h8=9
Happily, this completely unlocks the puzzle. Unique Possibilities will take this puzzle from
here to the end. (UP 81).
Solved Puzzle
Proof
A proof for tough sudoku of 01 26 2007:
- Start at 23 filled - the given puzzle. Unique Possibilities to 26 filled. (UP 26).
- Hidden pair 46 at i12 forbids i2=139, i1= 189 UP 30
- Hidden pair 17 at c56 forbids c5=45, c6=59
- Y wing style c3=5 == a3=5 -- a456=5 == b5=5 -- b5=4 == b12=4 forbids c3=4
UP 44
- d8=9 == d7=9 -- d7=7 == g7=7 -- h9=7 == h5=7 -- h5=1 == h8=1 forbids h8=9 UP 81
- Sets: 2 + 2 + 3 + 4 = 11
- Max depth 4 at step 4
- Rating: 2(.03) + .07 + .15 = .28
The proof above has been pared down to steps required to prove the puzzle solution.