A magic square is an arrangement of numbers in a square grid, where the numbers in each row, and in each column, and the numbers in the forward and backward main diagonals, all add up to the same number.A magic square of order N means it has N rows and N columns.It contains all integers from 1 to N^2.
The constant that is the sum of every row, column and diagonal is called the magic constant or magic sum.Let it be M.
M=[N*(N^2+1)]/2 where N is the order of magic square.
Example-
Magic square of order 3-
2 7 6
9 5 1
4 3 8
M(constant) = [3*(3^2+1)]/2 = 15.
Magic square of order 5-
9 3 22 16 15
2 21 20 14 8
25 19 13 7 1
18 12 6 5 24
11 10 4 23 17
The task is to generate the magic square given its order or number of rows/columns.
Algorithm-
There is a pattern in which the numbers are stored in a magic square.
In any magic square, the first number i.e. 1 is stored at position (N/2, N-1). Let this position be (i,j). The next number is stored at position (i-1, j+1) and the process continues.
Note-
1. If the calculated row position becomes -1, it will be N-1.Similarly,if the calculated column position becomes N, it will be equal to 0.
2. If the magic square already contains a number at the calculated position, calculated column position will be decremented by 2, and calculated row position will be incremented by 1.
3. If the calculated row position is -1 & calculated column position is N, the new position would be: (0, N-2).
Code-
[cpp]
int magicSquare[100][100];
// Initialize position for 1
int i = N/2;
int j = N-1;
// Putting values in magic square
for (int num=1; num <= N*N; )
{
//3rd condition
if (i==-1 && j==N)
{
j = N-2;
i = 0;
}
//1st condition
else
{
if (j == N)
j = 0;
if (i < 0)
i=N-1;
}
//2nd condition
if (magicSquare[i][j])
{
j -= 2;
i++;
continue;
}
else
magicSquare[i][j] = num++; //set number
j++; i–; //normal condition
}
[/cpp]
Note-
This approach works only for odd values of N.
