How to Solve 3×3 Magic Square Puzzle in C & Python

What is a Magic Square?

A magic square is a square matrix with a special arrangement of numbers. The values are placed so that the sum in every row, every column, and both main diagonals stays the same. Magic squares are simple logic puzzles used in recreational mathematics.

Magic squares example:

The diagram above shows a magic square of order 3. The sum of every diagonal, row, and column equals 15. The next section explains how this constant total is produced.

How Magic Squares Work

A magic square of order n is an n by n matrix containing n² positive integers. The number of rows or columns is called the order of the matrix.

Typical magic square puzzles have an odd order and use the integers from 1 to n². Because every row, column, and diagonal must add up to the same value, that value is called the magic sum or magic constant. The constant depends only on n. The formula for the magic sum of order n is:

Consider a magic square of order 3. The magic sum then is:

This formula explains the arithmetic, but the puzzle has a long cultural history that gives it its memorable name.

Why are They Called Magic?

Ancient mathematicians were fascinated by interesting combinations of numbers, and the magic square was one of them. The earliest evidence dates back to China around 190 BCE.

Studies show evidence of magic square puzzles in ancient Japan, India, and Arabia. Legends linked these arrangements to the magical world, and the name stuck. Beyond folklore, mathematicians have also defined formal categories that distinguish one square from another.

Types of Magic Square

There are several variants of magic squares in mathematics:

• Normal Magic Square: Contains the first n² natural numbers.
• Semi-Magic Square: Only the rows and the columns add up to the magic constant.
• Simple Magic Square: The rows, columns, and both main diagonals add up to the magic constant.
• Most Perfect Magic Square: A normal magic square with two extra properties. Every 2 by 2 sub-square of the matrix adds up to 2(n²+1), and any pair of numbers that are n/2 cells apart sums to n²+1.

More categories exist based on additional properties. Whenever the term “magic square” is used without qualification in this tutorial, it refers to an odd-order, normal, simple magic square.

Algorithm to Generate a Magic Square

The classic algorithm for generating an odd-order magic square, called the Siamese method, is as follows:

• The first number (1) is stored at position (n/2, n-1), where the first coordinate is the row index and the second is the column index. For later steps, call this position (x, y).
• The next number is placed at (x-1, y+1). If that position is invalid, apply the following rules:
  1. If the row index is -1, wrap it to n-1. If the column index is n, wrap it to 0.
  2. If the calculated position already contains a number, increment the row by 1 and decrement the column by 2.
  3. If the row is -1 and the column is n at the same time, the new position is (0, n-2).

Note: This algorithm only generates valid magic squares of odd order. The result is a normal magic square containing the first n² natural numbers. There can be more than one valid solution for the same n.

The rules become clearer through a small example with order 3, which uses the numbers 1 through 9.

How it Works on a 3 by 3 Square

Applying the algorithm above, the steps are:

Step 1) The first number (1) is placed at (3/2, 3-1) or (1, 2). For later steps, set x = 1 and y = 2.

Step 2) The positions of the remaining numbers are calculated as follows.

Position of number 2:

The next number should go to (x-1, y+1) or (0, 3), which is not a valid position. By rule (a), the column wraps to 0, giving (0, 0). Set x = 0, y = 0.

Position of number 3:

Number 3 should be at (x-1, y+1) or (-1, 1), which is not a valid position. By rule (a), the row wraps to n-1 (which is 2). So number 3 goes to (2, 1). Set x = 2, y = 1.

Position of number 4:

Number 4 should be at (x-1, y+1) or (1, 2), which is valid but already contains 1. By rule (b), the new position is (1+1, 2-2) or (2, 0). Set x = 2, y = 0.

Position of number 5:

Number 5 should be at (x-1, y+1) or (1, 1), which is a valid empty position. Set x = 1, y = 1.

Position of number 6:

Number 6 should be at (x-1, y+1) or (0, 2), which is a valid empty position. Set x = 0, y = 2.

Position of number 7:

Number 7 should be at (x-1, y+1) or (-1, 3), which is not valid. By rule (c), the new position is (0, n-2) or (0, 1). Set x = 0, y = 1.

Position of number 8:

