Magic Square – Solve 3×3 Puzzle using C & Python Examples

What is Magic Square?

A Magic square is a square matrix with a special number arrangement. These numbers are arranged so that the sum of the numbers on each diagonal, row, and the column remains the same. Magic squares games are simple logic puzzles used in recreational mathematics.

Magic squares example:

$Magic Square$

Above given diagram is an example of a magic square of order 3. The sum of each diagonal, row, and column is 15.

How Magic Square works

Magic squares are n*n matrices consisting of n^2 positive integers. The number of rows or columns of a square matrix is called the order of the matrix.

Typically, magic squares puzzles have odd orders and bear the integers from 1 to n^2. The sum of each diagonal, row, and column is the same. This number is called magic sum or magic constant. Generally, this magic sum depends on the order of the matrix. The magic squares formula for the magic sum of order n is-

Let’s take an example of a magic square with integers 3. So, the magic sum would be-

Why are they called Magic?

Ancient mathematicians were fascinated by the nature of several interesting combinations of numbers. The magic square was one of them. The earliest evidence of magic squares dates back to China in 190 BCE.

Some studies show evidence of the Magic squares puzzle in ancient Japan, India, and Arabia. Based on some legends, it was assumed that those special formations of numbers were connected to the magical world. Hence, those squares were named magic squares.

Types of Magic Square

There are different variants of magic squares mathematics –

Normal Magic Square: This type of magic square contains the first n^2 numbers.
Semi-Magic Square: In this type, only the rows and the column sum up to the magic constant.
Simple Magic Square: In contrast to the previous type, the rows, columns, and both diagonals sum up to the magic constant.
Most Perfect Magic Square: This is a normal magic square with two special properties. Here, each 2 by 2 sub square of the matrix adds up to a total of 2(n^2+1). And any pair of numbers that are n/2 squares apart from the grid sum to n^2+1.

Based on properties, there are many more types of magic squares. But whenever we just mention the magic square, we assume it is an odd-order normal and simple magic square.

Algorithm to Generate Magic Square

The algorithm for generating odd-order magic squares is:

The first number or 1 will be stored at (n/2, n-1), where the first coordinate is the row position, and the second coordinate is the column position. For later steps, let’s denote this position as (x, y).
The next numbers will be stored at (x-1, y+1). If the position is not valid, then we’ll consider the following conditions.
1. If the row position is -1, it will warp to n-1. Similarly, if the calculated column position is n, it will warp to 0.
2. The row position will be incremented by 1, and the column position will be decremented by 2 if the calculated position already contains a number.
3. If the row position is -1 and the corresponding column position is n, the new position will be (0, n-2.

Note: This algorithm only generates valid magic squares of odd order. We also consider this magic square a normal magic square with the first n^2 numbers. Moreover, there can be multiple solutions for the same value of n.

Let’s take an example and see how it works. Let’s say we want to find the magic square of order 3. As it will be a simple and normal magic square of odd order, it will contain all the numbers from 1 to 3^2 or 9.

How it works?

According to our algorithm, the steps will be the following:

Step 1) The first number or 1 will be at the (3/2, 3-1) or (1, 2) position. By convention, consider x= 1 and y= 2 for later steps.

Step 2) The position for the rest of the numbers will be calculated in the following manner-

Position of number 2:

The next number will be at (x-1, y+1) or (0, 3), which is not a valid position. By using condition (a), the corresponding valid position would be (0,0). So, x= 0, y= 0.

Position of number 3:

Number 3 will be at (x-1, y+1) or (-1, 1), which is not a valid position. By using condition (a), the valid row position would be n-1 or 2. So, number 3 will be at (2, 1). For the next number, x= 2, y= 1.

Position of number 4:

Number 4 should be at (x-1, y+1) or (1, 2) which is a valid position. But that position already contains a number. According to condition (b), the valid position would be (1+1, 2-2) or (2,0). For the next number x= 2, y= 0.

Position of number 5:

Number 5 should be at (x-1, y+1) or (1, 1) which is a valid position. For the next number x= 1, y= 1.

Position of number 6:

Number 6 should be at (x-1, y+1) or (0, 2) which is a valid position. For the next number x= 0, y= 2.

Position of number 7:

Number 7 should be at (x-1, y+1) or (-1, 3) which is not a valid position. According to condition (c), the valid position would be (0, n-2) or (0, 1). For the next number x= 0, y= 1.

Position of number 8:

Number 8 should be at (x-1, y+1) or (-1, 2) which is not a valid position. By using condition (a), the valid position would be (2, 2). For the next number x= 2, y= 2.

Position of number 9:

Number 9 should be at (x-1, y+1) or (1, 3) which is not a valid position. By using condition (a), the valid position would be (1, 0).

Pseudo-code

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

C++ Code 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

Python Code 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)