This page will examine elephant guns for analyzing sudoku puzzles. This style of analysis
was introduced to me by Andrei Zelevinsky.
While AIC or forbidding chains handle bilocation and bivalue terms with sufficient efficiency,
they fail to adequately handle multiple strong/weak inferences emanating from a single node. There
are many ways to address this problem. What follows is one possible manner.
When I was first introduced to these concepts, I thought they were excellent proving tools.
However, I found them unwieldy to use as tools for finding possible sudoku eliminations or patterns.
Since then, I have changed my mind. The primary inspiration, in my opinion, is that sudoku
can be reduced to merely counting truths, and figuring out where they must lie. This is
very obvious in the first matrix type (pigeonhole). It is less obvious in the other matrix
types.
Pigeonhole Matrix
Definition
The following is true for all pigeonhole matrices:
 Each entry is a Boolean variable. (either True or False)
 Unused matrix cells  blank cells  are considered false.
 Size is nxn
 Each row contains at least one truth (a strong inference set)
 Each column, except the first column, contains at most one truth (a weak inference set)
 The first column, the result column, is proven to contain at least one truth 
thus a derived strong inference set.
In the special case where the first column is also a weak inference set, then all columns are proven
to be strong inference sets. I like to call this a
symmetric pigeonhole matrix
Caveat: A weak inference set cannot usually include the same possible Boolean argument twice. This is because
Boolean A does not normally forbid itself.
Proof
There are many possible proofs. My favorite one is simple counting:
 There are n matrix rows, thus at least n matrix truths
 For each column 2 through n, there exists at most one truth
 Thus, in n1 columns, there exists at most n1 truths.
 The number of truths is the first column is:
 greater than or equal to n (by matrix rows)
 minus at least (n1) by matrix columns
 equals at least one
One can also employ a proof by contradiction. Also an easy inductive proof is possible.
Utility
Symmetric Pigeonhole matrices easily handle proving relationships such as swordfish, naked triples,
Sue de Coq, Hub Spoke Rims, etc. The first step that I took in the Easter Monster puzzle can
also be written as such a matrix. The advantage, in the case of symmetric pigeonhole matrices, is
that little regard needs to be applied to figuring out how to build one. So, to build a matrix
to prove that Easter Monster step, one need only start listing the strong sets considered. One need
then only place the row items in a column such that they meet the weak inference requirement.
Example
In the example below, I have added a description column to the far right to describe
the nature of the strong inference set considered on each row. I have also added a description
row at the bottom to describe the nature of the weak inference set considered on each column.
1r2 
c5 
c6 
c7 

            
6r2 
c5  c6   c9 
   
   
   
2r2 
c5  c6   
c1    
   
   
7r2 
 c6   
 c3   
   
   
7c2 
   
 r1  r6  
   
   
2c2 
   
r3   r6  r5 
   
   
1c2 
   
  r6  r5 
r7    
   
6c2 
   
  r6  r5 
 r9   
   
6r8 
   
   
 c1  c4  c5 
   
1r8 
   
   
c3   c4  c5 
   
2r8 
   
   
  c4  c5 
c7    
7r8 
   
   
  c4  
 c9   
7c8 
   
   
   
 r9  r4  
2c8 
   
   
   
r7   r4  r5 
1c8 
  r3  
   
   
  r4  r5 
6c8 
   r1 
   
   
  r4  r5 

cell  cell  box  box 
box  box  cell  cell  box  box  cell  cell  box  box  cell  cell 
The matrix above proves each column is a strong inference set, justifying the eliminations argued
for in the Opening Volley on the Easter Monster.
With asymmetric pigeonhole matrices, the first column is less restricted. This, in my opinion, makes
them a bit harder to locate. However, every bilocation/bivalue AIC can be written as a
pigeonhole matrix. However, that is not the limit of their utility.
Triangular Matrices
Defintion
The following is true for all triangular matrices:
 Each entry is a Boolean variable. (either True or False)
 Unused matrix cells  blank cells  are considered false.
 Size is nxn
 Each row contains at least one truth (a strong inference set)
 Each column, except the first column, has the following quality:
 The top nonempty entry is in conflict with each entry below it
 Note there is a subtle difference here from the pigeonhole matrix.
 The following cells are always blank:
 For each row i, rowicolumnj for all j>i+1
 Note this is a significant difference
 The first column, the result column, is proven to contain at least one truth 
