2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Please include the language you're using in the tags. Looks like C? \$\endgroup\$ – AlexV May 17 at 14:33
  • \$\begingroup\$ 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. \$\endgroup\$ – pacmaninbw May 17 at 15:11
  • \$\begingroup\$ I delete question 3. I think question 1 is fine, since this only a sidenote. \$\endgroup\$ – TVSuchty May 17 at 15:19
  • \$\begingroup\$ Your example looks wrong - it already has 6 in the right place. Should it be 2? \$\endgroup\$ – vnp May 17 at 15:55
  • \$\begingroup\$ yes. Thank you. \$\endgroup\$ – TVSuchty May 17 at 16:00
3
\$\begingroup\$
  • 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.