Solving the Magic Square Challenge in Python

In this post, I’ll share how I solved the classic "Magic Square" problem using Python. This challenge pushes you to think about matrix transformations, permutations, and cost optimization. If you enjoy puzzles and logic-based problems, you’ll find the magic square a fascinating task!

What Is a Magic Square?

A magic square is a square matrix in which the sums of every row, column, and diagonal are equal. In the case of a 3x3 magic square, the sum for each row, column, and diagonal is called the "magic constant." For a 3x3 matrix filled with unique numbers from 1 to 9, the magic constant turns out to be 15.

The Problem

Given a 3x3 matrix of numbers between 1 and 9, our goal is to convert it into a magic square with minimal "cost." Here, the cost refers to the absolute difference between each original and target matrix element. The task, then, is to find the magic square that can be formed with the smallest total cost.

Solution Outline

The challenge required a couple of major steps:

1. Generating all possible 3x3 magic squares.
2. Calculating the cost to convert the input matrix into each magic square.
3. Returning the minimum cost of these transformations.

Let’s dive into the steps involved in each part of the solution.

Step 1: Generate All Possible 3x3 Magic Squares

To find all possible 3x3 magic squares, we first create all permutations of the numbers 1 to 9. Out of these, only a few will satisfy the properties of a magic square. So, I defined a function to generate and check for these squares.

def get_permutations(arr):
    if len(arr) == 1:
        return [arr]

    perm = []
    for i in range(len(arr)):
        current = arr[i]
        remaining = arr[:i] + arr[i + 1:]
        for p in get_permutations(remaining):
            perm.append([current] + p)
    return perm
        

This recursive function builds all permutations of a list. After generating them, we validate which ones meet the magic square conditions.

Step 2: Check if a Matrix Is a Magic Square

The next task was to identify which of these matrices are actual magic squares. A matrix qualifies as a magic square if:

1. All row sums are the same.
2. All column sums are the same.
3. Both diagonals sum to the same constant.

Here’s the code I used to check these conditions:

def is_magic_square(s):
    lrd = 0  # Sum of the left-to-right diagonal
    rld = 0  # Sum of the right-to-left diagonal
    row_sums = []
    col_sums = []
    row_total = len(s[0])

    for i in range(len(s)):
        lrd += s[i][i]
        rld += s[i][row_total - i - 1]
        row_sums.append(sum(s[i]))
        col_sums.append(sum(s[j][i] for j in range(len(s[i]))))

    # Check if all row sums and column sums are equal and match the diagonals
    if all(x == row_sums[0] for x in row_sums) and all(x == col_sums[0] for x in col_sums):
        if lrd == row_sums[0] and rld == row_sums[0]:
            return True
    return False
        

Step 3: Calculate the Cost of Transformation

With the magic squares generated, we can calculate the cost of converting the input matrix into each valid magic square. This cost is the sum of the absolute differences between corresponding elements in the matrices.

def nearest_match(value, s):
    total_sum = 0
    for j in range(len(s[0])):
        for k in range(len(s[0])):
            diff = abs(value[j][k] - s[j][k])
            total_sum += diff
    return total_sum        

Step 4: Putting It All Together

The formingMagicSquare function brings it all together by generating possible magic squares, calculating transformation costs, and returning the minimum cost.

def formingMagicSquare(s):
    generate_possible_magic_squares(s)
    if len(sum_arr) == 0:
        return 0
    else:
        return sorted(sum_arr)[0]
        

Full Solution Code

Here’s the full code from start to finish:

def formingMagicSquare(s):
    generate_possible_magic_squares(s)
    if len(sum_arr) == 0:
        return 0
    else:
        return sorted(sum_arr)[0]

if __name__ == '__main__':
    s = [[7, 2, 9], [6, 6, 2], [5, 1, 2]]
    result = formingMagicSquare(s)
    print(result)
        

Results and Reflections

I learned a lot while working on this problem. The magic square challenge reinforced the importance of thinking through matrix transformations and cost calculations. If you're interested in matrix transformations or optimization problems, this is a fantastic exercise that teaches you about efficient recursion, matrix validation, and optimization techniques.