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 c5c6c9
2r2 c5c6 c1
7r2 c6 c3
7c2 r1r6
2c2 r3r6r5
1c2 r6r5 r7
6c2 r6r5 r9
6r8 c1c4c5
1r8 c3c4c5
2r8 c4c5 c7
7r8 c4 c9
7c8 r9r4
2c8 r7r4r5
1c8 r3 r4r5
6c8 r1 r4r5
cellcellboxbox boxboxcellcellboxboxcellcellboxboxcellcell

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

Easter Monster triangular matrix example

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
1r4c78c5c3
1r8c5c3c4
1c6r6r3r7

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

Easter Monster block triangular matrix example

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 c4c6c2
1r5 c8c4c2
6r5 c8 c4c2
16B7c2 (6)r9(1)r7
1c6 r6r7r3
1c8 r5 r3 r4
6B6 c8r4c9
7r4 c8c9c3
7r2 c3c6
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 r8c2
r5c2 162
2c8 r5 r4r7
7c8 r4r9
7r8 c9c4
2r8 c7c4 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.




4 Comments
Indicate which comments you would like to be able to see

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
 |  |
Please Log in to post a comment.

Not a member? Joining is quick and free.
As a member you get heaps of benefits.
Click Here to join.
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 Members
Tatiana from Malacca
tannalo from Queensland
dgreen from canada
Member's Birthdays Today
None Today.
Friends currently online
Want to see when your friends are online? Become a member for free.

Network Sites

Melbourne Bars Find the Hidden Bars of Melbourne
Free Crossword Puzzles Play online or print them out. 2 new crosswords daily.
Jigsaw Puzzles Play online jigsaw puzzles for free, with new pictures everyday
Sliding Puzzle Play online with your own photos
Flickr Sudoku Play sudoku with pictures from Flickr
Kakuro Play Kakuro online!
Wordoku Free Wordoku puzzles everyday.
Purely Facts Test your General Knowledge.
Pumpkin Carving Pattern Free halloween pumpkin carving patterns.