thus a derived strong inference set.
Proof
This proof is inductive.
 Note that for a 1x1 triangular matrix, the first row and the first column form an identity,
thus the inductive assumption is trivially true.
 Assume the inductive assumption is valid for all cases such that m<n, n>1.
 Consider an nxn triangular matrix. Two cases need be considered
 Suppose the entry at row n, column 1 is true. Then clearly the first column
contains a truth.
 Suppose the entry at row n, column 1 is false. Then some entry, call it j, j>1,
at row n column j must be true.
 Therefor, the entry at row j1, column j is false. This is, by definition, the
top entry in that column.
 Consider now the submatrix formed by rows 1 through j1 and
columns 1 through j1. It is a triangular matrix. Therefor, some
item in column 1 must be true.
Utility
Triangular matrices are useful to tackle situations which require nets. The downside is
that one needs to start with a bivalue/bilocation type of argument. However, one can continue from
that argument and add strong inferences at will, as long as one only adds one extra undetermined
item each time. Some where one then needs to close the loop. This is a bit arbitrary, though. One
can always close the loop. However, there is no gaurantee that closing the loop will yield anything
valuable.
Example
Complex single candidate chain
I encountered the situation above while wrestling with the Easter Monster. Candidate 1
is limited to the highlit cells. The cells that are highlit blueish represent the four
strong inference sets that I considered. Typically, when I color, I break out subgroups and
analyze their interactions. One could say all sudoku eliminations stem from a similar reduction
in puzzle strong inferences considered.
As an AIC, I could write:
 (1): r2c7=c5[c5r48,r3c6]=[r4c78=c3r8c3=c4c6r7=r6] => r6c7 <>1
Note that I need to do two things:
 recognize the multiple forbiddings caused by (1)r2c5
 break out a subchain  contained above by the brackets [].
If I am thinking triangular matrix like, here is what I do:
 Start with the bilocation relationship r2c7=r2c5
 Decide that r2c7 may be my start point
 Consider all the forbiddings produced by r2c5
 Look for a conditional subchain that always has no more than one extra candidate
 Locate such a chain and bring it to focus on one cell
Here is the resultant triangular matrix: (I have added labels to the left of the matrix to
define the strong inference sets considered.)
1r2 
c7 
c5 


1r4  c78  c5  c3  
1r8   c5  c3  c4 
1c6  r6  r3   r7 
Using the Triangular Matrix thought process has proven valuable (for me at least) in
finding such eliminations.
Note that one can expand the idea to use triangular matrices to find new strong inference sets,
even if the sets do not immediately forbid anything.
Block Triangular Matrices
Defintion
The following is true for all block triangular matrices:
 Each entry is a Boolean variable. (either True or False)
 Unused matrix cells  blank cells  are considered false.
 Size is nxn
 Each row contains at least one truth (a strong inference set)
 Each column, except the first column, has the following quality:
 The top nonempty entry is in conflict with each entry below it
 Note there is a no difference here from the triangular matrix.
 If there are two top entries in a single row, then they each form a block. Each
of these blocks must form triangular matrices.
 The first column, the result column, is proven to contain at least one truth 
thus a derived strong inference set.
Proof
By defintion, block triangular matrices reduce to a strong inference set of triangular matrices.
Utility
Block triangular matrices are helpful in pushing deductions through unavoidable multivalue
or multilocation strong inference sets. In general, they are ugly. In practice, they are usually
avoidable. However, in some cases they are the quickest way to a deduction.
Example
Below is another example from the Easter Monster. At this point, I am not certain if the following
step will be in my solution. Nevertheless, it is one of the deductions sitting on my desktop.
Complex xyz winglike configuration
The deduction centers upon (1=6)r6c6. The logic plays out: (1)r7c4=[(2)r7c8=(2)r7c6] => r7c4≠2. The path to get there starts:
(1)r7c4=[(2)r7c8=(21)r5c8=[(1)r7c6=(1)r7c2(1)r5c2=(1)r5c4](1=6)r6c6.....=(2)r7c6]. The entire
path is very messy to place into AIC language. However, it is fairly straighforward as a Block Triangular
Matrix (BTM).
Once again, the first column will be a strong inference set descriptor. Note also that the
path uses a proven strong set and a proven weak set. Specifically, the following two proven (previously on
the opening page of the Easter Monster)
relationships are used: (1)r7c2=(6)r9c2 and (1)r45c8(6)r45c8. The first of these serves to shorten the deduction a bit.
The weak relationship is not really required, but it is a more accurate representation of
how I found the elimination.
2c8 
r7 
r5 










