Forming a Magic Square Algorithm

Howdy fellow programmers! 👋🏽

In this article, I'll be describing how I solved the Forming a Magic Square Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

If this is your first time reading my data structures and algorithms article, please consider reading more in my Algos in Plain English series.😃

Before I get into this challenge, I'll like to state that this one was the most difficult one I solved to date. In fact, I had to get help from the discussion forums on HackerRank because I was unable to figure it out after 2 days.

Problem 🎲

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

You will be given a 3 x 3 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 of |a - b|. Given s, convert it into a magic square at minimal cost. Print this cost on a new line.

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

Example

s = [ [5,3,4], [1,5,8], [6,4,2] ]

The matrix looks like this:

We can convert it to the following magic square:

This took three replacements at a cost of |5-8| + |8-9| + |4-7| = 7

Function Description

Complete the formingMagicSquare function in the editor below.

formingMagicSquare has the following parameter(s):

• int s[3][3]: a 3 x 3 array of integers

Returns

• int: the minimal total cost of converting the input square to a magic square

Input Format

Each of the 3 lines contains three space-separated integers of row s[i].

Sample Input 0:

Sample Output 0:

1

Explanation:

If we change the bottom right value, s[2][2], from 5 to 6 at a cost of |6-5| = 1, s becomes a magic square at the minimum possible cost.

I'll get right into the algorithm. Please feel free to read the full question on HackerRank.

Before we get into the solution, I'd like to explain this challenge a bit.

A Magic Square is a square array of positive numbers (integers) in which the sum of each row, column and both diagonals are the same.

Souce: Wikipedia.

We'll start by stating two observations:

1. The "middle" of any 3x3 magic square must be 5 (I'll explain how below)
2. The "magic sum" must be 15.

We know this because the magic square contains integers in the inclusive range [1, 9]. The sum of these numbers is 45 (1+2+...+8+9). There are 3 rows that will include all 9 numbers summing up to 45, therefore the sum of each row will be 45/3 = 15. 🤓

Now let's think about all possible combinations of the magic square. File_Yanghui_magic_square.GIF

There are 8 valid combinations of 3 numbers (between 1 - 9) that add up to 15:

1. 9 5 1
2. 7 5 3
3. 2 5 8
4. 4 5 6
5. 2 9 4
6. 6 1 8
7. 6 7 2
8. 8 3 4

All 8 of these combinations need to appear in the square as a row, column or diagonal.

The center cell must appear in the middle row, middle column and both diagonals, so it must be a number that appears four times, and the only digit that does is 5. So 5 must be the centre of the matrix.

Similarly, each of the corner digits must form part of a row, a column and a diagonal. Meaning each corner cell must be a digit that appears 3 times. These digits are the even numbers 2, 4, 6, and 8. This means the diagonals must be "2 5 8" and "4 5 6"

What's left are the middle edge cells, each of which needs to appear in one row and one column. These are the remaining numbers 1, 3, 7 and 9. Meaning the middle row and column must be "9 5 1" and "7 5 3".

To get all possible combinations of magic squares, we'll simply take the mirror images (horizontally and vertically) and the rotation of each. (remember the gif above? 🧐).

Mirror images:

Rotated images:

Boy that was a lot, huh...

Now, to replace a number at a position s[i][j] in the magic square, all we have to do is compare it with all possible numbers in this same position from our generated matrices. The cost will be the difference between these two numbers.

Time to code! 👨🏽‍💻

Solution 💡

Unlike my usual approach to algorithms, I'll be approaching this one differently because I was inspired by Dave Guymon's article on Strategically Thinking Through Coding Exercises.

Let's write down the steps we'll use to solve this problem.

# Create a variable called 'all_sqares' to store all 8 combinations of a 3x3 magic square.
# Compare a given magic square combination, 'p' with the function parameter, 's'. Note: s is also a magic square.
# Compare all digits in the rows in p and s, and return their difference in a variable, 'cost'
# Append these 'costs' to a variable, 'total_cost' and return the 'minimum cost'

Let's get to it...

# Create a variable called 'all_sqares' to store all 8 combinations of a 3x3 magic square.

def formingMagicSquare(s):
    # Write your code here
    all_squares = [
        [[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]],
    ]

# Compare a given magic square combination, 'p' with the function parameter, 's'. Note: s is also a magic square.

def formingMagicSquare(s):
    # Write your code here
    all_squares = [
        [[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]],
    ]
    for p in all_squares:
        cost = 0
        for p_row, s_row in zip(p, s):

# Compare all digits in the rows in p and s, and return their difference in a variable, 'cost'

def formingMagicSquare(s):
    # Write your code here
    all_squares = [
        [[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]],
    ]
    for p in all_squares:
        cost = 0
        for p_row, s_row in zip(p, s):
            for i, j in zip(p_row, s_row):
                if not i == j:
                    cost += max([i, j]) - min([i, j])

# Append these 'costs' to a variable, 'total_cost' and return the 'minimum cost'

def formingMagicSquare(s):
    # Write your code here
    total_cost = []
    all_squares = [
        [[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]],
    ]
    for p in all_squares:
        cost = 0
        for p_row, s_row in zip(p, s):
            for i, j in zip(p_row, s_row):
                if not i == j:
                    cost += max([i, j]) - min([i, j])
        total_cost.append(cost)

    return min(total_cost)

Conclusion

This is more or less a brute force approach where we compare each number in s against those in all 8 combinations of the magic square, calculate the cost of replacing them, i.e., the difference between the two, and finally return the smallest cost.

Thanks for reading!

Hope this article helped with understanding this challenge. Happy Coding!👨🏽‍💻