Forbidding Chains 101 The Theory


Many places with tips, tricks, techniques or help on how to solve sudoku puzzles completely miss the true power of forbidding chains. When each is considered in their most general form, Alternating Inference Chains and Forbidding Chains are equivalent.

Rusted Chains - Greenock by Craig McMaster

A puzzle perplexes perhaps,

Stamina and strength it saps.

That taunting tyrant, this trick tames!

Fear not, forge forbidding chains!





If this is your first visit to my blog, you may wish to peruse previous blog pages. If so, point your mouse to the right, under Previous Entries. Many of the terms I use here have been previously defined. Please refer to the Definitions if you need them.

Why bother with forbidding chains?


Well, if you do not mind guessing, then really there is no reason. If, on the other hand, you
like to justify your reasons for filling in the puzzle, then forbidding Chains are:
  • Complete - All the information to justify an elimination is contained within the chain.
  • Concise - Given you want to be complete, I know of few shorter expressions
  • Circumspect - Few puzzles fail to be constrained by forbidding chains
  • Clear - The reasoning for an elimination is transparent.
  • Comprehensive - Most logical techniques within Sudoku (and many beyond Sudoku) are forbidding chains
  • Contagious - Once you have been bitten by the chain finding bug, they are hard to resist
  • not Complex - Once you own the concept, it is not difficult

Since there is a fair amount of writing on the web concerning forbidding chains, I thought I might weigh in on what they are not. Forbidding chains are not:

  • forcing chains
  • limited to conjugate pairs
  • limited to X cycles, Y cycles, tricycles, motorcyles, etc.
  • guessing
  • limited to Nishio chains
  • limited to Sudoku
  • and the list could be endless, almost
Forbidding chains, properly understood, have as a subset the following Sudoku techniques:
  • Locked candidates
  • Naked subsets (pairs, triples, quads, etc)
  • Hidden subsets
  • Coloring
  • Xwings, swordfish, jellyfish, squirmbags, etc.
  • Y wings, Y wing styles
  • Sue de Coq
  • Alternating inference chains (AIC)
  • Almost locked sets
  • Turbot fish
  • and the list could go on, and on, and on
The only techniques that do not fit nicely into the manner that I will explain forbidding chains are those involving Uniqueness of Solution. Even those, though, may fit under the wide tent of forbidding chains

When I first started to attempt the Tough puzzles at Sudoku.com.au, I suspect that I was no different than most people who see forbidding chain proofs today. My eyes glossed over. I had no clue what the terminology meant. I thought that Sudoku was so easy that elevating proofs to such terminology was the height of grandiosity. I committed an intellectual mortal sin. I had contempt prior to investigation. gb from france very kindly, and oh so politely, set me straight. My mind, slowly and begrudgingly, opened to the power of forbidding chains. This conversation is found in the comments from the Tough puzzle of February 2, 2006.

It is assumed, for the rest of all the pages that deal with forbidding chains, that one is familiar with the following terms and symbols, as I define them, in my Definitions.

  • Boolean variable
  • strong
  • weak
  • native
  • ==
  • --
Caveat If you have garnered the meaning of any of the above elsewhere, there is some chance of misunderstanding my definitions. The differences may be logically slight, but the implications of these differences are potentially large.

Alternating Inference Chains, called AIC for short, are the same concept as forbidding chains. The manner that I define forbidding chains, though, allows more flexibility. The main difference being that I limit the arguments in a forbidding chain less.

For the rest of this discussion, a single capital letter is presumed to be a Boolean variable. Consider the following truth tables (list of possible states) for (A == B), (A -- B):


A == B A -- B
TrueTrueFalseFalse
TrueFalseTrueFalse
FalseTrueFalseTrue

As you can see from the truth tables, if exactly one of A,B is true, then their relationship is both strong and weak. Limiting the use of forbidding chains to such conjugate pairs is both needlessly restrictive and enormously counterproductive. It is true, however, that in Sudoku, if {A,B} is a native strong set then {A,B} is also a native weak set. If a link is both strong and weak, the proof writer merely chooses which of these qualities advances the proof. Recall:
  • (A == B) means at least one of {A,B} is True.
  • (A -- B) means at most one of {A,B} is True.
This is, really, all you need to know. The rest of the information contained on these pages is nothing but the logical consequences of linking these two relationships together.

Chain Linking Theory

Theorem 1

  • If: A == B -- C == D
  • Then: A == D

Proof: Consider the following hypothetical chain:

  • A == B -- C == D
  • Interpret this chain as being three independent statements:
    1. A == B
    2. B -- C
    3. C == D
    • Suppose A is true. Then, we know nothing about whether B and therefor C, D be true or false. This is ok.
    • Suppose A is false. Then by 1) above, B is true.
    • If B is true, then by 2) above, C must be false
    • If C is false, then by 3) above, D must be true
    • Now, consider the following proven truth table:
      A ??? D
      TrueTrue
      TrueFalse
      FalseTrue
      
      If you compare this table with the one above regarding (A == B), it should be
      clear that one can conclude: (A == D).
Theorem 1 begs:

Consider the following hypothetical chain:

