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.