Forbidding Chains 102 The Practice


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

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.

 |  |
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?
 |  |
Thanks, Steve
 |  |

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 More...
 |  |
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.

 |  |
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 More...
 |  |
Great explanation it is slowly making sense
Thanks
 |  |
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 More...
 |  |
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 More...
 |  |
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!
 |  |
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 More...
 |  |
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 More...
 |  |
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 More...
 |  |
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 More...
 |  |
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 More...
 |  |
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?
 |  |
Correction THE 5 at d9 is only weakly linked to the 5 at e9
 |  |
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.
 |  |
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.
Click Here to join.
You can also try the Chatroom (No one chatting right now - why not start something? )
Check out the Sudoku Blog     Subscribe
Members Get Goodies!
Become a member and get heaps of stuff, including: stand-alone sudoku game, online solving tools, save your times, smilies and more!
Previous Entries

07/Jan/07 Ywing Styles
06/Jan/07 Definitions
31/Dec/06 Y wings
27/Dec/06 Coloring
11/Dec/06 Beginner Tips
Brought to you by the same team that put the
Cheap Flights into IWantThatFlight.com.au
Check out all the Daily Horoscopes
Welcome our latest Members
PumpkinFace from PA
messipicane from Cameroon
Aurelia from La Mesa
Member's Birthdays Today
Wagdy Kamel from EGYPT-now in FL.USA., Mary from St. Louis, hocadobi from Arizona, USA
Friends currently online
Want to see when your friends are online? Become a member for free.

Network Sites

Melbourne Bars Find the Hidden Bars of Melbourne
Free Crossword Puzzles Play online or print them out. 2 new crosswords daily.
Jigsaw Puzzles Play online jigsaw puzzles for free, with new pictures everyday
Sliding Puzzle Play online with your own photos
Flickr Sudoku Play sudoku with pictures from Flickr
Kakuro Play Kakuro online!
Wordoku Free Wordoku puzzles everyday.
30 Dollar Date Night - Date Ideas for Savvy Partners.
Pumpkin Carving Pattern Free halloween pumpkin carving patterns.