Solved

Magic Square with variable dimensions

Posted on 2008-10-01
18
4,878 Views
Last Modified: 2013-12-14
Hello everyone, I hate to make my first question as my first post, I would like to become a part of this seemingly great community, but I need to ask a question because I am stumped.

I need to create a Magic Square. This is my homework assignment, and I have spent 3 days now trying to figure it out. My instructor has not responded to my questions via email and hopefully you guys can help with this assignment.

Here are the instructions:

"
A magic square is an n x n matrix in which each of the integers 1,2,3...n 2 appears exactly once and all column sums, row sums, and diagonal sums are equal. For example, the following is a 5 x 5 magic square in which all of the sums add up to 65:

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

The following is a procedure for constructing an n x n magic square for any odd integer n. Place 1 in the middle column of the top row. Then after integer k has been placed, move up one row and one column to the right to place the next integer k + 1, unless one of the following occurs:

    * If a move takes you above the top row in the ith column, move to the bottom of the ith column and place k + 1 there
    * If a move takes you outside to the right of the square in the ith row, place k + 1 in the ith row at the left side.
    * If a move takes you to an already filled square or if you move out of the square at the upper right-hand corner, place k + 1 immediately below k.

Write a program to construct n x n magic square for any odd value of n. "


My current code is started but the logic to actually enter the values I am stumped. I can only use <iostream>.
I know that I need to create a counting (for) loop to add the values into the array, but I literally am stumped. Hopefully someone will be up tonight who can help me out!

Thanks in advance, and I am happy to be on the site now.

#include <iostream>

using namespace std;
 

void fillMagicSquare(int newarray[][n], int size);
 
 

int main()

{

int n = 1;

cout << "Please enter the size of the matrix, it must be an odd number: " << endl;
 

	while (true)

	{

			cin >> n;

			int magic_square[n][n];

			if (n%2==0)

				{

					cout << "You must choose an odd number! Choose Again: " << endl;

				}

			else

				{

				fillmagicsquare(arra, n);

				}

	}

}
 
 
 

void fillMagicSquare(int newarray[][n], int size)

{

size = n2;

int nsqr = n2 * n2;

int i=0, j=n2/2;
 

}

Open in new window

0
Comment
Question by:underscore_elite
  • 6
  • 5
  • 4
  • +2
18 Comments
 
LVL 84

Expert Comment

by:ozo
Comment Utility
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
0
 

Author Comment

by:underscore_elite
Comment Utility



Thank you for the links that explain the workings of magic squares... I understand how the square "works" I am really just trying to lay it out into code.


Here is my best noob assumption on how the program would work.

I would assume a series of for loops that would place the appropriate values -- starting with 1 and moving up and to the right to place the next value (2), and to somehow figure out if a value has already been placed in that coordinate of the array, perhaps if the array gets set completely to 0 and then the program somehow checks to see if the value in that box is 0 and if it is, it will put the next value in it, if it is not zero then it will put the value in the box directly below it. That is at least how I think the logic would work.

Oh my, that is not even remembering that if it hits the top of the array, I have to somehow tell it to put the next value in the opposite side of the array. I feel like I know what it needs to do, but putting it into actual code is tough. This is an 8 week course, and it seems that we were just learning functions and operators a week or two ago, and now we are getting into crazy arrays, and searching them, my instructor does not explain anything and never answers emails. I basically have the internet and my book to help (and the book is not much help). I know that with practice it will eventually come naturally, but I have only been learning coding for less than 6 weeks. I aced my basic class because the teacher actually explained everything.

Anyways enough with my personal problems and frustration, I am asking for help, I am not asking for the code, I just feel like I do not even know where to start building those loops.

0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
The code you posted has a few problems :

1)
>>                         int magic_square[n][n];

You cannot declare a static array with a variable dimension. If you need that, you need to dynamically allocate the array. Take a look at this tutorial about dynamic memory :

        http://www.cplusplus.com/doc/tutorial/dynamic.html


2)
>>                                 fillmagicsquare(arra, n);

'arra' has not been declared.


3)
>> void fillMagicSquare(int newarray[][n], int size);

'n' is not a const value here, so it can't be used like this. In any case, as per my first remark, you should probably use dynamically allocated arrays, which are passed to a function slightly differently (as a pointer-to-pointer).


4)
>> size = n2;

You passed 'size' as a parameter to the function ... why do you overwrite that value ? What is 'n2' anyway ?



Start by fixing these problems, and you should have a working framework for the assignment. All that's left then is to :

(a) implement the algorithm for generating the magic square
(b) output-ing the result
0
 

Author Comment

by:underscore_elite
Comment Utility
Thank you for the response, I will use your suggestions and keep working at it.

