• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1483
  • Last Modified:

Magic Square

Hi, I have a program on magic square. I could check the rows.
To check the coloms and the diagonals it will be done only after all the rows are filled.
 If after filling the rows the columns and diagonals are not name number how should I come back and do again.
My program is given below. For some functions the parameters are not fully filled. Take it easy I will do it later on. I want you to guide me how to proceed. More over this is recursive as I have to submit it recursive.

/////////////////////////////////////////Magic square program///////////////////////////////////////////////

#include<stdio.h>
#include<stdlib.h>


#define MAGIC_SQUARE_SUM  15

void permute(int,int,int);
int cal_col_pts(int,int);
int rowsum(int[],int);
int colsum(int[],int,int);
void displayrow(int[],int);
int testmagic(int[],int,int,int);
int A[9],B[9];

void main(void)
{
      int n,x=1,num=0,slots=0,point;

      printf("Enter a number");
      scanf("%d",&n);
      printf("Enter the size of the square( 3*3,4*4, 5*5...) ");
      scanf("%d",&num);
      slots=num*num;
      point=cal_col_pts(slots,num);
      permute(n,point,num);
}

int cal_col_pts(int slots,int num)
{
      int x=slots/num;
      x--;
      num*=x;
      return num+1;
}

void permute(int n,int pts,int num)
{
      int i,temp=0;
      
    for (i = 1;i<=9;i++)
      {
        if( B[i]==0)     // if i is free
        {
            B[i]=1;
            A[n]=i;    
                  
            if ((n % 3) == 0) // if n is div by 3
            {
                if ( (temp=rowsum(A,i)) == 15 )
                {
                              
                    if( n<9 )
                        permute(n+1,pts,num);    
                    else   // at the end
                                testmagic(A,i,pts,num);
                        
                }
            }
            else
                permute(n+1); //recurse
                  B[i]=0;
        }
      }
}

int testmagic(int A[],int i,int pts,int num)
{
      int flag1=0,flag2=0,flag3=0;
      columnsum(A,max,pts);
      diagonalsum();
      reverse_diagonaldum();
}

