even magic square?

[kingarthur]

Hi there,
this is my first post, so pls be polite ;)
since a few days i am programming java (for school).

but i dont get it.. i tried to fill the 4x4 matrix with random generated numbers (1-16) and wrote a method, that they could only be used once.
then i wrote some methods to check wether die rows,cols and diagonals have the right sum.

But that way coasts me ~1 day to find a real magic square and that is def. not okay.
i googled for a while and found many solutions, but most of them didn't work correctly. someone told me, that i am supposed to use "backtracking". but i dont understand this theory.

Does anybody have a working backtracking solution for an evan magic square or could explain that theory to me?

it would be really great!

thank you

bye

ps: sorry for my bad english.

[PoovenM]

I'd like to help... but I have no knowledge of magic squares or the mentioned algorithm... or perhaps I do and it just sounds foreign. Care to explain what a magic square is? An example would suffice. It appears that you just need a bunch of criteria to verify if the square is 'magic' or not? In which case, please show us your code so that we can identify logic errors... and perhaps you don't need to use backtracking.

Oh and welcome to DaniWeb! You'll find that we're rather polite and friendly to those that actually try to do their homework hehe

[kingarthur]

Hi,
thank you for welcoming me ;)

Sorry, i'd forgotten to explain the magic square:
a magicS is matrix (in my case 4x4) filled with the numbers from 1 - 16. each number could only be used once and the sum of every row,collum and the 2 diagonals has to be 34.

i have tried some algorithms and i made it.

public void versuche(int n, int[][] quadrat, int ziffer){
	          long time1 = System.currentTimeMillis();
		if ((ziffer > (n*n)) && isMagisch(quadrat)){
			zeige(quadrat);
			System.exit(0);
		} else {
			for (int x = 0;x<n; x++){
				for (int y = 0; y <n; y++){
					if (quadrat[x][y] == 0){
						quadrat[x][y] = ziffer;
						do{
						versuche(n, quadrat, ziffer);
						quadrat[x][y] = 0;
						}while(checkZiffer(quadrat, ziffer));
					}
				}
			}
		}
	}

but this one is very slowly. it should solve the square in 1-2 seconds. my algorithm needs 30min :(

Could someone help here?

[PoovenM]

Oh gosh, your code is rather confusing... I think it's because I'm not sure what your methods and variable are meant to do. If the algo is taking that long to compute the answer (does it give the correct answer?) then it is flawed.
My first question: the method isMagisch, what does that check? Based on the name, I'd assume it determines if the matrix is 'magic' or not?
My second question: How do you verify that the numbers you generate are not duplicated?

My suggestion: Sum the diagonal that goes from left to right in which case the indices increment by 1 for both dimensions of the matrix, that is, where i is the counter in the for loop.
Then sum the other diagonal, where one dimension increases as the other decreases (the pairs would be {0, 2}; {1, 1}; {2, 0}). If the sum of the previous diagonal is the same as the newly calculated sum then proceed.
Sum each row, iteratively, if the sum of the diagonal isn't equal at any point then break the loop.
Sum each column and the same principal as above applies. Don't sum each column if the above checks indicated a negative 'magic square.'

If you're having trouble understanding how to implemented what I've suggested, please first try parts of it and post your attempted code and we'll help spruce it up. My suggested method might not be 'backtracking' but it should take at most a few seconds to process.

Oh, one last comment: it seems that you're using n to store the dimension of your matric. Rather use quadrat.length or quadrat[0].length where both length final variables would have the same value. Let me know if you don't understand this concept.

[Salem]

Did you research the problem at all before diving headlong into the code?
http://en.wikipedia.org/wiki/Magic_square

[PoovenM]

Ah, so then calculate M, as defined by the wikipedia site Salem provided and ensure the calculated sums match M?

[kingarthur]

Did you research the problem at all before diving headlong into the code?
http://en.wikipedia.org/wiki/Magic_square

What do you exactly mean?
the first part with M? this is definitly wrong. just try n = 4.

in their set phrase the Sum should be 43. but it isnt. a magic square of n=4 has a sum of 34(!!). the real set phrase has to be :
M = n/2 * (n+1)
-> n means cells (=16)
M = 16/2 * 17
M = 8 * 17
M = 136
136 : 4 = 34

if you meant the constructing part, then: this doesnt work neither. because i have initial values, so i cant work with a system. i have to "backtrack" :)

