# 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: 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)
```

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
```

## Complexity Analysis

• Space Complexity: To maintain the magic square matrix, we require a n*n array. So, the space complexity would be O(n^2).
• Time Complexity: The code that we used to generate magic squares math consists of two loops. The outer loop runs for n times, and the inner loop also runs for n times. Ultimately the time complexity is O(n^2).