Number 8 should be at (x-1, y+1) or (-1, 2), which is not valid. By rule (a), the row wraps to 2, giving (2, 2). Set x = 2, y = 2.

Position of number 9:

Number 9 should be at (x-1, y+1) or (1, 3), which is not valid. By rule (a), the column wraps to 0, giving (1, 0).

With every cell filled, the same logic translates directly into pseudo-code.

Pseudo-code for Magic Square

Begin
    Declare an array of size n*n
    Initialize the array to 0
    Set row = n/2
    Set column = n-1
    For all number i: from 1 to n*n
        If the row = -1 and column = n
            row = 0
            column = n-2
        Else
            If row = -1
                row = n-1
            If column = n
                column = 0
        If the position already contains a number
            decrement column by 2
            increment row by 1
            continue until the position is not 0
        Else
            put the number i into the calculated position
            increment i
        Increment column value
        Decrement row value
End

The pseudo-code maps directly onto compiled and interpreted languages, shown next in C++ and Python.

C++ Code for Magic Square

Input:

/*
A C/C++ program for generating odd order magic squares
*/
#include <bits/stdc++.h>
using namespace std;

void GenerateMagicSquare(int n)
{
    int magic[n][n];
    //initializing the array
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            magic[i][j] = 0;
    //setting row and column value
    int i = n / 2;
    int j = n - 1;
    for (int k = 1; k <= n * n;)
    {
        //checking condition (c)
        if (i == -1 && j == n)
        {
            j = n - 2;
            i = 0;
        }
        else
        {
            //checking condition (a)
            if (j == n)
                j = 0;
            if (i < 0)
                i = n - 1;
        }
        //checking condition (b)
        if (magic[i][j])
        {
            j -= 2;
            i++;
            continue;
        }
        else
        {
            //placing the number into the array
            magic[i][j] = k;
            k++;
        }
        //for the next number setting (i-1, j+1)
        j++;
        i--;
    }
    //printing the matrix
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << magic[i][j] << "  ";
        cout << endl;
    }
}
int main()
{
    //This code works for only odd numbers
    int n = 7;
    cout<<"The magic sum is " << n*(n*n+1)/2 <<endl;
    GenerateMagicSquare(n);
    return 0;
}

Output of Example:

The magic sum is 175

20  12  4  45  37  29  28
11  3  44  36  35  27  19
2  43  42  34  26  18  10
49  41  33  25  17  9  1
40  32  24  16  8  7  48
31  23  15  14  6  47  39
22  21  13  5  46  38  30

The Python version below uses identical row and column rules.

Python Code for Magic Square

def GenerateMagicSquare(n):
    #initializing the array
    magic = [[0 for x in range(n)]
                for y in range(n)]
    #setting row and column value
    i = n // 2
    j = n - 1
    k = 1
    while k <= (n * n):
        #checking condition (c)
        if i == -1 and j == n:
            j = n - 2
            i = 0
        else:
            #checking condition (a)
            if j == n:
                j = 0
            if i < 0:
                i = n - 1
        #checking conditon (b)
        if magic[i][j]:
            j = j - 2
            i = i + 1
            continue
        else:
            #placing the number into the array
            magic[i][j] = k
            k = k + 1
        #for the next number setting (i-1, j+1)
        j = j + 1
        i = i - 1
    #printing the matrix
    for i in range(0, n):
        for j in range(0, n):
            print('%2d ' % (magic[i][j]),end='')
            if j == n - 1:
                print()
#This code works for only odd numbers
n = 7
print("The magic sum is ",n * (n * n + 1) // 2, "\n")
GenerateMagicSquare(n)

Output of Example:

The magic sum is  175

20 12  4 45 37 29 28
11  3 44 36 35 27 19
 2 43 42 34 26 18 10
49 41 33 25 17  9  1
40 32 24 16  8  7 48
31 23 15 14  6 47 39
22 21 13  5 46 38 30

Both implementations behave identically, making it easy to compare their cost.

Complexity Analysis

• Space Complexity: The magic square is stored in an n by n array, so the space complexity is O(n²).
• Time Complexity: The generator uses two nested loops. The outer loop runs n times, and the inner loop also runs n times, so the overall time complexity is O(n²).

FAQs