For the mean time, I have been trying a different setup for the whole thing... check it out and see if it would be set up better.... There are notes inside the code to explain what I was thinking while I wrote some of this stuff.





#include <iostream>

using namespace std;
 

int getDim();

int n2;
 

int main()

{

int i;

int j;

int n = getDim();  // trying to get a value to 'n' that is the user provided odd number from the getDim function, but it always comes back 0.

cout << "You chose a "<< n << "x" << n << " matrix" << endl; //this line is to test if the value for 'n' came back correctly.
 

/* below is where I declared the matrix using the coordinates 'n' that the user provided. 

int matrix[n][n]; I believe I get a compiler error from this line. Does an array have to be filled with a constant? 
 

!! THE CODE COMPILES WITHOUT ERROR IF I REMOVE THE BELOW LOOP. !! 

The reason being because I have not declared my matrix array, I have not declared it because I do not

know how to create an array with dynamic dimensions yet. Something my teacher decided to not teach but expect us to know
 

*/

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

	  

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

	  

          matrix [i][j] = 0;
 

}
 
 
 

int getDim()

{

int n = 0;

cout << "Please enter the size of the matrix, it must be an odd number: " << endl;
 

	while (true)

	{

			cin >> n;
 

			if (n%2==0)

				{

					cout << "You must choose an odd number! Choose Again: " << endl;

				}

			else

				{

				n = n2;

				return (n2);

				}

	}

}

Open in new window

0
 
LVL 3

Expert Comment

by:sistemu
Comment Utility
"int matrix[n][n]; I believe I get a compiler error from this line. Does an array have to be filled with a constant? "
As Infinity08 just said before,you can't define an array like that.
The memory is allocated at compile time, but your program finds out the value of n only at run-time. If you didn't learned to allocate dinamicaly memory, you should try something like
  int matrix[10][10];
 It should be enough.
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
Comment Utility
>> int n = getDim();  // trying to get a value to 'n' that is the user provided odd number from the getDim function, but it always comes back 0.

That's because of this line :

>>                                 n = n2;

As I said in my previous post, you're overwriting the value of n here with n2.



>> int matrix[n][n]; I believe I get a compiler error from this line. Does an array have to be filled with a constant?

See my previous post.



>> I have not declared it because I do not know how to create an array with dynamic dimensions yet.

See the tutorial I posted earlier ;)
0
 

Author Comment

by:underscore_elite
Comment Utility
Thanks everyone!! Really good info, much appreciated. I will keep working and probably have a couple more questions here soon. Points will be awarded in the morning :-)
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> Points will be awarded in the morning :-)

You can keep working with us on this assignment if your prefer, and award the points once the assignment is done.
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 

Author Comment

by:underscore_elite
Comment Utility
Okay to be honest, I borrowed some logic for the loops that will control the placement if the location that it is supposed to add a number is not a zero, OR if the location already has a number in it. I wrote it all from scratch, but I had to look at the setup of the loops in order to move the placement. I completely understand it when I actually look at the code, it sucks that it is so hard for me to just "think" it up in my head without having to melt my brain against the keyboard <_<

So.... everything is compiling, and the array seems to be filled correctly.

Yet I am stuck printing my array. I am forced again to put variables into the coordinates for the array. Feedback is needed, thanks....


To Print the Array, I am using code shown below, how can I print the array in proper format, and keep variables out of the array coordinates?



   /* n is the length of each side (the dimensions) and r and c are just placeholders for the for loops.
 

*/
 

int r;

	int c;

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

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

			cout << matrix[r][c] << "/t" ;

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> how can I print the array in proper format, and keep variables out of the array coordinates?

You can use variables as indexes into the array. What I said earlier was about defining the array - you cannot use non-const variables for that.

So, in this case, it's fine.
For properly formatting the output, you'll however need to do a few more things :

(a) instead of <= for the upper boundary, use <. You don't want to show too much data.

(b) you'll need to add a newline at the end of each row.

(c) \t is the tab character, not /t
0
 
LVL 45

Expert Comment

by:Kdo
Comment Utility
Hi underscore,

A couple of things to add to the discussion.....

There are several advanced concepts in play here.  Dynamic memory management and possibly recursion.  Getting a good program out of this will be easier if you tackle one of them at a time.

Start by "hard coding" the matrix size.  Make it arbitrarily large (perhaps 100 x 100) so that you can build any magic square in it up to size 100.  Having an upper limit of 100 shouldn't be a hardship for developing the code.  After you have the algorithm debugged you can come back in install the dynamic arrays.

As far as building the magic square, it's not nearly as tough as the instructor would have you believe.  :)

