# 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? May 17, 2019 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. May 17, 2019 at 15:11
• I delete question 3. I think question 1 is fine, since this only a sidenote. May 17, 2019 at 15:19
• Your example looks wrong - it already has 6 in the right place. Should it be 2?
– vnp
May 17, 2019 at 15:55

• 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? May 17, 2019 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, 2019 at 20:28
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 12, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://codereview.stackexchange.com/questions/220416/computing-the-cost-for-creating-a-perfect-square-with-n-3", "fetch_time": 1713598286000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-18/segments/1712296817491.77/warc/CC-MAIN-20240420060257-20240420090257-00702.warc.gz", "warc_record_offset": 158667120, "warc_record_length": 41975, "token_count": 1258, "char_count": 3830, "score": 4.4375, "int_score": 4, "crawl": "CC-MAIN-2024-18", "snapshot_type": "longest", "language": "en", "language_score": 0.8059774041175842, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00059-of-00064.parquet"}