Forbidding Chains 102 The Practice - Sudoku Solving Technique

Many places with tips, tricks, techniques or help on how to solve sudoku puzzles completely forgo a complete discussion of forbidding chains. Probably, this is because finding the chains, that is the real trick.

Chains Required

To gain a bit more traction,

Open the trunk, target the chain.

Espy them with some passion,

As to idle same, quite a bane.





Tritely and often, language is avowed as less succinct than images. In deference to this adage, this page will amply employ the latter.

Complete Puzzle Proof

The following is a complete proof of the Tough puzzle of January 15, 2007.

Starting Point

Tough puzzle of Jan. 15, 2007 at start





Possible locations for 4

Tough puzzle of Jan. 15, 2007 looking at 4's

Because of the three original 4's, clearly ab3,c2,ab1 ≠ 4. Thus one could write:

  • b2 = 4%Box. Meaning: b2 = 4 because it is the only 4 possible in that box.
Some may choose to somehow optimize their search for UP's at the beginning. I basically just scroll through the candidates, unless I see something obvious.

Possible locations for 5

At 24 filled, looking at 5's

Above we have a good example of eliminations that can be made during set up. Note the strong 5's at c46 and g46. One could immediately eliminate 5 from b456 and h456. If one does that, now we also have strong 5's at df5. One can additionally eliminate 5 from e4,ef6. One could instead make all these eliminations in one step:

  • c4=5 == c6=5 -- g6=5 == g4=5 forbids b456,h456,e4,ef6=5
  • This is really just an X wing, and the eliminations are justified by
    • c4=5 == c6=5 forbids b456=5
    • g6=5 == g4=5 forbids h456=5
    • c4=5 == g4=5 forbids e4=5
    • since g4=5 -- c4=5, the additional wrap around chain result
      • c6=5 == g6=5 forbids ef6=5

Some more Unique Possibilities (UP)

To avoid the tedium of analyzing each indiviual candidate in this manner, I trust you can ascertain the validity of the following cell solutions:

  • a8 = 7 %Box
  • h8 = 8 %Row
  • h7 = 3 %Row and %Box - note we need the previous UP to get this one
  • g2 = 1 %Cell - again, need the previous UP

More eliminations at UP 28

At 28 filled, looking at 2's and 8's

Before filling in the possibility matrix, a few more eliminations are possible. Note above the following:

  • Locked 2's at g46 forbids i456=2
  • Locked 8's at ab1 forbids ef1=8

Possibility matrix at 28 filled

At 28 filled, possibility matrix

If you have not erred, and made the eliminations noted above, your current possibility matrix should look exactly like the one above. Here, none of the following techniques will yield any eliminations: subsets (naked or hidden), locked candidates, coloring, xwings, swordfish, Y wings. There is, however, at least one easy to spot forbidding chain.

How does one spot forbidding chains? The method that I use is progressive. I start looking where I believe chains are most likely to exist, and progress towards the least likely. Another factor in the search order is the efficient advancement of the puzzle.

Since forbidding chains use strong sets as their primary building block, it is logical to look at the native strong sets first. I begin by identifying the strongest of the native strong sets. Of these, there are two types:

  1. Cells limited to two candidates
  2. Candidates limited to two locations in a large container
Generally, I print out the puzzle and mark it up. Since if the puzzle is in an early stage, (less than about 35 cells solved), there usually are more of item 2, my focus for this puzzle will be primarily on sets strong by location. Here is a typical attack:
  • First, make sure I did not miss any coloring eliminations. Since coloring involves only one candidate at a time, it is easy to spot. Also, the Coloring search gives me a feel for the puzzle.
  • I print out the puzzle. It is time to find a pen (I despise pencils) .
  • All the candidates limited to two locations within a large container get circled
  • All the cells limited to two candidates get committed to memory - you may choose to mark them

Search plan, from most important to least

  1. All the cells with more than two circles in them
  2. All the cells such that
    • There are two circles
    • There are only two candidates
    • Are not part of a pair
      • Why not these? Most of their strength is spent
  3. All the cells such that
    • There are two circles
    • They see a two candidate cell
  4. All the remaining cells with two circles
  5. All the cells with two candidates
  6. All the one circle cells.
