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

Question

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.

Answer 1

• 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.