Forbidding Chains 101 The Theory - Sudoku Solving Technique

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.

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 Sudoku Techniques. 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
True		True		False		False
True		False		True		False
False		True		False		True

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
    True		True
    True		False
    False		True

    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 A_i == B_i for all (i ≤ n)
• Let B_i -- A_i+1 for all (i < n)
• Conclude
  • A_i == B_j 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 A_i == B_i for all (i ≤ n)
• Let B_i -- A_i+1 for all (i < n)
• Let A₁ -- B_n
• Conclude
  • A_i == B_j for all (i ≤ n), and for all (j ≤ n)
  • A_i -- B_j 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.