Each iteration above has an internal hierarchy:
  • Start with the candidate that is circled most often
  • Progress towards the candidate circled least often

First puzzle mark-up at 28 filled

At 28 filled, puzzle mark-up

With this puzzle, there are no cells with more than two circles in them, so the search defaults to item 2. The most promising start point then is cell f7 = 25, with two circles. Here, I quickly find a short chain.

Forbidding Chain Found

When I first started to dabble in forbidding chains, I would diagram them on the puzzle much like the image below. This helped me not only to visualize what was going on, but also to check the chain for validity.

Forbidding chain at 28 filled Key:

Black circles =
strong link endpoints
Black lines =
strong links
Red lines =
weak links
Green circles =
Eliminations
Notice: Here is one forbidding chain representation of this step:
  • f7=5 == f7=2 -- f1=2 == e1=2 -- e1=5 == e9=5 thus:
    • f7=2 == f1=2 forbids f56=2
    • e1=2 == e1=5 forbids e1=6
    • f7=5 == e9=5 forbids d9=5
After making these eliminations, we have still no more Unique Possibilities. So examine the new puzzle.

At 28 filled after wrap around chain

Triplet at 28 filled

The partial puzzle above has:

  • Naked triple 129 in the blue cells
  • Hidden triple 568 in the yellow cells
Each of these forbid exactly the same things:
  • abe9 = 1
  • e9 = 2
  • abe9 = 9
After performing these eliminations, there are some Unique Possibilities. Rather than illustrate all these, I will just list them:
  • e8 = 1% Box & Column
  • c6 = 1% Column
  • c4 = 5% Box & Column
  • g4 = 2% Cell
  • g6 = 5% Cell
This gives us 33 cells solved.

Puzzle at 33 filled

coloring on 6's at UP 33







Here, the search begins all over again. There are a couple of locked sets eliminations possible here, but... while looking for Unique Possibilities, I noticed an easy chain with candidate 6.






  • 6's in column c are limited to c2,c8
  • 6's in box e8 are limited to e9,f8
  • Conclude:
    • c2=6 == c8=6 -- f8=6 == e9=6 forbids e2=6

Happily, this elimination unravels the puzzle! If needed, below are the Unique Possibilities to 81 filled cells. (UP 81).
  • e2=8 e4=9 e6=2 e1=5 e9=6 a9=8 b9=5 f8=4 d8=9 d9=2 f7=5 c8=6 all %cell
  • c2=9 f5=7 f6=8 d4=4 d5=5 b5=6 a4=3 b4=7 b6=9 a6=4 a5=2 b7=1 all %cell
  • a7=9 a1=6 a3=1 b3=3 b1=8 c3=7 c2=3 f2=6 f1=2 i2=7 i3=6 i4=8 all %cell
  • h4=6 i6=3 h6=7 h7=4 i7=2 i1=9 h1=3 h3=5 h5=1 i5=4 i9=1 h9=9 all %cell

Solved Puzzle

UP 81

Complete proof of this puzzle in the style I usually use:

  1. Start at 23 filled - the given puzzle. Unique Possibilities to 28 filled. (UP 28).
    1. Locked 4's at gh7 forbids f7=4
    2. X wing on 5's at dg46 forbids bh456,de4,ef6=5
    3. f7=5 == f7=2 -- f1=2 == e1=2 -- e1=5 == e9=5 forbids d9=5, e1=68, f56=2
    4. triple {29,19,129} at (dgi9} forbids abe9=19,e9=2 UP 33
  2. fc on 6's: c2 == c8 -- f8 == e9 forbids e2=6 UP 81
  • sets: 1 + 2 + 3 + 3 + 2 = 11
  • Max depth 3: at step 2.3 and step 2.4
  • Rating: .01 + 2(.03) + 2(.07) = .21

Practice puzzles: I shall eventually add some specific ones. With the information contained in the blog up to this point, one can solve:

  • All the Tough Puzzles at Sudoku.com.au from year 2005
  • One can use the archive link at the top of the page to access these puzzles

