Forming Magic Squares

I want to share my experience resolving hard problems(they were to me). This one from hackerrank.

Here we’ll be approaching Magic Squares that has a fixed size of 3 x 3

STOP THIS MADNESS AND SHOW ME THE CODE

Photo by Michael Dziedzic on Unsplash

I struggle maybe over a week in order to unveiling the correct logic to be applied to this problem. It was really frustrating to not came up with a good solution for many days. Then I decided I would record every failure I ran into and made a notebook that could be shared with people in the same Journey.

When I approached the very first time the challenge (forming magic squares) I didn’t know that there was a whole narrative around Magic Squares. There is! and the first concept we must seeking to understand is the Magic constant.

Magic constant

The first thing shock me out, it was the existence of a constant that makes a lot easier to reason about magic squares: The Magic Constant. And it turns out it depends uniquely on the magic square length. I mean, it can be calculate it just knowing the length of any inner array.

M = n(n2+1)/2 (from geeksforgeeks)

Magic squares

Here the definition from HackerRank

We define a magic square to be an matrix of distinct positive integers from to where the sum of any row, column, or diagonal of length is always equal to the same number: the magic constant.

Surfing around the web I came across with the solution on geeksforgeeks, but I couldn’t understand the solution and neither it was the one I was looking for. The algorithm was focused in building a magic square using random numbers but says nothing about shaping one from having already the numbers. It tried to define some rules for making magic squares and then transforming that rules into code but they miss the fact that we code for humans and therefore I couldn’t follow with esay that solution.

The proposal (mine)

the big picture

Aha! not that bad right? but the algorithm starts to complicate from here. Let’s take a look at getMagicSquare function

Get All Magic Squares for 3 x 3

It turns out that for a 3 x 3 matrix, there are just 8 magic squares that can be formed using numbers from 1 to 9.

The rules (3 x 3)

1. The magic constant is 15
2. A magic square always has the number 5 at the very center of it
3. Even numbers should be on the squares.
4. Odd numbers are on the edges.

A detailed explanation about the topic can be found here.

What makes a magic square?

I couldn’t find a suitable way to compute all the varians from even numbers located on the corners’ square that make them a magic a square. But I could compute all the permutations (magic or not magic squares) and then delete the unworthy ones.

Get Distances

I really want to tank Presh Talwalkar for the awesome post he made about the topic.

How Many 3×3 Magic Squares Are There? Sunday Puzzle