diagonalsum()
{
      for(i=0;i<max;i=num+i+1)
      {
            sum+=A[i];
            if(i==pts && (sum!=MAGIC_SQUARE_SUM)
                  break;
            else
                  continue;
      }
}

reverse_diagonal_sum()
{
      int sum=0;
      for(i=pts;i<=ptsnum;i=i%n)
      {
            sum+=A[i];
            if(sum==MAGIC_SQUARE_SUM)
                  return flag-1;
            int flag=0;
      
}


int rowsum(int A[],int i)
{
      int x=0,flag=0,temp=0;
      for(temp=1;temp<=i;temp++)
      {
            x+=A[temp];
            if(temp%3 ==0)
            {
                  if(x==15)
                        continue;
                  else
                      return flag;
            }
      }
      return (flag=1);
}

columnsum(int A[],int max,int pts,int num)
{
      int i=0,j=0,sum=0,flag=0;
      
      for(;i<max;i+=num)
      {
            sum+=A[j];
            if(sum==MAGIC_SQUARE_SUM)
            {
                  j++;
                  i=j;
                  if(j>num)
                  {
                        return flag=1;      
                  }
            }
            else
                  return flag=0;
            
      }
}

void displayrow(int A[],int i)
{
      int temp=i/3;
      int j=0;
      for(j=0;j<i;j++)
      {
            printf("%d",A[j]);
            if((j%3)==0)
                  printf("\n");
      }
}
0
rmvprasad
Asked:
rmvprasad
  • 4
  • 3
  • 2
  • +1
1 Solution
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi rmvprasad,

You need a recursive solution.

Consider a 3x3 square that will contain the digits 1 through 9.  (You can also use 0 through 8 or any other combination of digits that you want.)

The easiest implementation is to use a buffer of N*N elements.  In this case 3*3=9 so a buffer of 9 integers will suffice.

Now place the 9 digits into the buffer in any order that you want.  (Sequentially is a good start because it makes for easy debugging.)

This array looks like:

Array[0] == 1;
Array[1] == 2;
Array[2] == 3;
Array[3] == 4;
...
Array[8] == 9;

Test the array.  You'll have to implement two dimensions overlayed on top of the array.  If the array is a magic square, print it.

If not, swap that last two digits.  The array now contains 1 2 3 4 5 6 7 9 8.

Text the array.  If the array is a magic square, print it.

If not, swap the next two digits.  The array now contains 1 2 3 4 5 6 7 8 9.

etc..

You really need a recursive function to manage the position within the array and to perform the swapping.


Good Luck!
Kent
0
 
Amritpal SinghCommented:
following is an alternate sol. plz try it

Assign the numbers in the order 1,2,3... in the matrix in the following pattern.


Put the first number (1) as the middle element in the first row (Let it be i,j).

 

Put the next element in the diagonally previous (i-1,j-1) location, if the location is empty.

 

The rows and columns are considered to be circular, i.e. if i-1 or j-1 comes to a negative value, then highest row or column is taken.

 

If the location is not empty then put the number in the next row, in the same column(i+1,j), here , rows are considered to be circular.

 

Continue assigning numbers in this pattern until the matrix is filled (ie n * n times ) */

 

#include<stdio.h>
#define N 10 //Defines the maximum size of the matrix

void main( )
{

int a[N][N]={{0}},i,j,k,n,s,p; //Declaring and initialising the variables

 

label:

clrscr( );
printf("Enter the size : "); //Reading the size
scanf("%d",&n);


if((n%2==0)||(n>N)) //Validating the input size
{

printf("\n\nThe size must be even and less than %d :Try again\n\n",N);
printf("Press any key to continue ........\n");
getch();
goto label;

}


j=0;
k=n/2;

 

//Generating the Magic square
for(i=1;i<=n*n;i++)
{

a[j][k]=i;
s=j-1;
p=k-1;


if(s<0)

s=n-1;

if(p<0)

p=n-1;


if(a[s][p]!=0)

j++;

else

{

j=s;
k=p;

}

}

 

printf("\nThe Magic square is \n\n");
for(i=0;i<n;i++) //Displaying the result
{

for(j=0;j<n;j++)

printf(" %2d ",a[i][j]);

printf("\n");

}

getch( );

}
0
 
PaulCaswellCommented:
rmvprasad,

There are quite a few concerns about your code. I suspect that you have skipped one of the most important stages of software design, that of planning. You have made some progress in deciding how to add up the rows and columns etc but if you step back and think about it there may be a better way to go.

You are correct that there are two main parts to this, first to permute the square and second to detect a solution. The permutation will enumerate all possible layouts of the square, once each is complete the detection function must be called and, if it signals correctness, the square must be printed.

Lets see this in code fragments.

Here's one that is almost guaranteed to appear in some form:

// If the layout is full and correct then print it.
if ( complete () && correct () ) printlayout ();

This will be somewhere in your permute logic:

void permute ()
{
     ...
     if ( complete () && correct () ) printlayout ();
     ...
}

The permute logic must scan for empty slots and fill them with unused numbers:

void permute ()
{
  int x, y;
  // Scan the board for a gap.
  for ( x = 0; x < n; x++ )
  {
    for ( y = 0; y < n; y++ )
    {
     // Empty?
     if ( layout[x][y] == 0 )
     {
     // Add another number.
     ...
     if ( complete () && correct () ) printlayout ();
     ...
      }
    }
  }
}

Do you see where I am going? Let the code define the data structures! Already, we have decided that a zero entry in the layout means that there is no number there. We also want to access the layout as 'layout[x][y]' so you ought to use the standard 2d array techniques.

Sorry to seem to suggest that you should start over from scratch but that is sometimes one of the questions a proffesional must ask.

If you want to continue with the code you've got, get it to compile without error or warning and repost it. We can then make suggestions on fixing the problems.

Paul
0
Improve Your Query Performance Tuning

In this FREE six-day email course, you'll learn from Janis Griffin, Database Performance Evangelist. She'll teach 12 steps that you can use to optimize your queries as much as possible and see measurable results in your work. Get started today!

 
Kent OlsenData Warehouse Architect / DBACommented:
Hi Paul,

Good observations.

One can (and probably should) actually build a magic cube by defining the underlying mathematics and solving the resultant equations.  The easiest way is to "hard code" the solution for a 3*3 cube, and then turn it into a general purpose solution.

[sidebar]
Solving as amrit suggests is easiest with two solutions.  One for odd N (with a center square) and one for even N (with a center quad).
[/sizebar]

Solving for N=3 can actually be kind of fun.  I'll lay it out.

Let's define the cube by assigning the letters 'A' through 'I'.

  A B C
  D E F
  G H I

The math is as follows.  We have a magic cube iff:

 A + B + C = D + E + F = G + H + I = A + D + G = B + E + H = C + F + I = A + E + I = C + E + G

Whew.  (But we knew that.)

So we define the controls as:

int Table[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int *A, *B, *C, *D, *E, *F, *G, *H, *I;

The "Table" is simply initialized with the digits that we're going to used.  This can be any order that we choose.

In the program setup, we equate our letters to the positions in the table:

main ()
{
...
  A = Table;
  B = A + 1;
  C = B + 1;
  D = C + 1;
  E = D + 1;
  F = E + 1;
  G = F + 1;
  H = G + 1;
  I  = H + 1;
...

We now call our recursive function that generates all possible orders of 9 numbers.  Whenever it completes a restructuring, we test for a solution:

int IsMagicSquare (void)
{
  if (*A + *B + *C != *D + *E + *F)
    return 0;
  if (*A + *B + *C != *G + *H + *I)
    return 0;
  if (*A + *B + *C != *A + *D + *G)  /*  reduces to B + C != D + G  */
    return 0;
  if (*A + *B + *C != *B + *E + *H)  /*  reduces, etc...  */
    return 0;
  if (*A + *B + *C != *C + *F + *I)
    return 0;
  if (*A + *B + *C != *A + *E + *I)
    return 0;
  if (*A + *B + *C != *C + *E + *G)
    return 0;
  return 1;
}

The result is that our code actually looks like it's trying to solve the same problem that we are.  (Of course, one could always use macros to #define A as Table[0], too.)  Having now completed the program, it's pretty easy to convert it to a general purpose solution.


Kent
0
 
PaulCaswellCommented:
Kent,

Nice description.

I am being a bit cagey about too much source at this stage as it is difficult to see if this is homework or not. I would have thought that if it was just an experiment then rmvprasad would have made more effort to at least get it to compile. As it is there are many places where there would at least be warnings if not downright errors. In view of this I was guiding rmvprasad towards a clear understanding of what is wanted, how to solve it. I was delaying techniques until next stage.

The techniques needed here will probably be some or all or more of:

1. Clear algorithm. You've done that.
2. 2d memory allocation methods (int ***).
3. Recursive space-filling.
4. Algorithmic optimisation (optimise the check process, not the fill process).
5. Side effects of recursion (stack overflow).

Perhaps if we work together on this the ride will be smooth.

rmvprasad,

Please do not worry if you dont understand a lot of this, we will help explain it as you get to your solution.

Is this homework? We will still help you if it is, just in a different way that is more likely to help you in your future. I have taught programming myself and I am sure there are others like me here. We will be able to explain much more clearly if we know at what level you are at.

Paul
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi Paul,

I'm doing much the same.  Any solution is, by definition, recursive.  This is the core part of the program and we've both stayed away from doing that for him.

Kent
0
 
SadrulCommented:
apart from what's already been discussed, i would like to add a possible improvement:

we don't need to consider all the permutations of the numbers. we have numbers from 1 to 9. so each row (or column) will have a sum of ( 9 * (9 + 1) / 2 ) / 3 = 15. so at any stage, we have to check that the first three numbers (which are the numbers in the first row) add up to 15. if not, we change the permutation, without wasting our time for the rest of the positions. only when we get a sum of 15 for the first row do we proceed to set the entries in the second row, and so on. this way it should take much less time.

-- Adil
0
 
Kent OlsenData Warehouse Architect / DBACommented:

Hi Sadrul,

Good thought.  When the stack depth advances to a depth of exactly 3, 6, or 9 (on a 3*3 matrix) specific tests can be run that will determine whether the generation progresses or regresses.

But it sounds like the OP is still stuck writing the "brute force" function, which is quite a bit simpler.


I like the way you think.  :)

Kent
0
 
PaulCaswellCommented:
>>I like the way you think.  :)

I second that. :))

Paul
0
 
SadrulCommented:
thanx :-)

-- Adil
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

  • 4
  • 3
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now