19 Comments
Indicate which comments you would like to be able to see

Steve  From Ohio    Supporting Member
Check out my page
Not a sudoku comment here:

Why do I despise pencils?

Pencils have a single advantage: Their markings are erasable.

Pens have this advantage: Marking with pens is faster.

Since I think much faster than I can write, the act of scribing always frustrates me.

For me, easing that frustration is more valuable than ease of revision.

Meredith  From North Carolina
Steve, thanks for the blog! One question on Jan 15. In your first forbidding chain, I don't follow that f7=2 == f1=2 forbids f56=2. In the chain, we have f7=2 -- f1=2. Isn't this a weak link, not a strong one?
Mary  From Sacramento
Thanks, Steve
Chris  From Massachusetts, USA

Yikes! Now I know why I stick with hard or less...

During commercials for the Pats-Chargers game today, I worked on the Boston Globe Sudoku puzzle. I tried looking for forbidding chains, but had a tough time finding any. Wound up throwing the whole thing in the trash basket after making a mistake. The Globe puzzles are usually doable without forbidding chains, but I would like to complete a tough puzzle from this site some day. I will try printing one out, making several copies, and working on it over a longer period of time.
Thanks for the theory, Steve. Are you a math professor?
Steve  From Ohio    Supporting Member
Check out my page
Hi Meredith!
The forbidding chain, since it is a wrap around forbidding chain, proves all the weak links within it as being strong.

The fact that forbidding chains expose the multiple eliminations possible in such a situation is one of the foremost reasons that I prefer forbidding chains over other chain-like techniques.

Steve  From Ohio    Supporting Member
Check out my page
Hi Chris!
Once upon a time .... I had a vibrant interest in mathematics. Sadly, I squandered my youth and forbade myself the oppurtunity to make a career in the field.
Sudoku suprised me by awakening again the mathematical side of my brain.

I improved my ability to locate forbidding chains gradually over many puzzles.
For most people, practice may be required to fine tune the locating of chains.
Tricia  From Queensland    Supporting Member
Check out my page
Great explanation it is slowly making sense
Thanks
jyrki  From Finland
Thank you Steve!

It is beginning to make sense, and your exposition is very useful. Two comments spring to mind:

1) I really want to see somebody go thru all this in 5 minutes to solve a tough one. That is unbelievable. Some of these people are really quick/smart. I mean marking the possibilities alone would take 5 minutes for me, no time left for thinking!

2) To a great extent this technique depends on marking the possibilities. Yes, you need to do it to demonstrate the technique, but in my humble opinion Sudokus should be solved without any marking aids. I myself cannot meet this goal with the tough levels here, but the hard ones I can do.
An occasional short fc I've spotted, but no hope for the longer ones.
Steve  From Ohio    Supporting Member
Check out my page
Hi jyrki!
1) If speed of solution is the goal, then guessing is the vehicle. I suspect that the lightning fast times frequently employ a guess, or perhaps incomplete logic. Sadly, there is no way to prove or disprove that notion, as the fast solvers are not writing down their steps.
2) For me, if a puzzle does not require me to mark the possibilities, I do not find it very interesting. So, I suppose we have a philosophical difference as to what a 'good' Sudoku puzzle means. I believe that the variety of puzzles that are presented on a good sudoku site are a reflection of varied tastes.
Meredith  From North Carolina
OK, Steve, this is starting to make sense. The wrap around is a particulary powerful fc! I have to say, I agree with Jyrki - there's no way I can do these in a short amount of time, and I stubbornly want to be able to do all the steps in my head!
jyrki  From Finland
Thanks for the comments, Steve!

1) I suspect this to be the case. I do not consider a sudoku puzzle is not solved unless I can deduce that I have the only solution. Thus the difference between a solution and a proof consists of writing the steps down!