My hole programm runs correctly. if n=3, then it take me just 250ms to generate the square. but with n=4 i need 3h(!!).

Oh gosh, your code is rather confusing... I think it's because I'm not sure what your methods and variable are meant to do. If the algo is taking that long to compute the answer (does it give the correct answer?) then it is flawed.
My first question: the method isMagisch, what does that check? Based on the name, I'd assume it determines if the matrix is 'magic' or not?
My second question: How do you verify that the numbers you generate are not duplicated?

isMagisch checks the entire square (collums,rows and diagonales).
to verify i wrote a method checkNum(), which goes threw the array and checks wether the number is used or not. then it returns true or false
if its true (== number is already justed) then he adds 1.

My suggestion: Sum the diagonal that goes from left to right in which case the indices increment by 1 for both dimensions of the matrix, that is, where i is the counter in the for loop.
Then sum the other diagonal, where one dimension increases as the other decreases (the pairs would be {0, 2}; {1, 1}; {2, 0}). If the sum of the previous diagonal is the same as the newly calculated sum then proceed.

okay, you mean, that i have to check only the diagonales, while i am filling it?!
what should it be good for? it doesnt proof anything

Oh, one last comment: it seems that you're using n to store the dimension of your matric. Rather use quadrat.length or quadrat[0].length where both length final variables would have the same value. Let me know if you don't understand this concept.

stupid question, but why? where is the difference? i tought it would be easier for the "user" ;)

thanks for your patience

[BestJewSinceJC]

What part of your code isn't working? Your code should be split into pieces/methods that each perform a specific task. You should be able to identify where the code isn't behaving as expected, either with a debugger or just by using print statements. Tell us where your code doesn't work, and we will help you make it work. Asking us to "solve this for you" is ridiculous, especially since very few of us actually know what magic squares is.

[kingarthur]

Hi there,

sorry. i didn't ment, that you should solve my homework ;)

Okay, from the scratch^^ :

a magic square is a square with a length of 4x4 Cells (in my case).
these cells should be filled with the numbers 1-16. each number should only be used once and the sum of each row, collum and diagonal has to be 34.

My version of the magic square is working. but it costs me 3h, instead of 1-2 seconds.

my code is splitted into methods for: filling the square, for checking the entire square of it's sums, for checking the current number, if its already used and for printing the whole array.

its just, that the filling seems to have some problems. i tought, that their is a general solution for backtracking and i made a clearly mistake that you would see in a view seconds ;)

all my other methods are working fine. i tested them.

bye

[Aditya_5]

Hi there kingarthur!
this is my first post too, so pls be polite ;)
I'm programming for school too.
I completely understand what you mean by "recursive backtracking".(quite usefull)
I'm having the same problem with even magic squares as they dont have any pattern.If you have got over the problem please tell me.
I tried this code(but taking too long for n=4).Works fine with 3x3.

static boolean control(int ar[][],int n){
  for(int i=0;i<n;i++){
  for(int j=0;j<n;j++){
      if(ar[i][j]==0){
          for(int k=1;k<=n*n;k++){
              if(eligible(ar,k)){ar[i][j]=k;
              if(control(ar,n))return true;ar[i][j]=0;}
              else ar[i][j]=0;  }
      if(ar[i][j]==0)return false;}
      }}
if(sum(ar))return true;
return false;
    }

eligible()-checks repetition
sum()-checks sum of rows,cols and diagonals.
please reply.

[JamesCherrill]

Hi Aditya, wecome to DaniWeb.

kingarthur posted this 4 years ago, and hasn't been seen here for the last 2 years, so you probably won't get a reply from him now.

Start a new thread of your own and someone will help.

ps Don't be surprised by long run times for bigger squares - the number of ways to fit all the numbers in an nxn square scales something like n squared factorial - that's truely horrendous. I tried this and got solutions for a 5x5 grid in about 50,000 recursions, but a 6x6 took about 54 million (70 seconds on my not-very-fast pc).