You are given a square matrix $A \in \mathbb{ N}^{n,n}$, this number contains integers from $1$ to $n^2$. The task is to compute the minimal cost, to change this square into a perfect square. A perfect square is a Matrix, such that every row, column and (full) diagonal add up to a magic number. The Matrix is limited by containing each number from $1$ to $n^2$ exactly once.
E.g.:
$$M = \begin{bmatrix}4\,\, 9\,\, 2 \\ 3 \,\,5\,\,7 \\ 8 \,\,1\,\,6\end{bmatrix}$$
$M$ is a perfect square.
To change $A$ into a perfect square, you are allowed to change every number freely. However this increases the cost by $c_{n+1} = c_{n} + |m_{i,j} - a|$, where $a$ is the new number.
It turns out, by the way, that the magic number is always:
$$m = \frac{n\cdot (n^2+1)}{2}$$
Example of computing the cost:
$$f(\begin{bmatrix}3\,\, 7\,\, 6 \\ 9\,\, 5\,\, 1 \\ 4\,\, 3\,\, 8\end{bmatrix}) = 1$$ If we change s[1][1] to 2 and s[1][3] to 6, we get a perfect square. The cost is 2-1 = 1;
Compute the minimal cost for n = 3:
This implementation solves the problem, but I have needed to realize that there are only 8 perfect squares for $n = 3$. "$5$" for n = 3 must always be in the middle of the matrix because any of the other numbers lead to contradictions. I have found that the odd numbers except $5$ are always in the middle of the outer rows(columns), while all even numbers are in the edges. Is there a reason for that?
int formingMagicSquare(size_t s_rows, const int** s) {
long long cost = -1;
if(s_rows == 3){
cost = LLONG_MAX;
const int perfect_squares[8][3][3] = {
{{2,7,6},{9,5,1},{4,3,8}},
{{4,3,8},{9,5,1},{2,7,6}},
{{6,1,8},{7,5,3},{2,9,4}},
{{2,9,4},{7,5,3},{6,1,8}},
{{8,3,4},{1,5,9},{6,7,2}},
{{6,7,2},{1,5,9},{8,3,4}},
{{4,9,2},{3,5,7},{8,1,6}},
{{8,1,6},{3,5,7},{4,9,2}}
};
for(int k = 0; k < 8; k++){
long long cost4_this_operation = 0;
for(int i = 0; i < 3;i++){
for(int j = 0; j < 3; j++){
long long diff = perfect_squares[k][i][j] - s[i][j];
cost4_this_operation += ((diff < 0) ? -diff : diff);
}
}
if(cost4_this_operation < cost)cost = cost4_this_operation;
}
}
return cost;
}
Some questions for the mathematicians:
- Can you generalize this problem without coming up with algorithms of complexity $O(n^2!)$
- How do you build such a perfect square for n > 3
- This might be CS: Are their algorithms which lead you to the minimal cost faster?
Thank you.