# Groups within Matrix - Challenge Exercise

1. Mar 18, 2013

### hzb5080

Hello, I am writing my first software program (language:python) with the goal of conducting an interesting exercise related to matrices. I've ran into a slightly complex problem. First let me define something that will make my problem easier to communicate. Let an "H group" be a group of cells in matrix A. The group has an order to it, may start anywhere in matrix A and each cell is connected to an adjacent unused cell. No cell can be used twice and call the number of cells in any given H group its length, L. Example:

Matrix A: 2x2:

[1][2][3]
[4][5][6]
[7][8][9]

An H group that starts at cell [1], has length 4 and goes clockwise along the perimeter would be : [1], [2], [3], [6]. This H group has 1 turn. Other examples of H groups: [2],[5],[9],[6],[8] and [7],[8],[9],[6],[5],[4],[1],[2],[3] and [3],[5],[6],[2] and [1],[2],[6],[8] but NOT [1],[2],[8].

My goal is to find and equation to represent the number of H groups with length L>=3 in a pxq matrix. These H groups may have turns (unlike the two equations below)

Now, I've obtained an equation to find the number of H groups that are directed only Up, Down, Left and Right. Keep in mid this means these H groups have no "turns" in their pattern and the pattern connecting the cells is either purely up, down, left or right. This equation is: sum of up + down + left + right = 2p(q-L+1)+2q(p-L+1). Note, this form of the equation does not hold for H groups with L = 1. Please disregard this.

I've also obtained a similar equation for the diagonal sum of H groups. Again, no turns allowed. The sum of unidirectional diagonal H groups in any direction (upright, upleft, downright or downleft) is =(p-L+1)*(q-L+1). The sum of all 4 directions is 4*(p-L+1)*(q-L+1). Again ignore the case of L = 1.

Now I obtained these two equations by picking small pxq matrices, counting the unidirectional H groups and finding a pattern that lead me to the equation. However, the complexity is greatly increased when turns are involved. I could try a brute force approach and start with a 2x2 matrix and find all the H groups by hand. This has so far proven unhelpful...

The following part may or may not be useful depending on how clearly you interrupt me. I encourage you to ignore it if you do not fully understand...Though I was able to fairly easily predict H groups of length L=4 in a 2x3 matrix by looking at the H groups of length L=3, I have found no reasonable pattern. The approach I've been taking involves looking at unique patterns (aka basic shapes) and rotating these basic shapes.