From: tran@haldne.biogen.lsumc.edu (ldt)
Newsgroups: soc.culture.vietnamese
Subject: Re: [Help]..Math expert needed ...
Date: 10 Sep 92 16:54:38 GMT
Reply-To: tran@haldne.biogen.lsumc.edu
Organization: SCV Relay
Originator: daemon@media-lab.media.mit.edu

>From: vcsc467@sfsuvax1.sfsu.edu (CSc STUDENT)
>Subject: Re: [Help]..Math expert needed...
>Message-Id: <1992Sep9.220127.11880@csus.edu>
>Date: Wed, 9 Sep 1992 22:01:27 GMT
>
>In article <1992Sep8.163631.1@ttd.teradyne.com> nguyen@ttd.teradyne.com writes:
>>Hi pals,
>>
>>My little nephew asked me to solve a puzzle which I can't come up with an
>>answer for.  Maybe some MATH experts out there may help me explain the
>>solution to a puzzled nephew of an incompetent uncle like moi :-)).
>>
>>	The Problem :
>>
>>		Given a 5x5 square, and a set of numbers I such that 
>>
>>			 1 <= I <= 25
>>
>>		Fill the 5x5 square such that the sum of each row is equal
>>		to 65.  And the sum of each column is also equal to 65.  As
>>		well as the sum of each diagonal equals to 65.
>>
>>		Note: each number between 1 and 25 can only be used once.
>>
>>	Can you find a formular for this problem.  If it were a 4x4 or a 6x6 
>>	square, would the formular hold true?
>>
>>I've tried to generate a set of permutations on my P.C that fit the bill, but
>>this method is just a "black box solution" which I don't really care for.
>>
>>Cheers,
>>.."Pray 4-HiWind"
>>
>
>
>Answer:
>
>Actually, I don't know of a formula for this problem, but I
>did learn of a way in solving it a few yrs back.  This   
>method only works for odd x odd squares!  
>
>Here goes nothing . . .
>
>
>       |----------------------------------| 
>       |  11  |  18  |  25  |  02  |  09  |
>       |----------------------------------|
>       |  10  |  12  |  19  |  21  |  03  |
>       |----------------------------------|
>       |  04  |  06  |  13  |  20  |  22  |
>       |----------------------------------|
>       |  23  |  05  |  07  |  14  |  16  |
>       |----------------------------------|
>       |  17  |  24  |  01  |  08  |  15  |
>       |----------------------------------|
>
>
>Formula for 3x3 square:
>
>
>1>                      2>                      3>
>
>|-----------------|     |-----------------|     |-----------------|      
>|     |     |     |     |     |     |  2  |     |     |     |  2  |
>|-----------------|     |-----------------|     |-----------------|
>|     |     |     |  >  |     |     |     |  >  |  3  |     |     |
>|-----------------|     |-----------------|     |-----------------|
>|     |  1  |     |     |     |  1  |     |     |     |  1  |     |
>|-----------------|     |-----------------|     |-----------------|
>
>1)  Start from middle square of last row with # 1
>2)  Go SE, since there's no square there, go to the top of the
>    column you're pointing at w/nxt # (2) 
>3)  Go SE, since there's no square there, go all the way to the 
>    left of the row you're pting at w/nxt # (3) 
>
>
>4>                      5>                      6>
>
>|-----------------|     |-----------------|     |-----------------| 
>|  4  |     |  2  |     |  4  |     |  2  |     |  4  |     |  2  |
>|-----------------|     |-----------------|     |-----------------|
>|  3  |     |     |  >  |  3  |  5  |     |  >  |  3  |  5  |     |
>|-----------------|     |-----------------|     |-----------------|
>|     |  1  |     |     |     |  1  |     |     |     |  1  |  6  |
>|-----------------|     |-----------------|     |-----------------|
>
>4)  Go SE, since that square is occupied by a #, thus put the   
>    next # (4) on top of current square which is 3
>5)  Go SE, there is nothing in that square, thus put next # (5)
>    there
>6)  Go SE,  same as step 5 . . . put next # (6) in that square
>
> 
>7>                      8>                      9>
>
>|-----------------|     |-----------------|     |-----------------|
>|  4  |     |  2  |     |  4  |     |  2  |     |  4  |  9  |  2  |
>|-----------------|     |-----------------|     |-----------------|
>|  3  |  5  |  7  |  >  |  3  |  5  |  7  |  >  |  3  |  5  |  7  |
>|-----------------|     |-----------------|     |-----------------|
>|     |  1  |  6  |     |  8  |  1  |  6  |     |  8  |  1  |  6  |
>|-----------------|     |-----------------|     |-----------------|
>
>7)  Go SE, since there's no square there, go right to the top  
>    of current square with next # (7)
>8)  Go SE, since there's no square there, go all the way to the 
>    left on row below current w/ next # (8)
>9)  Go SE, since there's no square there, go straight to the 
>    top of that column
>
>Good luck in finding a formula for it on your PC!!
>
>Regards,
>
>/Thanh Ti.nh
>

I found this algorithm for creating an nxn magic square for n odd.
Hope it would help you.  Let me know if it works.

PROCEDURE MAGIC(square,n)

   !for n odd create a magic square which is declared as an array
   ! square (0:n-1,0:n-1)
   ! (i,j) is a square position. 2<= key <= n**2 is integer valued.
   ! <= read as less than or equal

   if n is even then [print('input error');stop]
   square <- 0                              !initialize square to 0           
   square(0,(n-1)/2) <- 1                   !store 1 in middle of first row
   key <- 2; i <- 0; j <- (n-1)/2           !i,j are current position
   while key <= n**2 do
      k <- (i-1) mod n                      !look up
      l <- (j-1) mod n                      !look left
      if square(k,l) =+ (not equal) 0 then
         i <- (i+1) mod n                   !square occupied, move down
      else
         i <- k                             !square k,l need to be assigned
         j <- l
      endif
      square(i,j) <- key                    !assign it a value
      key <- key + 1
   end while
   print(n,square)                          !output result
end MAGIC 

This algorithm is printed on page 34 of "Fundamentals of Data Structures", 
by Ellis Horowits & Sartaj Sahni, chapter 1,Computer Science Press, Inc., 1976.
I had to modify it a bit so that I could type on the terminal.

---------------------------------
Tra^`n DDi`nh Lie^.u               
LSU Medical Center in New Orleans  
tran@haldne.biogen.lsumc.edu       
---------------------------------
Newsgroups: soc.culture.vietnamese