Magic Square | ODD Order
Last Updated :
19 Oct, 2023
A magic square of order n is an arrangement of n2 numbers, usually distinct integers, in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant. A magic square contains the integers from 1 to n2.
The constant sum in every row, column and diagonal are called the magic constant or magic sum, M. The magic constant of a normal magic square depends only on n and has the following value:
M = n(n2+1)/2
For normal magic squares of order n = 3, 4, 5, ...,
the magic constants are: 15, 34, 65, 111, 175, 260, ...
In this post, we will discuss how programmatically we can generate a magic square of size n. This approach only takes into account odd values of n and doesn’t work for even numbers. Before we go further, consider the below examples:
Magic Square of size 3
-----------------------
2 7 6
9 5 1
4 3 8
Sum in each row & each column = 3*(32+1)/2 = 15
Magic Square of size 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
Sum in each row & each column = 5*(52+1)/2 = 65
Magic Square of size 7
----------------------
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
Sum in each row & each column = 7*(72+1)/2 = 175
Did you find any pattern in which the numbers are stored?
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) where we can consider each row & column as circular array i.e. they wrap around.
Three conditions hold:
- The position of next number is calculated by decrementing row number of the previous number by 1, and incrementing the column number of the previous number by 1. At any time, if the calculated row position becomes -1, it will wrap around to n-1. Similarly, if the calculated column position becomes n, it will wrap around to 0.
- 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.
- If the calculated row position is -1 & calculated column position is n, the new position would be: (0, n-2).
Example:
Magic Square of size 3
----------------------
2 7 6
9 5 1
4 3 8
Steps:
1. position of number 1 = (3/2, 3-1) = (1, 2)
2. position of number 2 = (1-1, 2+1) = (0, 0)
3. position of number 3 = (0-1, 0+1) = (3-1, 1) = (2, 1)
4. position of number 4 = (2-1, 1+1) = (1, 2)
Since, at this position, 1 is there. So, apply condition 2.
new position=(1+1,2-2)=(2,0)
5. position of number 5=(2-1,0+1)=(1,1)
6. position of number 6=(1-1,1+1)=(0,2)
7. position of number 7 = (0-1, 2+1) = (-1,3) // this is tricky, see condition 3
new position = (0, 3-2) = (0,1)
8. position of number 8=(0-1,1+1)=(-1,2)=(2,2) //wrap around
9. position of number 9=(2-1,2+1)=(1,3)=(1,0) //wrap around
Based on the above approach, the following is the working code:
C++
#include <bits/stdc++.h>
using namespace std;
void generateSquare(int n)
{
int magicSquare[n][n];
memset(magicSquare, 0, sizeof(magicSquare));
int i = n / 2;
int j = n - 1;
for (int num = 1; num <= n * n;) {
if (i == -1 && j == n)
{
j = n - 2;
i = 0;
}
else {
if (j == n)
j = 0;
if (i < 0)
i = n - 1;
}
if (magicSquare[i][j])
{
j -= 2;
i++;
continue;
}
else
magicSquare[i][j] = num++;
j++;
i--;
}
cout << "The Magic Square for n=" << n
<< ":\nSum of "
"each row or column "
<< n * (n * n + 1) / 2 << ":\n\n";
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
cout << setw(4) << magicSquare[i][j] << " ";
cout << endl;
}
}
int main()
{
int n = 7;
generateSquare(n);
return 0;
}
|
C
#include <stdio.h>
#include <string.h>
void generateSquare(int n)
{
int magicSquare[n][n];
memset(magicSquare, 0, sizeof(magicSquare));
int i = n / 2;
int j = n - 1;
for (int num = 1; num <= n * n;) {
if (i == -1 && j == n)
{
j = n - 2;
i = 0;
}
else {
if (j == n)
j = 0;
if (i < 0)
i = n - 1;
}
if (magicSquare[i][j])
{
j -= 2;
i++;
continue;
}
else
magicSquare[i][j] = num++;
j++;
i--;
}
printf("The Magic Square for n=%d:\nSum of "
"each row or column %d:\n\n",
n, n * (n * n + 1) / 2);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%3d ", magicSquare[i][j]);
printf("\n");
}
}
int main()
{
int n = 7;
generateSquare(n);
return 0;
}
|
Java
import java.io.*;
class GFG {
static void generateSquare(int n)
{
int[][] magicSquare = new int[n][n];
int i = n / 2;
int j = n - 1;
for (int num = 1; num <= n * n;) {
if (i == -1 && j == n)
{
j = n - 2;
i = 0;
}
else {
if (j == n)
j = 0;
if (i < 0)
i = n - 1;
}
if (magicSquare[i][j] != 0) {
j -= 2;
i++;
continue;
}
else
magicSquare[i][j] = num++;
j++;
i--;
}
System.out.println("The Magic Square for " + n
+ ":");
System.out.println("Sum of each row or column "
+ n * (n * n + 1) / 2 + ":");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
System.out.print(magicSquare[i][j] + " ");
System.out.println();
}
}
public static void main(String[] args)
{
int n = 7;
generateSquare(n);
}
}
|
Python3
def generateSquare(n):
magicSquare = [[0 for x in range(n)]
for y in range(n)]
i = n // 2
j = n - 1
num = 1
while num <= (n * n):
if i == -1 and j == n:
j = n - 2
i = 0
else:
if j == n:
j = 0
if i < 0:
i = n - 1
if magicSquare[int(i)][int(j)]:
j = j - 2
i = i + 1
continue
else:
magicSquare[int(i)][int(j)] = num
num = num + 1
j = j + 1
i = i - 1
print("Magic Square for n =", n)
print("Sum of each row or column",
n * (n * n + 1) // 2, "\n")
for i in range(0, n):
for j in range(0, n):
print('%2d ' % (magicSquare[i][j]),
end='')
if j == n - 1:
print()
n = 7
generateSquare(n)
|
C#
using System;
class GFG {
static void generateSquare(int n)
{
int[, ] magicSquare = new int[n, n];
int i = n / 2;
int j = n - 1;
for (int num = 1; num <= n * n;) {
if (i == -1 && j == n)
{
j = n - 2;
i = 0;
}
else {
if (j == n)
j = 0;
if (i < 0)
i = n - 1;
}
if (magicSquare[i, j] != 0) {
j -= 2;
i++;
continue;
}
else
magicSquare[i, j] = num++;
j++;
i--;
}
Console.WriteLine("The Magic Square for " + n
+ ":");
Console.WriteLine("Sum of each row or column "
+ n * (n * n + 1) / 2 + ":");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
Console.Write(magicSquare[i, j] + " ");
Console.WriteLine();
}
}
public static void Main()
{
int n = 7;
generateSquare(n);
}
}
|
Javascript
<script>
function generateSquare(n)
{
magicSquare = Array(n).fill(0).map(x => Array(n).fill(0));
var i = parseInt(n / 2);
var j = n - 1;
for (num = 1; num <= n * n;) {
if (i == -1 && j == n)
{
j = n - 2;
i = 0;
}
else {
if (j == n)
j = 0;
if (i < 0)
i = n - 1;
}
if (magicSquare[i][j] != 0) {
j -= 2;
i++;
continue;
}
else
magicSquare[i][j] = num++;
j++;
i--;
}
document.write("The Magic Square for " + n
+ ":<br>");
document.write("Sum of each row or column "
+ parseInt(n * (n * n + 1) / 2) + ":<br>");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
document.write(magicSquare[i][j] + " ");
document.write("<br>");
}
}
var n = 7;
generateSquare(n);
</script>
|
PHP
<?php
function generateSquare($n)
{
$magicSquare;
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j < $n; $j++)
$magicSquare[$i][$j] = 0;
$i = (int)$n / 2;
$j = $n - 1;
for ($num = 1; $num <= $n * $n; )
{
if ($i == -1 && $j == $n)
{
$j = $n-2;
$i = 0;
}
else
{
if ($j == $n)
$j = 0;
if ($i < 0)
$i = $n-1;
}
if ($magicSquare[$i][$j])
{
$j -= 2;
$i++;
continue;
}
else
$magicSquare[$i][$j] = $num++;
$j++; $i--;
}
echo "The Magic Square for n = " . $n
. ":\nSum of each row or column "
. $n * ($n * $n + 1) / 2;
echo "\n\n";
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
echo $magicSquare[$i][$j] . " ";
echo "\n";
}
}
$n = 7;
generateSquare ($n);
?>
|
Output
The Magic Square for n=7:
Sum of each row or column 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
Time Complexity: O(n2)
Auxiliary Space: O(n2)
NOTE: This approach works only for odd values of n.
Vedic Mathematics Approach:
This approach is taken from logic given in vedic mathematics. (Very simple to understand)
Note: Only work with ODD values of n.
Approach:
- Start from the cell which is at middle of last column of square.
- Place the number 1.
- Move to the cell which is at top-right position.
- If it is out of square limits then take modulo with n.
- Move to the cell which comes after taking modulo.
- When we reach multiple of n, move to the left cell.
- If it is out of square limits then take modulo with n.
- Put the next number and repeat the above steps.
Working code:
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 7;
vector<vector<int>> magicSquare(n, vector<int>(n, -1));
int x = (n / 2), y = n - 1;
for(int i=1; i<=n*n; i++) {
magicSquare[x][y] = i;
if(i % n == 0) {
y--;
} else {
x--; y++;
}
x += n; x %= n;
y += n; y %= n;
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cout<< magicSquare[i][j]<< " ";
}
cout<< endl;
}
return 0;
}
|
Java
import java.util.Arrays;
public class GFG {
public static void main(String[] args) {
int n = 7;
int[][] magicSquare = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(magicSquare[i], -1);
}
int x = n / 2, y = n - 1;
for (int i = 1; i <= n * n; i++) {
magicSquare[x][y] = i;
if (i % n == 0) {
y--;
} else {
x--; y++;
}
x = (x + n) % n;
y = (y + n) % n;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(magicSquare[i][j] + " ");
}
System.out.println();
}
}
}
|
Python
n = 7
magicSquare = [[-1 for _ in range(n)] for _ in range(n)]
x, y = n / 2, n - 1
for i in range(1, n * n + 1):
magicSquare[x][y] = i
if i % n == 0:
y -= 1
else:
x -= 1
y += 1
x = (x + n) % n
y = (y + n) % n
for i in range(n):
for j in range(n):
print magicSquare[i][j],
print
|
C#
using System;
class Program {
static void Main()
{
int n = 7;
int[, ] magicSquare = new int[n, n];
int x = (n / 2), y = n - 1;
for (int i = 1; i <= n * n; i++) {
magicSquare[x, y] = i;
if (i % n == 0) {
y--;
}
else {
x--;
y++;
}
x = (x + n) % n;
y = (y + n) % n;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Console.Write(magicSquare[i, j] + " ");
}
Console.WriteLine();
}
}
}
|
Javascript
function generateMagicSquare(n) {
const magicSquare = new Array(n).fill(0).map(() => new Array(n).fill(0));
let x = Math.floor(n / 2);
let y = n - 1;
for (let i = 1; i <= n * n; i++) {
magicSquare[x][y] = i;
if (i % n === 0) {
y--;
} else {
x--;
y++;
}
x = (x + n) % n;
y = (y + n) % n;
}
return magicSquare;
}
function printMagicSquare(magicSquare) {
for (let i = 0; i < magicSquare.length; i++) {
console.log(magicSquare[i].join(' '));
}
}
const n = 7;
const magicSquare = generateMagicSquare(n);
printMagicSquare(magicSquare);
|
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Output:
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
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...