Hi forsight-ga,
I adapted the implementation on codeproject.com to use dynamic arrays instead.
Below are 2 versions of a Magic Square generator. The first is a
simple version, which only generates magic squares for odd square
sizes using an optimized algorithm. The second can generate squares
for both odd and even square sizes.
A screenshot can be found on http://www.codeproject.com/cpp/Magic_Square.asp
(or if the site is down, you can find a cached copy on
http://66.102.11.104/search?q=cache:http://www.codeproject.com/cpp/Magic_Square.asp)
////////// SIMPLE VERSION /////////
#include <iostream>
#include <iomanip>
using namespace std;
int ReadSquareSize()
{
int x;
cout<<"Enter a positive odd integer square size of 3 or more: ";
while(1)
{
cin>>x;
if(x>=3 && x%2==1)
{
return x;
}
else
{
cout<<"Enter a positive odd integer square size of 3 or more: ";
}
}
cout<<endl;
}
int main()
{
int k,g;
int unit;
int row,col,newRow,newCol;
int n = ReadSquareSize();
int square[n][n];
for(k=0 ; k<n ; k++) {
for(g=0 ; g<n ; g++) {
square[k][g] = 0;
}
}
unit= 1;
row= 1;
col= (n+1)/2;
k= 1;
square[row-1][col-1]=k;
for(k=2 ; k<=n*n ; k++)
{
newRow= row - 1;
newCol= col + 1;
if (newRow==0 && newCol==(n+1))
{
newRow = row + 1;
newCol = n;
row = newRow;
col = newCol;
square[row-1][col-1]=k;
}
else
{
if(newRow==0)
{
newRow= n;
}
if(newCol==(n+1))
{
newCol= 1;
}
if(square [newRow-1][newCol-1]==0)
{
row=newRow;
col=newCol;
square[row-1][col-1]=k;
}
else
{
newRow= row + 1;
newCol= col;
if(newRow==(n+1))
{
newRow= 1;
}
row= newRow;
col= newCol;
square[row-1][col-1]=k;
}
}
}
// print and free the square
for(int i=0; i<n ;i++)
{
for(int j=0; j<n ; j++)
{
cout<<setiosflags(ios::left) << setw (5) << square[i][j];
}
cout<<endl;
delete[] square[i];
}
free(square);
return 0;
}
////////// ENHANCED VERSION /////////
#include <iostream>
#include <iomanip>
using namespace std;
int ReadSquareSize();
void OddMagicSquare(int** matrix, int n);
void DoublyEvenMagicSquare(int** matrix, int n);
void SinglyEvenMagicSquare(int** matrix, int n);
void MagicSquare(int** matrix, int n);
int** CreateMatrix(int n);
void FreeMatrix(int** matrix, int n);
int main(int argc, char* argv[])
{
int i,n;
n = ReadSquareSize();
int** matrix = CreateMatrix(n);
MagicSquare(matrix, n);
// print the square
for(int i=0; i<n ;i++)
{
for(int j=0; j<n ; j++)
{
cout<<setiosflags(ios::left) << setw (5) << matrix[i][j];
}
cout<<endl;
}
FreeMatrix(matrix,n);
return 0;
}
int ReadSquareSize()
{
int x;
cout<<"Enter a positive integer square size of 3 or more: ";
while(1)
{
cin>>x;
if(x>=3)
{
return x;
}
else
{
cout<<"Enter a positive integer square size of 3 or more: ";
}
}
cout<<endl;
}
void MagicSquare(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(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(int** matrix, int n)
{
int i, j;
int** I = CreateMatrix(n);
int** J = CreateMatrix(n);
//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];
}
FreeMatrix(I,n);
FreeMatrix(J,n);
}
void SinglyEvenMagicSquare(int** matrix, int n)
{
int i, j, k, index=0;
int p=n/2;
int** M = CreateMatrix(p);
MagicSquare(M, p);
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;
int* I = new int[p];
int* J = new int[n];
for (i=0; i<p; i++)
I[i]=i+1;
k=(n-2)/4;
for (i=1; i<=k; i++)
J[index++] = i;
for (i=n-k+2; i<=n; i++)
J[index++] = i;
int temp;
for (i=1; i<=p; i++)
for (j=1; j<=index; 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;
FreeMatrix(M,p);
delete[] I;
delete[] J;
}
int** CreateMatrix(int n)
{
int i;
int** matrix = new int* [n];
for(i=0;i<n;i++)
{
matrix[i] = new int[n];
}
return matrix;
}
void FreeMatrix(int** matrix, int n)
{
for(int i=0; i<n ;i++)
{
delete[] matrix[i];
}
free(matrix);
}
/////////////////// END CODE ////////////////
I've tested both versions on my system and they work perfectly.
The algorithms used for both odd and even size magic square creation
are described here:
http://rec-puzzles.org/new/sol.pl/arithmetic/magic.squares
Sincerely,
rhansenne-ga.
Search terms used: "C++" "magic square" |
