Many places with tips, tricks, techniques or help on how to solve sudoku
puzzles that tackle forbidding chains fail to contemplate the next logical step.
By example, we are going to do just that.
A few chains are here in front of me,
Rusty, old, mangled and tangled,
How to use them I cannot quite see,
Let us try something newfangled.
The following is a complete proof of the
Tough puzzle of January 19, 2007.
There are other ways to approach this very tough puzzle, but the following is the least deep
that I could find. If this is your first visit to this blog, you may need to study previous
blog pages first. Links to these pages are to the right under Sudoku Techniques
It is assumed that you understand the terms used here (see Definitions> and
that you understand the general idea of forbidding chains (see Forbidding Chains
101 The Theory).
Starting Point
Eliminations available at start
Note the following:
- 5's in box e5 locked at ef4
- 38 in box e5 locked at de6
- forbids (not 38) at de6
- forbids hi6=8
- 38 in column d limited to d68
Hopefully the highlit cells help
Given the above eliminations, one should find the following Unique Possibilities:
- a2 = 8% column & box
- f7 = 4% row
- c3 = 3% row
- b5 = 3% row
- e8 = 1% box & row
Possibility Matrix at 28 filled after noted eliminations
If you are using a program such as Simple Sudoku, at this point the program is stuck. Recall
that before puzzle mark-up, I check for easy coloring eliminations. Focus on the possible
locations for candidate 9:
- 9's in row 7 are limited to ai7
- 9's in row 5 are limited to ahi5, thus
- fc on 9's: i7 == a7 -- a5 == hi5
Note that cells hi5 and cell i7 both
see cells i46. Of these, only i6 contains a
potential 9 for elimination.
This elimination reveals:
- i2 = 246
- i3 = 24
- i6 = 46, thus
- Triple 246 at i236 forbids
- i5 = 6
- i7 = 2
- i8 = 26
- gh12 = 2 because within the triple, 2's are locked at i23
Now we also have:
- a7 = 59
- i7 = 59, thus
- Pair 59 at ai7 forbids
New Possibility Matrix at 28 filled
At this point, I can find no more easy eliminations, so I print out the puzzle and mark it
as noted in the previous blog, Forbidding Chains 102 The Practice.
Puzzle Mark up at 28 filled
Typically, while marking up the puzzle I will make some notes as to points of interest in
the puzzle. With the marks above, I noted that the 2 at e1 sees two very strong cells
and is the endpoint of multiple strong links, so it probably will be part of a chain. I also
noted that the 1 at b1 looks like an easy target for elimination, as it is seen by two strong
cells and the endpoint of a strong link. The 7 at d3 is similar, but as it turns out is more
problematic. The cell e3 seems very likely as part of some chains to me. This conclusion is
deduced from a short study of the mark-up.
Here I find some short Y wing style chains that make some eliminations:
- b1=2 == e1=2 -- e3=2 == e3=7 -- a3=7 == a3=1 forbids b1=1
- d2=4 == d3=4 -- i3=4 == i3=2 -- e3=2 == e3=7 forbids d2=7
These two eliminations are easy, but they do not seem to significantly advance the puzzle.
There are some other easy chains - a bit deeper - for example:
(They need d2≠7)
- i6=6 == i6=4 -- i3=4 == d3=4 -- d3=7 == d4=7 -- g4=7 == g5=7 forbids g5=6
- g5=7 == g4=7 -- d4=7 == d3=7 -- d3=4 == i3=4 -- i6=4 == i6=6 -- h5=6 ==
{hi5=pair 89} forbids g5=68
This last one does solve the cell g5, but still the puzzle is resistant. Moreover, it requires
a chain type not fully covered yet in the blog. Since this puzzle seems to need this type
of chain....
More Forbidding Chain Theory
Recall a standard form of the forbidding chain is:
- A == B -- C == D (A,B,C,D are Boolean variables)
Suppose for a moment that B is actually a forbidding chain. For the larger chain to be valid,
B would have to be a Boolean variable that was either true or false and the following two
statements would have to be valid:
What this means in a puzzle is that an
almost strong set within B is either a strong
set by itself, or A is true. Also, that the forbidding chain B forbids C. In the last chain
listed above:
- g5=7 == g4=7 -- d4=7 == d3=7 -- d3=4 == i3=4 -- i6=4 == i6=6 -- h5=6 ==
{hi5=pair 89} forbids g5=8
the argument {hi5=pair 89} is:
- Actually a forbidding chain: h5=8 == h5=9 -- i5=9 == i5=8
- is true OR h5=6 since h5 is limited to 689
- Forbids g5=8 if it is true
Thus this argument works perfectly well as a Boolean variable within the chain.
Back to the puzzle
Given this new theoretical tool, there are dozens of forbidding chains
available. I cannot possibly list all of the ones that I find here becuase it would just
take too long. You may very well find a better, quicker way to solve this puzzle than the
one that I will illustrate. This new theoretical tool is one of many reasons that
I like to use forbidding chains instead of other solving technqiues. With this new tool, one
can use all techniques inside of forbidding chains.
This makes for one powerful tool!
Depth 7 chain that significantly unlocks the puzzle
key:
- Black lines = strong links
- Red lines = weak links
- Black circles = link endpoints
- Green circle = elimination target
Strong sets:
- a34=1
- bh6=1
- hi6,h4=4
- eg7=2
- ei3=2
- gh4=2
- di3=4
Forbidding chain representation of this step:
- a3=1 == a4=1 -- b6=1 == h6=1 -- h6=4 ==
{i6=4 == h4=4 -- h4=2 == g4=2 -- g7=2 == e7=2 -- e3=3 == i3=2}
-- i3=4 == d3=4
The key to this chain is noticing the strong 4's in box h5 conspire with the two's to constrict
the one's.
After making this elimination, we have the following:
- a3 = 1% row thus UP 29
- Hidden triple 124: bgh4=1, bh4=4, gh4=2 forbids
- g5 = 7% column and box thus UP 30
(presuming one has not yet done this)
- Triple 257: b1=25, b2=257, b9=257 forbids
New possibility Matrix at 30 filled
Note these strong sets:
Thus fc on 7's:
After this:
Thus b2 = 7% row. (UP 31.)
After solving this cell:
- Hidden pair 47 at c68 forbids c6=6 and forbids c8=256
- Locked 2's at bc9 forbids efh9=2
New puzzle at 31 cells filled
Key as before. Note these strong sets:
- be1 = 2
- b9 = 25
- ef9,f8 = 5
- f82 = 2
This yields the forbidding chain shown. Note it is a wrap around chain, thus
all the candidates circled green that lie on a weak link are forbidden, as
all the weak links are now proven strong.
Forbidding chain representation:
- e1=2 == b1=2 -- b9=2 == b9=5 -- ef9=5 == f8=5 -- f8=2 == f2=2
- forbids e23=2 and forbids c9=5
The puzzle now falls apart nicely as follows:
- e3=7%cell, d3=4%cell, i3=2%cell, f9=7%row, d4=7%row, c6=7%row, c8=4%cell, b8=9%cell
- a7=5, b9=2, c9=6, a8=7, b1=5, c2=2, c5=5, d1=1, d2=5, h9=8, e9=5, f8=2, e7=3 all %cell
- d8=8, d6=3, e6=8, g7=2, i7=9, i8=5, h1=6, g1=8, e1=2, i2=4, i5=8, i6=6, h5=9 all % cell
- g4=1, h6=4, h4=2, h8=3, h2=1, g2=3, g8=6, b6=1, f6=9, a5=6, a4=9, b4=4, e4=6 all % cell
- f4=5, f2=6, e2=9 all % cell
Completed puzzle
Proof presented in my usual style
A proof for tough sudoku of 01 19 2007:
- Start at 23 filled - the given puzzle. Unique Possibilities to 27 filled. (UP 27).
- Hidden pair 38 at de6 forbids hi6=8, d6=7, e6=679
- Hidden pair 38 at d68 forbids d8=157 UP 28
- Locked 5's at ac5 forbids ab4=5
- fc on 9's: i7 = a7 -- a5 == hi5 forbids i6=9
- triple 246,24,46 at i236 forbids i56=6 and forbids i78,gh12=2
- Pair 59 at ai7 forbids e7=5
- a3=1 == a4=1 -- b6=1 == h6=1 -- h6=4 =={i6=4 == h4=4 -- h4=2 == g4=2 -- g7=2 == e7=2 -- e3=2 == i3=2} -- i3=4 == d3=4 forbids d3=1 depth 7 UP29
- Hidden triple 124 at bgh4 forbids b4=79,g4=67, h4=69 UP 30
- Triple 257 at b129 forbids b6=7, b8=257
- fc on 7's: a8 == a4 -- c6 == f6 forbids f8=7
- Locked 7's at ef9 forbids bc9=7 UP 31
- Hidden pair 47 at c68 forbids c6=6, c8=256
- Locked 2's at bc9 forbids efh9=2
- e1=2 == b1=2 -- b9=2 == b9=5 -- ef9=5 == f8=5 -- f8=2 == f2=2 forbids e23=2, c9=5 UP 81
- Sets: 2+2+1+2+3+2+7+3+3+2+1+2+1+4 = 35
- max depth 7
- Rating: 3(.01)+6(.03)+3(.07)+.15+1.27 = 1.84 Truly tough!
