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.
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;
}
I have more questions about this code and I am not sure if I am allowed to ask them here because they ask for better ways to do this. However, I have specific questions:
- How do you return properly if the program cannot solve a certain case?
Can you calculate the absolute amount better than:
long long diff = perfect_squares[k][i][j] - s[i][j]; cost4_this_operation += ((diff < 0) ? -diff : diff);
- The for-Looping seems not to be proper. How would you do that?
Thank you.
6
in the right place. Should it be2
? \$\endgroup\$ – vnp May 17 '19 at 15:55