Steps to Solve Tough Sudoku of 24-Jan-2007 with Proof
The following is an illustrated proof for the
Tough Sudoku of 01/24/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, are found to the right, under Sudoku Techniques.
Puzzle at start
A few Unique Possibilities:
- i4 = 3% box & column
- b5 = 3% row
- a9 = 3% row, box & column
- i8 = 5% column
Now at UP 26, (or at the start),
note also Hidden pair 17 at e2f3. Thus e2f3 are limited to only 17.
Possibility Matrix at 26 filled
In column i, both 1s and 4s are locked in box h2. Forbids:
3 strong sets with the 7's:
- a67 = 7
- h72 = 7
- gf3 = 7
Beg this forbidding chain on 7's:
- a6 == a7 -- h7 == h2 -- g3 == f3 forbids f6=7
Yielding this new possibility matrix:
Possibility Matrix again at 26 filled
Most normal techniques fail to advance this puzzle further. In order to properly
analyze this puzzle at this point, I print it out and mark it up. Often times, the act of
marking the puzzle makes a few forbidding chains obvious.
Puzzle Mark-up at 26 cells solved
Refer to the page,
Forbidding Chains 102 The Practice for an in depth explanation of
my puzzle markings at this stage. I have added the black V at g8 because of the 26 at a8 and
69 at b9.
Of special interest are the endpoints of strong links in the following cells: a6, c7, c9.
Two of these three beg the following:
Depth 4 Forbidding Chain
Key:
- Black circles = endpoints of strong links
- Black lines = strong links
- Red lines = weak links
- Green circles = elimination targets
This forbidding chain is an excellent example of mixing the use of strength in location and
strength in cells. It can be written as follows:
- c9=8 == c7=8 -- c7=1 == f7=1 -- f3=1 == f3=7 -- g3=7 == g9=7
- forbids c9=7 and
- forbids g9=8
One can now solve the following cells:
- g9 = 7% row
- h2 = 7% box & column
- f3 = 7% box & row
- e2 = 1% cell
- i3 = 1% box, row, & column
- i2 = 4% cell
Yielding Unique Possibilities to 32 cells filled (UP 32).
New Possibility Matrix at UP 32
Here we have the following Locked candidate eliminations:
- Locked 4's at ab3
- Locked 6's at ac2
There are a few forbidding chains on 8's possible. One that gets all the eliminations in one
step is commonly called a
finned X wing. Note these strong sets:
- d3, g3 = 8
- g8, ef8 = 8
Thus the following forbidding chain on 8's:
- d3 == g3 -- g8 == ef8 forbids d79=8
Once again, most normal techniques fail to advance this puzzle further. One could
do another puzzle mark-up, but not that many changes have occurred. I often just use my old
mark-up at this point. Happily, the possibly pivotal 6 at g8 yields some eliminations.
Key as as before.
The following strong sets are considered:
- g8, ab8 = 6
- b9 = 6, 9
- b3, g3 = 9
The strong link:
is a common trick.
b9 = 69 is the vertex of the Y.
Forbidding chain representation of this step:
- g8=6 == ab8=6 -- b9=6 == b9=9 -- b3=9 == g3=9 forbids g8=9
After this step, we have the additional eliminations:
- Locked 9's at hi7 forbids cd7=9
Y wing style eliminations #2
This elimination type I find to be very common. The 6's at g8h7 form the vertex of
this Y. Here is this step as a forbidding chain:
- a8=2 == a8=6 -- g8=6 == h7=6 -- d7=6 == d6=2
Y wing style elimination #3
Here, f8=18 is the vertex. Notice again that a candidate is grouped within a strong set.
In this case, the 8's in box h8 are grouped according to rows. Here is this step as a
forbidding chain:
- c7=1 == f7=1 -- f8=1 == f8=8 -- g8=8 == hi7=8
Now we can solve some more cells again:
- c9 = 8% box & column
- c1 = 9% column
- i1 = 8% cell
- i7 = 9% cell
- d3 = 8% row & box
- g3 = 9% row & box
Possibility Matrix at UP 38
From this point, the puzzle solves quickly. One way to finish:
Then:
- d2 = 2% row
- d7 = 6% cell
- % cells to the end
Solved Sudoku
Proof
Here is the proof, pared down to required steps and presented in my usual style:
- Start at 22 filled - the given puzzle. Unique Possibilities to 26 filled. (UP 26).
- Hidden pair 17 at e2f3 forbids e2=245, f3=248
- c9=8 == c7=8 -- c7=1 == f7=1 -- f3=1 == f3=7 -- g3=7 == g9=7
forbids g9=8,c9=7 UP 32
- fc on 8's:d3 == g3 -- g8 == ef8 forbids d79=8
- g8=6 == ab8=6 -- b9=6 == b9=9 -- b3=9 == g3=9 forbids g8=9
- Locked 9's at hi7 forbids cd7=9
- a8=2 == a8=6 -- g8=6 == i7=6 -- d7=6 == d7=2 forbids ac7,ef8=2
- c7=1 == f7=1 -- f8=1 == f8=8 -- g8=8 == hi7=8 forbids c7=8 UP 38
- Locked 2's at ab3 forbids ac2=2 UP 81
- Sets: 2 + 4 + 2 + 3 + 1 + 3 + 3 + 1 = 19
- Max depth 4 at step 2.2
- Rating: 2(.01) + 2(.03) + 3(.07) + .15 = .37
Like most puzzles, there are many ways to tackle this one. Below find two alternate approaches.
Alternate Proof 1
Step 3.2 of this proof uses a forbidding chain element explained in
Advanced Forbidding Chains.
- Start at 22 filled - the given puzzle. Unique Possibilities to 26 filled. (UP 26).
- Hidden pair 17 at e2f3 forbids e2=245, f3=248
- c9=8 == c7=8 -- c7=1 == f7=1 -- f3=1 == f3=7 -- g3=7 == g9=7
forbids g9=8,c9=7 UP 32
- Locked 6's at ac2 forbids c1=6
- b9=9 == b9=6 -- a78=6 == a2=6 -- c2=6 =={pair 25 at c25} -- c1=25 == c1=9
forbids b3,c79=9 UP37
- Locked 2's at ab3 forbids ac2=2 UP 81
- Sets: 2 + 4 + 1 + 5 + 1 = 13
- Max depth 5 at step 3.2
- Rating: 2(.01) + .03 + .15 + .31 = .51
Alternate Proof 2
Step 3.2 of this proof also uses a forbidding chain as a Boolean variable
- Start at 22 filled - the given puzzle. Unique Possibilities to 26 filled. (UP 26).
- Hidden pair 17 at e2f3 forbids e2=245, f3=248
- c9=8 == c7=8 -- c7=1 == f7=1 -- f3=1 == f3=7 -- g3=7 == g9=7
forbids g9=8,c9=7 UP 32
- c5=2 == c5=5 -- a6=5 == a2=5 -- d2=5 == d2=2 forbids c2=2
- Very common Y wing style above
- {pair 24 at ab3} == b3=9 -- b9=9 == b9=6 -- a8=6 == a8=2 forbids a2=2 UP 33
- Triple 689 at dhi7 (dh7=689,i7=89) forbids ac7=6, af7=8, c7=9 UP 81
- Sets: 2 + 4 + 3 + 4 + 3 = 16
- Max depth 4 at steps 2.2 and 3.2
- Rating: .03 + 2(.07) + 2(.15) = .47
Proof choices
For every tough sudoku puzzle, there are many manners to come to the solution, and therefor
many possible proofs. The choice as to which proof is better is a completely
arbitrary one. I prefer proofs of less maximum depth, but as is illustrated
above, adding a little bit of depth may reduce both the total strong sets considered
and the total steps used in a proof. The ratings that I assign are my clumsy attempt at comparing
proof complexity.
The choice of rating system is also completely arbitrary. For this reason, I
like to provide the entire vector: Total sets, Maximum depth, rating. Of course, more factors
could be considered. I am always hoping for someone to suggest a better, yet not overly
complicated, way to evaluate puzzle proofs.