r6c6 
  1  
6    
   
1r7 
c4   c6  c2 
   
   
1r5 
 c8  c4  c2 
   
   
6r5 
 c8   
c4  c2   
   
16B7c2 
   
 (6)r9  (1)r7  
   
1c6 
   
r6   r7  r3 
   
1c8 
 r5   
   r3 
r4    
6B6 
   
   
c8  r4c9   
7r4 
   
   
c8  c9  c3  
7r2 
   
   
  c3  c6 
2c6 
r7    
   r3 
   r2 
Note that (1)r6c6 reverts cleanly back to matrix column 1 with a 3x3 Triangular matrix,
whilst (6) r6c6 leaves in its wake a 9x9 Triangular matrix. They both overlap with the first matrix
row. The primary keys to finding the deduction are the first four matrix rows and the last matrix row.
The rest of the deduction is relatively easy (for that puzzle, I mean!) once one sees those parts.
Mixed Block Matrices
Definition
The following is true for all Mixed Block Matrices:
 Each entry is a Boolean variable. (either True or False)
 Unused matrix cells  blank cells  are considered false.
 Size is nxn
 Each row contains at least one truth (a strong inference set)
 The matrix is divided into blocks. The blocks are themselves one of the
previously defined matrix types. The matrix is configured such that it represents
an OR of the matrix blocks. This configuration results in a strong inference set of
matrices
 The first column, the result column, is proven to contain at least one truth 
thus a derived strong inference set.
Proof
This matrix type is so general that a rigourous proof, although possible, is a bit unwieldy. The
honus of creating a valid matrix configuration is upon the author. The short, conceptual form of the proof is:
An AIC of matrices
Utility
By mixing matrix types, one can write steps such as the Almost Remote Pair step of my solution
to Unsolvable 13 with relative ease. The real value lies in opening up the possibility matrix for
unconventional attack.
Example
The previous blog page, Opening Volley on the Easter Monster,
uses the following chain:
 note: (2)r5c2(2)r5c8 =>(16)r5c2=(16)r5c8
 (16)r5c2: (1)r8c3=(1)r7c2(1=6)r5c2(6)r9c2=(6)r8c1 => (1=6)r8B7 and (16)c2B7
 (16)r5c8:
 [(7)r8c4=(7)r8c9(7)r9c8=(72)r4c8=(2)r7c8(2)r8c7=(2)r8c45]
 (16)@r8c4ORc5=[(1)r8c3=(16)r8(c5ORc4)=(6)r8c1]
=> (1=6)r8B7 and (16)c2B7
 Clearly, we have proven (1=6)r8B7 and (16)c2B7
This same deduction can be easily written into a Mixed Block Matrix.
1B7 
r8 
c2 







6B7 
r8   c2  
   

r5c2 
 1  6  2 
   

2c8 
   r5 
r4  r7   

7c8 
   
r4   r9  

7r8 
   
  c9  c4 

2r8 
   
 c7   c4 
c5 
1r8 
 c3   
   c4 
c5 
6r8 
  c1  
   c4 
c5 
The bold items represent a 6x6 pigeonhole matrix. The result column of this 6x6
pigeonhole matrix is :[(1)r8c3=(6)r8c1]=(2)r5c8. The other items are part of a general
Triangular matrix. The final result, (1=6)r8B7 should be rendered more transparent.
Summary
Matrices are most definately elephant guns. They need only be employed when tackling the
most difficult of puzzles. Perhaps they are never necessary. There are other techniques that can
supplant them. However, thinking in terms of matrices can reduce elimination investigation to
a mere counting exercise. I look at a group of strong inferences and think perhaps:
and I know that I have found something.
This page is intended to also be a supplement for the eventually forthcoming solution to the
fabled Easter Monster puzzle.
Please to post a comment.
Not a member? Joining is quick and free.
As a member you get heaps of benefits.
to join.