A == B -- C == D -- E == F
 Again, interpret this chain as five independent statements. From Theorem 1, we
know:
  1. A == D
  2. Substitute: (A == B -- C == D) with (A == D), using theorem 1.
  3. Giving: A == D -- E == F
  4. Repeat steps 2 & 3 on this new chain.
  5. Conclude: A == F
We can argue similarly for chains of any length. I will forgo a formal proof (induction is one way) of this argument, and post:

Theorem 2

  • Let i, j, n be positive integers
  • Let Ai == Bi for all (i ≤ n)
  • Let Bi -- Ai+1 for all (i < n)
  • Conclude
    • Ai == Bj for all (i ≤ n), and for all (i ≤ j ≤ n)
Perhaps a bit heavy? Do not worry. Just know that one can expand the chains to any length.

What is important here? A forbidding chain must have alternating strong and weak links.

So what?

Forbidding chains are of little use unless they do as the name implies, forbid something! If any of the native strong sets in the chain, or any of the proven strong sets of the chain, are weakly linked with a common Boolean variable (sees the same candidate cell combination, in sudoku), then that common item is forbidden. Consider a short chain:

  • A == B
  • Suppose: C -- A == B -- C
  • Conclude: C is forbidden
This is easily understood as follows:
  • If A is true, then C must be false
  • If A is false, then B must be true, so C must still be false
Also, this idea can be understood through the following:

Theorem 3

  • Suppose C -- A == B -- D
  • Then C -- D
Proof:
  • Suppose (C -- D) is invalid. Then
  • C and D can be both true at the same time.
  • If C is true, then (C -- A) implies A is false
  • If D is true, then (D -- B) implies B is false
  • But, (A == B) means at least one of {A,B} is true
  • Thus we have a proof by contradiction. (C -- D) is not invalid.
Note if (C ≣ D), they both must be false.

The Wrap around chain

Suppose we had the following short chain:

  • A == B -- C == D
  • Suppose further:
    • A -- D
This is the shortest meaningful expression of a wrap around forbidding chain. Note since (A -- D), one could write the short chain above in a different order:
  • C == D -- A == B
  • and further:
    • B--C
Notice that the chain wraps around itself, or loops. It really has no endpoint, nor does it have a starting point. One can easily extrapolate this idea to chains of any length. Note that Theorem 4 below and Theorem 2 above are very similar, but significantly different.

Theorem 4

  • Let i, j, n be positive integers
  • Let Ai == Bi for all (i ≤ n)
  • Let Bi -- Ai+1 for all (i < n)
  • Let A1 -- Bn
  • Conclude
    • Ai == Bj for all (i ≤ n), and for all (j ≤ n)
    • Ai -- Bj for all (i ≤ n), and for all (j ≤ n)
Alternative explanation of Theorem 4:
  • Given any forbidding chain, of any length such that
    • Two proven strong endpoints of the chain are weakly linked
  • All the weak links of the chain that lie between these endpoints are also strong
  • All the strong links of the chain that lie between these endpoints are also weak

Theorem 4 exposes some of the additional power of forbidding chains. The following sudoku techniques are actually wrap around forbidding chains with two native strong links. As such, they are logically equivalent:

  • Naked pairs
  • Hidden pairs
  • X wings
This logical equivalence is a perhaps surprising result of forbidding chain analysis. I doubt that many, when first learning the three techniques above, think of them as being the same.

A wrap around forbidding chain is also called a nice loop.

The only other introduction to forbidding chains that I recommend is Forbidding Chains for absolute beginners by my first sudoku mentor, Bruno Greco.




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

In so many ways, the approach that Bruno Greco uses to explain forbidding chains is far superior to mine.

I choose to tread a slightly different path because:

Many times, alternate explanations of the same idea help people to understand better.

My more confusing, but more More...
 |  |
Steve, you're taking me back to that awful proofs class I had to take to earn my degree in math. I do want to get these chains down, though, so I don't hold it against you. *laugh*
 |  |
Hi JL!

I know the feeling!

Hopefully, the blog will yield tips that are usable for most.

Nevertheless, in order to really delve into the more advanced techniques, I am presented with a problem. Each one of the advanced ideas not yet treated in this blog are generally More...
 |  |
Hi STEVE,

THANK YOU VERY MUCH!
I have one dumb question... What is mean 101? you finished this on 10 Jan.?
 |  |
Hi ttt!
101 is alluding to a common manner of describing course difficulty in univerisities in this country, USA. Numbers such as this are almost added behind the course title.

Generally, the numbers start with a low number for less difficult courses, and a higher number for more More...
 |  |
Hmmmm In my comment above to ttt, I seem to have
forgotten the word 'always'. Should read:
'.... are almost always added ....'
 |  |
Wow! I really want to understand this and be able to complete the tough puzzles without guessing, but all the mathematical talk makes my head spin. Math is definitely not my strong suit. Oh well, I guess it takes time.
17/Apr/10 6:07 AM
 |  |
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
Check out all the Daily Horoscopes
Welcome our latest Members
neilehh from Anakie, Vic, Aussie
b33h1v3 from g3r0
ssduniversal from India
Member's Birthdays Today
Kristy B from Everett, WA
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.