Java

Java RSS

even magic square?

•

Join Date: Jan 2009

Posts: 12

Reputation: kingarthur is an unknown quantity at this point

Solved Threads: 0

kingarthur kingarthur is offline

Offline

Newbie Poster

even magic square?

Jan 12th, 2009

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.

•

Join Date: Aug 2006

Posts: 137

Reputation: PoovenM is on a distinguished road

Solved Threads: 11

PoovenM

Offline

Junior Poster

Re: even magic square?

Jan 13th, 2009

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

Last edited by PoovenM; Jan 13th, 2009 at 4:58 pm.

•

Join Date: Jan 2009

Posts: 12

Reputation: kingarthur is an unknown quantity at this point

Solved Threads: 0

kingarthur kingarthur is offline

Offline

Newbie Poster

Re: even magic square?

Jan 14th, 2009

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.

 Help with Code Tags 
 java Syntax (Toggle Plain Text) 
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));
					}
				}
			}
		}
	}
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?

Last edited by kingarthur; Jan 14th, 2009 at 4:51 am.

•

Join Date: Aug 2006

Posts: 137

Reputation: PoovenM is on a distinguished road

Solved Threads: 11

PoovenM

Offline

Junior Poster

Re: even magic square?

Jan 14th, 2009

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, [i][i] 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.

Last edited by PoovenM; Jan 14th, 2009 at 5:26 am.

•

Join Date: Dec 2005

Posts: 5,850

Reputation: Salem has a reputation beyond repute

Solved Threads: 749

Salem

Offline

Void main'ers are DOOMed

Re: even magic square?

Jan 14th, 2009

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

•

Join Date: Aug 2006

Posts: 137

Reputation: PoovenM is on a distinguished road

Solved Threads: 11

PoovenM

Offline

Junior Poster

Re: even magic square?

Jan 14th, 2009

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

•

Join Date: Jan 2009

Posts: 12

Reputation: kingarthur is an unknown quantity at this point

Solved Threads: 0

kingarthur kingarthur is offline

Offline

Newbie Poster

Re: even magic square?

Jan 14th, 2009

•

Originally Posted by Salem

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, [i][i] 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

Last edited by kingarthur; Jan 14th, 2009 at 5:19 pm.

•

Join Date: Sep 2008

Posts: 1,568

Reputation: BestJewSinceJC is a name known to all

Solved Threads: 196

BestJewSinceJC BestJewSinceJC is offline

Offline

Posting Virtuoso

Re: even magic square?

Jan 14th, 2009

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.

Last edited by BestJewSinceJC; Jan 14th, 2009 at 11:40 pm.

•

Join Date: Jan 2009

Posts: 12

Reputation: kingarthur is an unknown quantity at this point

Solved Threads: 0

kingarthur kingarthur is offline

Offline

Newbie Poster

Re: even magic square?

Jan 15th, 2009

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