Start with the cell at 0,0 and place a 1 in it.  Then move across the row, putting a value into each cell.  When the row is full, move to the next row and repeat.  When you insert a value into a cell, test that the value does not violate the uniqueness rule for that row and column.  The algorithm will need to be able to test all values from 1 to n for each cell, though not every value will be tried in every cell.

This will create a very nice pattern to the data so it will be easy to see if you "got it right".

The algorithm can be coded recursively.  Nested loops are a start, but a recursive routine will be easier.


Good Luck,
Kent
0
 

Author Comment

by:underscore_elite
Comment Utility
Thanks everyone. I really appreciate the feedback.

Here is my final code. I did not finish it completely, but it compiles and seems to make the square logically and completely but it does not print it.


#include <iostream>

using namespace std;
 

int getDim();

int n2;
 

int main()

{

int zerorow;

int zerocol;

int n = getDim();

cout << "You chose a "<< n << "x" << n << " matrix" << endl;

int matrix[45][45];

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

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

       matrix [zerorow][zerocol] = 0;
 

int row = 1;

int col = (n+1)/2;

int row2;

int col2;

int k = 1;

int nsq = n*n;
 

matrix[row-1][col-1] = k;
 

for(k=2 ; k <= nsq ; k++)

{

row2 = row - 1;

col2 = col + 1;
 

if (row2 == 0 && col2 == (n+1))

	{

    row2 = row + 1;

    col2 = n;

    row = row2;

    col = col2;

    matrix[row-1][col-1]=k;

    }

else

    {

    if(row2 == 0)

    {

    row2= n;

    }

    if(col2 == (n+1))

    {

        col2 = 1;

    }

    if(matrix[row2-1][col2-1] == 0)

    {

        row = row2;

        col = col2;

        matrix[row-1][col-1] = k;

    }

    else 

    {

    row2 = row + 1;

    row2 = col;

    if(row2 == (n+1))

    {

    row2 = 1;

    }

    row = row2;

    col = col2;

    matrix[row-1][col-1] = k;

}

}

}

return 0;
 

}
 
 
 
 

int getDim()

{

int n = 0;

cout << "Please enter the size of the matrix, it must be an odd number: " << endl;
 

	while (true)

	{

			cin >> n;
 

			if (n%2==0)

				{

					cout << "You must choose an odd number! Choose Again: " << endl;

				}

			else

				{

				n2 = n;

				return (n2);

				}

	}

}

Open in new window

0
 
LVL 45

Expert Comment

by:Kdo
Comment Utility

Printing the array is pretty simple (about 4 lines of code).  Insert the following code right before the return statement in main().

for (row = 0; row < n; ++row)
{
  for (col=0; col < n; ++col)
    fprintf (stdout, " %2d", matrix[row][col]);
  fprintf (stdout, "\n");
}


You'll find that your algorithm needs some help.  :(  You're not building a valid magic square.


Kent
0
 

Author Comment

by:underscore_elite
Comment Utility
well I guess I wont get full credit on it since the algorithm is not correct, but thanks for the input Kent.

The problem with the print code that you gave me is that we have never learned fprintf or stdout so we are not allowed to use it.

Next time I will take a full semester coding class instead of short term (fast track) so we do not cover the entire book in 7 weeks. I am fresh with no coding knowledge, and like I said before, it seems like we were just practicing making variables and structuring arrays about a week or two ago, and now were all the way here.

I am making a new thread with my next assignment once I get some valid code written. (I am not here to cheat, just get help and guidance) so hopefully all your experienced coders will meet up with me on that thread when I make it.

Thanks again everyone. Sorry the code is flawed, it just does not come naturally for me.
0
 
LVL 45

Expert Comment

by:Kdo
Comment Utility

Sorry -- using fprintf(stdout ....  is just a habit with me.  You can also do it using printf

for (row = 0; row < n; ++row)
{
  for (col=0; col < n; ++col)
    printf (" %2d", matrix[row][col]);
  printf ("\n");
}


Kent
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> Sorry -- using fprintf(stdout ....  is just a habit with me.  You can also do it using printf

I think they're learning C++, rather than C, and so are using the C++ streams (cout, etc.) for I/O. At least that's what his original code was using.


>> well I guess I wont get full credit on it since the algorithm is not correct

So you don't want to put in a little bit more effort to make it correct ? You're almost there ...
0
 
LVL 45

Expert Comment

by:Kdo
Comment Utility
>> I think they're learning C++, rather than C, and so are using the C++ streams (cout, etc.) for I/O. At least that's what his original code was using.

Showing my age, huh?  :)  If I don't go back and check the fine print I automatically revert to C.

0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.

743 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

12 Experts available now in Live!

Get 1:1 Help Now