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
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.
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)
Here the definition from HackerRank
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)
Aha! not that bad right? but the algorithm starts to complicate from here. Let’s take a look at getMagicSquare function
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)
- The magic constant is 15
- A magic square always has the number 5 at the very center of it
- Even numbers should be on the squares.
- Odd numbers are on the edges.
A detailed explanation about the topic can be found here.
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.
I really want to tank Presh Talwalkar for the awesome post he made about the topic.