Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Magic Square

Posted on 2004-10-25
10
Medium Priority
?
1,463 Views
Last Modified: 2010-05-18
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
Comment
Question by:rmvprasad
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
  • 2
  • +1
10 Comments
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 2000 total points
ID: 12407013
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
 
LVL 6

Expert Comment

by:Amritpal Singh
ID: 12408372
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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12419240
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12421433
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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12421631
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
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12421676
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
 
LVL 2

Expert Comment

by:Sadrul
ID: 12435999
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
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12436571

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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12442192
>>I like the way you think.  :)

I second that. :))

Paul
0
 
LVL 2

Expert Comment

by:Sadrul
ID: 12442221
thanx :-)

-- Adil
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

618 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question