Defined a magic square
n x nto be a matrix of distinct positive integers from
1 to n²where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant. The given
3 x 3a matrix s of integers in the inclusive range
[1, 9]. The program can convert any digit a to any other digit b in the range
[1, 9]at cost of
[a — b]. Given s, convert it into a magic square at a minimal cost. Print this cost on a new line.
The solving of this exercise isn’t so difficult. The main issue here is to understand the meaning and specification. I want to define the main parts of the magic square:
- All rows, columns, diagonals are always equal to
nis a matrix size. (Matrix should be a square)
- Items should be the arithmetic progression. Matrix with all number 3 or 4 for example is not a magic square. (It can be helpful if you need to calculate the sum of all items in a huge magic square). So the magic square
3 x 3should contain only
n ^ 2 = 1, 2, 3, 4, 5, 6, 7, 8, 9
- The order has matter!
So, in this exercise, we have only a
3 x 3 matrix. Magic square like that has only 8 possible variations of order. We need to compare this matrix with all these variations. The solving can be smarter for n x n matrix. But it was so slow (exercises on HackerRank has time complexity limitations, and that’s why solving looks silly).
We need to create all possible variations of the magic square with
3 x 3 size. Then calculate the difference between each variation and input matrix. The minimum value of these differences is our answer