Hackerrank: Forming a magic Square

I must admit that this problem actually took me a good while to solve. Once you have the right insight on forming a magic Square it is really straight forward. But until that point I was just stuck. Anyway, before rambling on lets get to the actual problem.

We define a magic square to be an  matrix of distinct positive integers from 1 to nwhere the sum of any row, column, or diagonal (of length n) is always equal to the same number (i.e., the magic constant).

Consider a  matrix, s, of integers in the inclusive range [1, 9]. We can convert any digit, a, to any other digit, b, in the range [1, 9] at cost .

Given , convert it into a magic square at minimal cost by changing zero or more of its digits. Then print this cost on a new line.

Note: The resulting magic square must contain distinct integers in the inclusive range [1, 9].

I started out with the idea that I could go through the square and change the number one by one based on an evaluation of the individual digits. But I realized from the second example that in some of the cases multiple numbers needed to be changed in order to which meant that I couldn’t just evaluate the individual digits to see if it should be changed.

Checking all possibilities for forming a magic square

Back to the drawing board.  I thought of checking all combinations but on the outset there was 9! = 362.880 possible solutions. What did I know about forming a magic square? I know that the so called magic constant has to be 15, so 5 have to be placed in the middle, which reduces the combinations to  8! = 40.320 a lot better.

That was when it dawned on me, that in order to make every sum crossing the center the pairs would be {1,9}, {2,8}, {3,7} and {4,6}, which means I just had to place 1-4 and the rest was given. that could be done in 876*5 = 1680. Possibly something I could brute force. However, I knew that not all of those 1680 solutions would be valid. As an example if I put 1 in the upper left corner I could not put 2 and 3 in the top row.  Which meant I had to consult google. It turns out there are only 8 possible solutions to the problem as given on the blog post on mindyourdecisions.

That should be rather easy to bruteforce. Just check the difference between the numbers in the given input and the 8 possible solutions and then take the smallest of those.

The implementation I did looks like

s = [[int(i) for i in input().split(' ')] for j in range(3)]
n = [s[i][j] for i in range(3) for j in range(3)]
all_n = [
            [8, 1, 6, 3, 5, 7, 4, 9, 2],
            [6, 1, 8, 7, 5, 3, 2, 9, 4],
            [4, 9, 2, 3, 5, 7, 8, 1, 6],
            [2, 9, 4, 7, 5, 3, 6, 1, 8],
            [8, 3, 4, 1, 5, 9, 6, 7, 2],
            [4, 3, 8, 9, 5, 1, 2, 7, 6],
            [6, 7, 2, 1, 5, 9, 8, 3, 4],
            [2, 7, 6, 9, 5, 1, 4, 3, 8]
        ]

allsum = []
for l in all_n:
    allsum.append(sum([abs(n[i]-l[i]) for i in range(9)]))

print(min(allsum))

As you can see I start by reading the input and making it into a 1 dimensional array. After that I hardcoded all 8 solutions. And then I just find the difference of each solution and the input and print the minimum. It might be possible to do it in less lines of code, but this one worked out nicely.

Posted by Kristian

Leave a Reply