# Computing the cost for creating a perfect square (with N = 3)

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:

1. How do you return properly if the program cannot solve a certain case?
2. 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);

3. The for-Looping seems not to be proper. How would you do that?

Thank you.

• Please include the language you're using in the tags. Looks like C? – AlexV May 17 at 14:33
• You have put the full text of the problem requiring a solution in the question, is there a link that you can provide to the question (is this a programming challenge of some sort)? The specific question questions may put this question off-topic, especially specific questions 1 and 3. – pacmaninbw May 17 at 15:11
• I delete question 3. I think question 1 is fine, since this only a sidenote. – TVSuchty May 17 at 15:19
• Your example looks wrong - it already has 6 in the right place. Should it be 2? – vnp May 17 at 15:55
• yes. Thank you. – TVSuchty May 17 at 16:00

• Since the function is hardwired to 3x3 matrices, it would make sense to pass a 3x3 matrix as an argument:

int formingMagicSquare(const int s[3][3])

This way you will not worry about what to do if s_rows != 3.

• stdlib provides int abs(int).

• The line

if(cost4_this_operation < cost)cost = cost4_this_operation;

better be split into

if(cost4_this_operation < cost) {
cost = cost4_this_operation;
}

Even better, make a static inline int min(int, int) function.

• I see nothing wrong with the loops.

• Of course, the solution is not scalable for larger dimensions.

• is not that inline C++? why should I split? – TVSuchty May 17 at 20:18
• @TVSuchty inline is C, see 6.7.4 Function Specifiers part of the Standard. Split because long lines are hard to read and maintain. – vnp May 17 at 20:28