Solved

Magic Square

Posted on 2004-10-25
1,410 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
Question by:rmvprasad
    10 Comments
     
    LVL 45

    Accepted Solution

    by:
    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
    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
    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
     
    LVL 45

    Expert Comment

    by:Kdo
    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
    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 45

    Expert Comment

    by:Kdo
    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
    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 45

    Expert Comment

    by:Kdo

    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
    >>I like the way you think.  :)

    I second that. :))

    Paul
    0
     
    LVL 2

    Expert Comment

    by:Sadrul
    thanx :-)

    -- Adil
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    6 Surprising Benefits of Threat Intelligence

    All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

    An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
    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.
    Video by: Grant
    The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

    913 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

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now