The general problem
Given a matrix, I would like to permute the order of values in each row, so that all the columns of the matrix sums to the same value.
A simple example
For example, given:
0 0 2 6
0 0 6 18
0 0 10 30
0 0 14 42
0 0 18 54
0 0 22 66
One solution is:
0 0 2 6
0 18 6 0
30 0 10 0
42 0 14 0
0 54 18 0
0 0 22 66
Notice that each column sums to 72. Of course, the solution is not unique; one may permute the columns themselves to obtain different solutions, such as:
0 0 2 6
18 0 6 0
0 30 10 0
0 42 14 0
54 0 18 0
0 0 22 66
The specific problem
Here I am looking at a simple $30 \times 5$ matrix. The matrix is defined thus: the contents of row $n$ is $[0, 0, 2f(n), 6f(n), 12f(n)+2]$ where $f(n) = 4n^2+4n+1$ and $n = 0, 1, 2, ...,29$.
Here is what the matrix looks like:
0 0 2 6 14
0 0 18 54 110
0 0 50 150 302
0 0 98 294 590
0 0 162 486 974
0 0 242 726 1454
0 0 338 1014 2030
0 0 450 1350 2702
0 0 578 1734 3470
0 0 722 2166 4334
0 0 882 2646 5294
0 0 1058 3174 6350
0 0 1250 3750 7502
0 0 1458 4374 8750
0 0 1682 5046 10094
0 0 1922 5766 11534
0 0 2178 6534 13070
0 0 2450 7350 14702
0 0 2738 8214 16430
0 0 3042 9126 18254
0 0 3362 10086 20174
0 0 3698 11094 22190
0 0 4050 12150 24302
0 0 4418 13254 26510
0 0 4802 14406 28814
0 0 5202 15606 31214
0 0 5618 16854 33710
0 0 6050 18150 36302
0 0 6498 19494 38990
0 0 6962 20886 41774
Obviously, the desired sum for each column is equal to the sum of all elements in the matrix divided by the number of columns. Here it is $\frac{1}{5}\left(60 + 20\sum_{n=0}^{29} f(n)\right) = 143972$.
We certainly cannot do this by brute force: For an $m\times n$ matrix the number of possibilities are: $(n!)^m$ which combinatorially explodes. Here, two of the columns given are zeros so we have $\left(\frac{n!}{2}\right)^m$ unique ways to permute the values of each row - which is not much better.
Fortunately, this matrix has a well-defined pattern to it, and I am wondering: can this pattern can be exploited to derive solutions more easily?
EDIT: I have made a recursive depth-first search to find solutions. On each iteration, it attempts to construct a vector that sums to the desired result (in this case 143972) by choosing each entry in the vector from a different row in the matrix. Once one such vector has been created, it removes the chosen entries from the matrix thereby changing it from an $m\times n$ matrix to an $m \times n-1$ one. This repeats until either no solution can be found, or a the matrix becomes empty. In the worst case, it runs on the order of $n^m$ for an $m\times n$ matrix (but it turns out that finding one solution is fast because my matrix has many, many solutions apparently).
Here are three sample solutions I have found using this approach:
Solution 1
6 14 0 0 2
0 54 18 110 0
50 0 0 302 150
0 0 98 590 294
0 0 162 486 974
0 0 242 1454 726
338 0 1014 0 2030
0 450 0 2702 1350
0 0 578 1734 3470
0 0 722 2166 4334
0 0 882 2646 5294
0 0 1058 3174 6350
0 0 1250 3750 7502
0 0 1458 4374 8750
0 0 1682 5046 10094
0 0 1922 11534 5766
0 2178 0 6534 13070
0 0 2450 7350 14702
0 0 2738 16430 8214
0 0 3042 18254 9126
3362 0 20174 10086 0
0 3698 22190 11094 0
0 12150 24302 4050 0
0 26510 13254 4418 0
0 28814 14406 4802 0
31214 15606 5202 0 0
33710 16854 5618 0 0
36302 18150 6050 0 0
38990 19494 6498 0 0
0 0 6962 20886 41774
Solution 2
6 0 2 0 14
0 110 0 54 18
0 150 0 50 302
294 590 0 0 98
486 974 0 162 0
726 242 1454 0 0
1014 2030 0 338 0
2702 450 1350 0 0
1734 3470 578 0 0
4334 2166 722 0 0
5294 2646 882 0 0
3174 6350 1058 0 0
7502 3750 1250 0 0
8750 4374 0 1458 0
10094 5046 1682 0 0
11534 5766 1922 0 0
13070 6534 2178 0 0
14702 7350 2450 0 0
16430 8214 2738 0 0
18254 9126 3042 0 0
20174 10086 3362 0 0
3698 22190 11094 0 0
0 24302 12150 4050 0
0 13254 26510 0 4418
0 4802 28814 14406 0
0 0 15606 31214 5202
0 0 5618 33710 16854
0 0 6050 18150 36302
0 0 6498 19494 38990
0 0 6962 20886 41774
Solution 3
0 14 0 6 2
0 18 110 0 54
0 0 302 150 50
0 590 294 98 0
162 974 0 486 0
1454 242 726 0 0
0 1014 2030 338 0
450 1350 2702 0 0
0 1734 3470 0 578
722 4334 2166 0 0
0 2646 5294 882 0
1058 3174 6350 0 0
0 3750 7502 1250 0
1458 4374 8750 0 0
0 5046 10094 1682 0
5766 11534 1922 0 0
2178 0 13070 6534 0
7350 14702 2450 0 0
0 2738 8214 16430 0
18254 9126 3042 0 0
0 3362 10086 20174 0
11094 22190 3698 0 0
0 4050 12150 24302 0
26510 13254 4418 0 0
0 0 4802 14406 28814
31214 15606 5202 0 0
0 0 5618 16854 33710
36302 18150 6050 0 0
0 0 6498 19494 38990
0 0 6962 20886 41774
But I still don't know whether there's a way to count the number of solutions, or how to generate more solutions more efficiently. And my depth-first-search algorithm is a rather brute-force way that doesn't take advantage of the known sequence that the original matrix is made up of.
