# Matrices in Sudoku

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 n-1 columns, there exists at most n-1 truths.
• The number of truths is the first column is:
• greater than or equal to n (by matrix rows)
• minus at least (n-1) 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 non-empty 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
1. Suppose the entry at row n, column 1 is true. Then clearly the first column contains a truth.
2. 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 j-1, column j is false. This is, by definition, the top entry in that column.
• Consider now the submatrix formed by rows 1 through j-1 and columns 1 through j-1. 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.

### 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 sub-groups 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=c3-r8c3=c4-c6r7=r6] => r6c7 <>1
Note that I need to do two things:
1. recognize the multiple forbiddings caused by (1)r2c5
2. break out a sub-chain - contained above by the brackets [].

If I am thinking tri-angular matrix like, here is what I do:

• Decide that r2c7 may be my start point
• Consider all the forbiddings produced by r2c5
• Look for a conditional sub-chain 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 non-empty 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 multi-value or multi-location 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 wing-like 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=(2-1)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
1. (16)r5c2: (1)r8c3=(1)r7c2-(1=6)r5c2-(6)r9c2=(6)r8c1 => (1=6)r8B7 and (1-6)c2B7
2. (16)r5c8:
1. [(7)r8c4=(7)r8c9-(7)r9c8=(7-2)r4c8=(2)r7c8-(2)r8c7=(2)r8c45]
2. -(16)@r8c4ORc5=[(1)r8c3=(1-6)r8(c5ORc4)=(6)r8c1]
=> (1=6)r8B7 and (1-6)c2B7
• Clearly, we have proven (1=6)r8B7 and (1-6)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:

• +1,+0,+0,+1,-1,+0,-1
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.

 Indicate which comments you would like to be able to see GeneralJokesOtherSudoku Technique/QuestionRecipes
 Hi STEVE, Very very good work STEVE... ! But I think how many people come here can understand ...? How about EUREKA Site now...? 28/Nov/07 2:53 AM |  |
 Hi ttt! Thanks! 'tis a bit much, some of this stuff. But, to slay a beast one must sometimes wield weaponry that takes some training, not to mention straining. Eureka is down for a bit, but I think it is coming back up soon. 28/Nov/07 5:33 AM |  |
 Eureka is opening back up at the following address:http://212.188.181.131/index.htm You may have to eliminate spaces if you paste that into the address bar of your browser. 28/Nov/07 11:42 PM |  |
 Hi STEVE, Thanks and waiting your proof for Easter Monster and next for ...Golden Nugget 29/Nov/07 2:06 AM |  |

Not a member? Joining is quick and free.
As a member you get heaps of benefits.
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 MembersIppy from Australiadrnancy from Mill Creek, WADeena Priyam from India
 Member's Birthdays Todaylinda from melbourne aust