12,551,373 members (53,815 online)
alternative version

294.2K views
36 bookmarked
Posted

Magic Square

, 8 Sep 2003
 Rate this:
Calculating Magic Square In Any Order Using Standard Template Library (STL)
<!-- Article image -->

Introduction

Magic square is an ancient mathematical problem that many people try to solve. May be you see it in some magazines or your teacher might have introduced it in a class.

Details

A magic square is an arrangement of numbers from 1 to n2 in an [n x n] matrix, with each number occurring exactly once, and such that the sum of the entries of any row, any column, or any main diagonal is the same.

It is not hard to show that this sum must be  n [ ( n2 + 1) / 2 ]. If we use this formula for that example output which is below, for [5x5] matrix; `5 [ ( 52 + 1 ) / 2 ] = 65`.

 17 24 1 8 15 65 23 5 7 14 16 65 4 6 13 20 22 65 10 12 19 21 3 65 11 18 25 2 9 65 65 65 65 65 65 65

Now, I want to show you a way to calculating magic squares in any order by using your talented computer.

Siamese method

This method is useful for calculating magic squares with odd order. It begins by placing a 1 in any location (in the center square of the top row in the above example), then incrementally placing subsequent numbers in the square one unit above and to the right. The counting is wrapped around, so that falling off the top returns on the bottom and falling off the right returns on the left. When a square is encountered which is already filled, the next number is instead placed below the previous one and the method continues as before. The method, also called de la Loubere's method.

For example, if order of square is 5, we have:

```void CalculateOddMagicSquare()
{
n=5;
int matrix[5][5];

int nsqr = n * n;
int i=0, j=n/2;     // start position

for (int k=1; k<=nsqr; ++k)
{
matrix[i][j] = k;

i--;
j++;

if (k%n == 0)
{
i += 2;
--j;
}
else
{
if (j==n)
j -= n;
else if (i<0)
i += n;
}
}
}```

Here is a very nice flash animation to show you how to fill square's cells. Thanks KIVANÇ HiKMET ANAR, for his flash.

Complete Work

Below is full source code of calculating magic squares in any order.

```#include "stdafx.h"
#include <vector>

using namespace std;

void OddMagicSquare(vector<vector<int> > &matrix, int n);
void DoublyEvenMagicSquare(vector<vector<int> > &matrix, int n);
void SinglyEvenMagicSquare(vector<vector<int> > &matrix, int n);
void MagicSquare(vector<vector<int> > &matrix, int n);
void PrintMagicSquare(vector<vector<int> > &matrix, int n);

int main(int argc, char* argv[])
{
int n;
printf("Enter order of square: ");
scanf("%d", &n);

vector<vector<int> > matrix(n, vector<int> (n, 0));

if (n<3)
{
printf("\nError: n must be greater than 2\n\n");
return -1;
}

MagicSquare(matrix, n);

//Print results
PrintMagicSquare(matrix, n);

return 0;
}

void MagicSquare(vector<vector<int> > &matrix,int n)
{
if (n%2==1)        //n is Odd
OddMagicSquare(matrix, n);
else          //n is even
if (n%4==0)    //doubly even order
DoublyEvenMagicSquare(matrix, n);
else      //singly even order
SinglyEvenMagicSquare(matrix, n);
}

void OddMagicSquare(vector<vector<int> > &matrix, int n)
{
int nsqr = n * n;
int i=0, j=n/2;     // start position

for (int k=1; k<=nsqr; ++k)
{
matrix[i][j] = k;

i--;
j++;

if (k%n == 0)
{
i += 2;
--j;
}
else
{
if (j==n)
j -= n;
else if (i<0)
i += n;
}
}
}

void DoublyEvenMagicSquare(vector<vector<int> > &matrix, int n)
{
vector<vector<int> > I(n, vector<int> (n, 0));
vector<vector<int> > J(n, vector<int> (n, 0));

int i, j;

//prepare I, J
int index=1;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
I[i][j]=((i+1)%4)/2;
J[j][i]=((i+1)%4)/2;
matrix[i][j]=index;
index++;
}

for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
if (I[i][j]==J[i][j])
matrix[i][j]=n*n+1-matrix[i][j];
}
}

void SinglyEvenMagicSquare(vector<vector<int> > &matrix, int n)
{
int p=n/2;

vector<vector<int> > M(p, vector<int> (p, 0));
MagicSquare(M, p);

int i, j, k;

for (i=0; i<p; i++)
for (j=0; j<p; j++)
{
matrix[i][j]=M[i][j];
matrix[i+p][j]=M[i][j]+3*p*p;
matrix[i][j+p]=M[i][j]+2*p*p;
matrix[i+p][j+p]=M[i][j]+p*p;
}

if (n==2)
return;

vector<int> I(p, 0);
vector<int> J;

for (i=0; i<p; i++)
I[i]=i+1;

k=(n-2)/4;

for (i=1; i<=k; i++)
J.push_back(i);

for (i=n-k+2; i<=n; i++)
J.push_back(i);

int temp;
for (i=1; i<=p; i++)
for (j=1; j<=J.size(); j++)
{
temp=matrix[i-1][J[j-1]-1];
matrix[i-1][J[j-1]-1]=matrix[i+p-1][J[j-1]-1];
matrix[i+p-1][J[j-1]-1]=temp;
}

//j=1, i
//i=k+1, k+1+p
i=k;
j=0;
temp=matrix[i][j]; matrix[i][j]=matrix[i+p][j]; matrix[i+p][j]=temp;

j=i;
temp=matrix[i+p][j]; matrix[i+p][j]=matrix[i][j]; matrix[i][j]=temp;
}

void PrintMagicSquare(vector<vector<int> > &matrix, int n)
{
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
printf(" %3d", matrix[i][j]);

printf("\n");
}

printf("\n\n");
}```