2) Degustibus non est disputandum. With your exposition in this blog I begin to understand your point of view. I guess my 'attitude problem' comes from my personal history as a sudoku enthusiast. I never learned to use possibility markers! My evolution started from using pencil markers for locked entries (like I deduced that there must be a five in abc1, or in d789, etc). Then I discovered blind/hidden groups and pencilled them in as well. After a talk with a colleague I set as a goal to solve sudokus without the possibility markers. With ferocious concentration I gradually learned to solve all the sudokus appearing in local newspapers (rated from 1 to 5 *s in difficulty) without these aids.
Thus with this history the need to start marking all the possibilities feels like a step backwards!

In my quest for more challenging puzzles (say, something I want to spend an entire Sunday afternoon rather than just a coffe break) I turned to 16x16 sudokus at the difficulty levels between medium and hard here. From your point of view that may the feel like going from word search puzzles to bigger word search puzzles :-).

To be able to do forbidding chains without markers - now that is a goal.

Steve  From Ohio    Supporting Member
Check out my page
Forbidding chains without the possibility matrix....
Not something that I could do, I fear... but
'tis certainly humanly possible for some. With some training, perhaps many.
Once upon a time in a land far, far away - when bored to tears with school, a buddy and I would play chess without the board - just writing the moves down on a piece of paper, spying the note, and responding on paper again. We played many a game that way. We did get caught, and then called liars, as the teacher refused to believe we could be playing chess sans board.
The moral of the story being, I believe that fc's can be found without possibility markers.
Steve  From Ohio    Supporting Member
Check out my page
Back when computer programs first were written and sold commercially for playing chess, they were easy to beat - as one only had to find out the 'move horizon' for the computer and then construct a position that was 'forcing' but deep. Since the computer could not see as far ahead as the human, it was then easily vanquished. Sadly, such a strategy of foiling the programming no longer works, as both the programming has gotten better, and the computers have gotten faster and have much more memory.

With sudoku, I often think of 'move horizons'. If one can develop a deep enough move horizon, than certainly forbidding chains without possibility markers could be within the scope of the human brain.
Steve  From Ohio    Supporting Member
Check out my page
In the puzzle example above, after the first puzzle mark-up:
If you were to start your search for forbidding chains in some locations other than the three strong sets that form the forbidding chain that I found, then:
Most locations for such a search are quickly discarded without any real analysis, as the endpoints of the strong links to do not provide one with weak links to other strong links. So, although the task may seem daunting at first - to search for forbidding chains that may have 68 possible starting points, it is not nearly that difficult.
First, there are only 34 strong sets really to consider. Of these, many of them are obviously not likely to lead anywhere: For example, the strong set ab3=1 has no weak links that will readily chain into another strong set. The same can be said of many other strong links in this example.
jyrki  From Finland
Steve! I think you're right. My main worry is that I might not learn to do it myself. Glad to hear that you escaped detention (even if your pride was dented by teacher not believing you). I couldn't play chess sans board. I believe my son could learn to do it quickly, and that it comes with practice. I met a guy like that in an army reserves training camp (I used a grid drawn on my notebook). The odds must be heavily stacked against find two classmates who could do it together! In high school a friend and I just used a briefcase placed between us (and containing a miniature chess set) on the last row of an auditorium. Us owning nearly identical briefcases helped :)
Norb  From California
Steve, I'm kind of a tyro and cannot see your rationale for eliminating the 5 at d9 since it is only weakly linked to one point in the chain (the 5 at d9) I do agree it should be gone but due to:
(b9=5)==(b7=5)==(f7=5)==(e9=5)

What am I missing?
Norb  From California
Correction THE 5 at d9 is only weakly linked to the 5 at e9
Steve  From Ohio    Supporting Member
Check out my page
Hi Norb!
It is also weakly linked to the 5 at f7, in the box e8.

In your argument, tho, f7,e9=5 is not yet a strong set, because of the 5 at d9!

Hopefully this clears things up. If not, you can also email me at solidsudoku@yahoo.com.
Norb  From California
Steve,

Of course you're right on both counts. In my strong chain analysis, (cuz that's the only chain I truly understand) I let your dark vertical strong link line convince me that the d9 cell was outside the e8 box. My apologies.

N
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