Magic Square HackerRank Exercise
Defined a magic square n x n to be a matrix of distinct positive integers from 1 to n^2 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 3 a 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 n^2, where n is 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 3 should 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