home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15085 < prev    next >
Encoding:
Text File  |  1992-11-17  |  1.9 KB  |  43 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!darwin.sura.net!jvnc.net!princeton!tinton.ccur.com!cjh
  3. From: cjh@tinton.ccur.com (Christopher J. Henrich)
  4. Subject: Magic Squares (was: Re: Sum of Numbers)
  5. Message-ID: <1992Nov14.233001.29160@tinton.ccur.com>
  6. Lines: 31
  7. Sender: news@tinton.ccur.com (News)
  8. Organization: Concurrent Computer Corp., Tinton Falls, NJ
  9. References: <1992Nov12.214936.15458@aio.jsc.nasa.gov>
  10. Date: Sat, 14 Nov 1992 23:30:01 GMT
  11. Lines: 30
  12.  
  13. In article <1992Nov12.214936.15458@aio.jsc.nasa.gov> nas_ps@jsc.nasa.gov writes:
  14. >I hope this is not a FAQ.  I have posted the same question on rec.puzzles.
  15. >Given numbers from 1 to 16, arrange them on a 4 by 4 - magic square such that
  16. >when added them diagonally, horizontally, and vertically would yield the same
  17. >number.  Is there any algorithm do this problem ? The solution may not be 
  18. >unique.  Can we use the solution from a simultaneous equations ?
  19. >
  20. There are 880 solutions.  We count two solutions as being the same if
  21. they differ only by a rotation or reflection of the square.  The
  22. algorithm for finding this out is an example of "backtracking."
  23. Here is an outline of how it might start (leaving out clever
  24. details):
  25.  
  26. Try to find solutions with, say, a "1" in the upper left hand
  27. corner.  So, place a "1" there; now try to find solutions by placing
  28. a "2" next to the "1".  so far so good, it seems... let's try placing
  29. "3" in the next square over.  It won't do.  To make the top
  30. row add up to 34, you would need to put "28" in the upper right,
  31. and the available numbers go up only to 16. So, *backtrack* -
  32. erase the "3" and try a "4".  And so on.
  33.  
  34. This is clearly a job for a computer.  In the seventeenth century,
  35. a French mathematician named Frenicle (^ over the first "e")
  36. did it by hand.  Others have implemented it by computer.
  37.  
  38. See also my paper on magic squares and linear algebra, in the 
  39. _American Mathematical Monthly_, June-July 1991.
  40.  
  41. Regards,
  42. Chris Henrich
  43.