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 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 
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:
 A == B
 B  C
 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:
 A == D
 Substitute: (A == B  C == D) with (A == D), using theorem 1.
 Giving: A == D  E == F
 Repeat steps 2 & 3 on this new chain.
 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:
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:
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_{1}  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.
Please to post a comment.
Not a member? Joining is quick and free.
As a member you get heaps of benefits.
to join.