Conclusion

Enjoy!

A list of licenses authors might use can be found here

Share

 CEO Misbah3Com Iran (Islamic Republic of)
I was born in Shiraz, a very beautiful famous city in Iran. I started programming when I was 12 years old with GWBASIC. Since now, I worked with various programming languages from Basic, Foxpro, C/C++, Visual Basic, Pascal to MATLAB and now Visual C++.
I graduated from Iran University of Science & Technology in Communication Eng., and now work as a system programmer for a telecommunication industry.
I wrote several programs and drivers for Synthesizers, Power Amplifiers, GPIB, GPS devices, Radio cards, Data Acqusition cards and so many related devices.
I'm author of several books like Learning C (primary and advanced), Learning Visual Basic, API application for VB, Teach Yourself Object Oriented Programming (OOP) and etc.
I'm winner of January, May, August 2003 and April 2005 best article of month competetion, my articles are:

You can see list of my articles, by clicking here

You may also be interested in...

 First Prev Next
 What's wrong with my Magic Square program? Trevon Harris21-Feb-15 20:25 Trevon Harris 21-Feb-15 20:25
 thank you...... aravindanne24-Jan-12 5:24 aravindanne 24-Jan-12 5:24
 a more general algorithm for generating magic squares ashishkumar3666-Nov-11 12:15 ashishkumar366 6-Nov-11 12:15
 program of magic square Member 820125830-Aug-11 15:58 Member 8201258 30-Aug-11 15:58
 magic square program sheila mejos30-Aug-11 15:09 sheila mejos 30-Aug-11 15:09
 domino problem SOLR@C21-May-11 15:59 SOLR@C 21-May-11 15:59
 help me mashmal11-Apr-11 11:47 mashmal 11-Apr-11 11:47
 help me please to expand my knowledge in programming.. nycshoes0317-Jul-09 17:12 nycshoes03 17-Jul-09 17:12
 magic square samantha0315-Jul-09 19:56 samantha03 15-Jul-09 19:56
 help me plzz dongky19864-Feb-09 1:41 dongky1986 4-Feb-09 1:41
 Can anyone give me a blue jay array source code about magic square with a A. method createArithmetic B. method matricize C. method reverseDiagonal D. method magicCheck E. method printMatrix The method written in parts A through E should be general enough to apply to an array of any size. Anyone knows about this, plzz.. share it with me.. e mail me at mr.dongky@hotmail.com
 problem Member 47188233-Sep-08 8:54 Member 4718823 3-Sep-08 8:54
 Help_Magic Square 00713-Jan-08 4:45 007 13-Jan-08 4:45
 Can anyone help with this program [modified] Well Alright 200411-Jun-07 14:14 Well Alright 2004 11-Jun-07 14:14
 Solvin a Magic Saquare in other method Nizar Hawat6-Jan-07 11:45 Nizar Hawat 6-Jan-07 11:45
 HeLP me to solve this probLem, pLease! winche9-May-06 2:12 winche 9-May-06 2:12
 help Shay00730-Mar-06 19:55 Shay007 30-Mar-06 19:55
 Magic Square Flaw bugDanny26-Sep-05 3:56 bugDanny 26-Sep-05 3:56
 Re: Magic Square Flaw A. Riazi26-Sep-05 4:10 A. Riazi 26-Sep-05 4:10
 Re: Magic Square Flaw bugDanny26-Sep-05 4:18 bugDanny 26-Sep-05 4:18
 hi prof Anonymous24-Sep-05 17:24 Anonymous 24-Sep-05 17:24
 Complete Distributed Solution MagicSquareJoe22-Jul-04 17:22 MagicSquareJoe 22-Jul-04 17:22
 Your Complete Work Anonymous15-Nov-03 14:55 Anonymous 15-Nov-03 14:55
 Re: Your Complete Work Anthony_Yio21-Dec-03 21:32 Anthony_Yio 21-Dec-03 21:32
 Re: Your Complete Work Giles13-Sep-04 2:53 Giles 13-Sep-04 2:53
 Re: Your Complete Work Anonymous18-Sep-04 14:49 Anonymous 18-Sep-04 14:49
 Could you explain this line? WREY10-Sep-03 13:33 WREY 10-Sep-03 13:33
 Re: Could you explain this line? Anonymously10-Sep-03 15:43 Anonymously 10-Sep-03 15:43
 Re: Could you explain this line? John A. Johnson10-Sep-03 20:36 John A. Johnson 10-Sep-03 20:36
 Re: Could you explain this line? WREY10-Sep-03 22:46 WREY 10-Sep-03 22:46
 Re: Could you explain this line? A. Riazi11-Sep-03 0:03 A. Riazi 11-Sep-03 0:03
 Re: Could you explain this line? John A. Johnson11-Sep-03 2:48 John A. Johnson 11-Sep-03 2:48
 Re: Could you explain this line? A. Riazi11-Sep-03 4:38 A. Riazi 11-Sep-03 4:38
 Re: Could you explain this line? John A. Johnson11-Sep-03 5:47 John A. Johnson 11-Sep-03 5:47
 Re: Could you explain this line? A. Riazi12-Sep-03 19:45 A. Riazi 12-Sep-03 19:45
 Very interesting article, but... Kacee Giger10-Sep-03 6:56 Kacee Giger 10-Sep-03 6:56
 Re: Very interesting article, but... Kacee Giger10-Sep-03 7:32 Kacee Giger 10-Sep-03 7:32
 Re: Very interesting article, but... Paolo Messina10-Sep-03 12:05 Paolo Messina 10-Sep-03 12:05
 Re: Very interesting article, but... Mister Transistor15-Sep-03 22:56 Mister Transistor 15-Sep-03 22:56
 Re: Very interesting article, but... A. Riazi15-Sep-03 23:37 A. Riazi 15-Sep-03 23:37
 I would love to have your program 20 years ago... John A. Johnson9-Sep-03 10:17 John A. Johnson 9-Sep-03 10:17
 Re: I would love to have your program 20 years ago... A. Riazi9-Sep-03 19:07 A. Riazi 9-Sep-03 19:07
 Re: I would love to have your program 20 years ago... WREY10-Sep-03 11:58 WREY 10-Sep-03 11:58
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Oct-16 23:21 Refresh 1