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.

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 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:

• 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 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.