Text of my article in Mathematics Teacher, Nov. 1988, Vol 81 # 8, 674-679.

Note that "N2" means "N squared".


                MAGIC SQUARES OF ALL ORDERS

                       Judson McCranie

                        Introduction

     In an article in the Mathematics Teacher, Pizarro (1986)
makes the statement that there seems to be no general procedures
for generating magic squares of even orders.  His mysterious
statement is definitely false.  Methods of construction for all
orders have been known for decades.

     First, let's review some of the basic facts of magic
squares.  Most readers will already be familiar with these
properties.  A "magic square" is a square arrangement of the
integers from 1 to N2, for order N (where N is a positive
integer), such that the numbers in the cells of each column, each
row, and each of the two main diagonals sum to the same number -
called the constant of the magic square.  The constant of a magic
square of order N is N(N2+1)/2.  Furthermore, magic squares exist
for all positive orders, except in the case of N=2.

     This paper gives methods for constructing magic squares of
all orders that can be adapted for use on a general-purpose
electronic digital computer.  A Pascal program for generating
magic squares is included.  The program was written in Turbo
Pascal for IBM PCs and compatibles, but it should run on any
Pascal system on any computer with no more than minor
modifications.  The only modification that is likely to be needed
to run it on other systems is to reduce the size of the constant
"maxorder" so the array called "cell" will fit into a small
amount of memory.

     From a computability viewpoint alone, a brute-force check of
all possible arrangements of the integers into a square
constitutes a procedure to produce magic squares of any order.
Although technically an algorithm, that approach is really not
one that is considered tractable, since the number of
possibilities grows at the rate of N factorial (N!).  The number
of possibilities would be too large to feasibly check for even
moderately small values of N.  The algorithms given here run in
an amount of time that is a quadratic function of N, which is the
best that can be expected since there are N2 cells to be filled. 
The program listed running on a Tandy 1000 generates an order 180
magic square in only about twelve seconds.   

                         Odd Orders

     When N is odd, we can use the method of S. de la Loubere as
described in Ball and Coxeter (1947) and in Hunter and Madachy
(1975).  The method is simpler than the method of Dantzig that is
given by Pizarro.  Although Loubere's method only works for odd
values of N, it is used in one of the methods of construction for
even values of N.  Let's number the columns from left to right
and call the top row the first row, etcetera.

     Loubere's method is started by placing a 1 in the middle
cell of the top row.  The rest of the integers are inserted in
order into the cells according to the following procedure.
Generally, we continue along the diagonal toward the upper right. 
When this process would take us to the (nonexistent) zeroth row,
continue with the Nth row instead.  When it would take us to the
(nonexistent) (N+1)th column, we continue on the first column
instead.  When we encounter a cell that has already been filled,
we drop down one row below the cell we just filled, fill it, and
continue diagonally from that cell.  This could cause us to go to
the (N+1)th row, in which case we go to the first row instead,
analogously to the cases above.  

     An order 5 magic square constructed by this method is shown
in figure 1.  The middle cell of the top row is filled with the
integer 1.  Then we continue along the diagonal to the upper
right, however, this would carry us off of the square, so 2 is
entered in the fifth row instead.  Then 3 is entered on the
diagonal to the right and above 2.  Then we would move off of the 
square on the right, so 4 is entered in the first column.  Then 5
is placed on the diagonal.  The next integer would be placed
along the diagonal, but that cell is already filled (with 1), so
we drop down one cell (from the cell just filled) and continue. 
This process is continued until all cells are filled, and the
result is a magic square.

                        Even Orders

     In the case when N is even and N>2, we shall examine some
methods in Ball and Coxeter.  Hunter and Madachy seem to take
their discussion of magic squares directly from this source, and
their book may be easier to obtain.  Unfortunately, their
discussion of the case in which N is a multiple of 4 is rather
ambiguous and it is not made clear how the procedure should be
generalized for higher N.  The former reference is clear,
however.  Let's call and even N singly-even if it is not
divisible by 4 and call it doubly-even if it is divisible by 4.
To motivate this terminology, note that singly-even integers are
divisible by 2 only to the first power, whereas doubly-even
integers are divisible by 2 to the second (or higher) power.

                       Singly-Even N

     First, we shall consider the case where N is singly-even,
that is N=6, 10, 14, etc.  The following method is due to Ralph
Strachey and is described by Ball and Coxeter and by Hunter and
Madachy.  The first step is to divide the N by N square into four
sub-squares of size N/2 by N/2.  Call the upper left sub-square
A, the lower right B, the upper right C, and the lower left D. 
Now consider A an N/2 by N/2 square and use Loubere's method for
order N/2 to construct a magic square in sub-square A.  Then for
each cell in sub-square B, set it equal to the sum of N2/4 and
the value in the corresponding cell of A.  For each cell in
sub-square C, do the same, except add N2/2 to the value in the
corresponding cell of A.  The cells of D are filled in the same
manner, except 3N2/4 is added to the corresponding cell of A.

     Now let M=(N-2)/4.  Consider the middle row of A.  Take the
M cells after the first one and exchange them with the
corresponding cells in D.  For the other rows of A, take the
first M cells of each row and exchange them with the
corresponding cells of D.  The final step is to exchange the
cells in the M-1 rightmost columns of B with the corresponding
cells of C.

     Figure 2 (parts a and b) shows how an order 10 magic square
is constructed by this method.  Figure 2a shows the square before
the exchanges are made.  Note that the upper left quadrant is the
same as figure 1, the order 5 magic square constructed by
Loubere's method.  Figure 2b shows the resulting magic square.

     The method of exchanging makes it clear that each integer
from 1 through N2 appears once and only once.  Although the
accompanying program uses the above method, it may be easier to
use addition and subtraction rather than exchanges.  Exchanging a
cell in A with the corresponding cell in D can be effected by
adding 3N2/4 to the cell in A and subtracting it from the cell in
D.  Exchanges between cells of B and C can be accomplished by
adding N2/4 to the cell of B and subtracting it from the cell of
C.

                       Doubly-Even N

     Ball and Coxeter give an unnamed method for the case of
doubly-even integers, that is N=4, 8, 12, etc.  First, fill in
the cells sequentially going left to right on the top row, then
the second row, etc.  So the first row will be the integers from
1 through N from left to right, the second row will contain N+1
through 2N from left to right, etcetera.  Now divide the N by N
square into (N/4)2 4 by 4 sub-squares.  Now for each cell that is
on the main diagonal of one of these sub-squares, exchange it
with the cell that is symmetric to it with respect to the center
of the N by N square.  Figure 3 shows an order 8 magic square
constructed this way.

     The method of exchanging makes it clear that each integer
from 1 through N2 appears once and only once.  From a computer
programming standpoint, it is easier to replace the cells with
its complement with respect to N2+1.  That is, if the cell with I
is to be exchanged, replace I by N2+1-I.  This is clearly
equivalent.

                       Other Methods
  
     Ball and Coxeter (1947) and Hunter and Madachy (1975) also
give some other methods of constructing magic squares, which will
be mentioned here.  The first is an alternative to Loubere's
method for odd orders which is due to Bachet de Meziriac.  It is
the same as Loubere's method method, except for two details.  The
integer 1 goes in the cell just above the center cell.  The
diagonal insertion method continues until we reach an occupied
cell.  In this method, we jump up two rows instead of down one
from the last cell that was filled.  Note that this method,
Loubere's method, and Dantzig's method all produce the familiar
magic square of order 3, which is the only one of that order
(except for rotations and reflections). 
 
     Some readers may not satisfied by the fact that two methods
are used for even orders, depending on whether N is divisible by
4 or not.  The above sources also give a method that works for
all even orders greater than 2 called de la Hire's method.  It is
a little more complex than the other methods and uses an
auxiliary square in the construction, and it is not presented
here.  

     As far as I know, there is no single method that applies to
both odd and even orders, except for the brute-force approach
mentioned in the introduction.  To be precise, the set of
algorithms is closed under the union operation.  So a program
that applies one algorithm in some cases and another algorithm in
other cases is itself an algorithm.  I know of no effective
methods that do not apply different cases, depending on the
order.

     Also, note that there are magic squares that are not
produced by any of these methods.  Except for a few small orders,
it is not known how many magic squares of a given order exist.
There is no way I know of (except for brute-force methods) to
produce all of the magic squares of a given order.

                      ACKNOWLEDGMENTS

     Thanks to the reviewers who made suggestions that improved
this paper.

                        BIBLIOGRAPHY

Ball, W. W. Rouse, and H. S. M. Coxeter.  Mathematical
Recreations and Essays.  MacMillan, New York, 1947.  Republished
Dover, 1987.

Hunter, J. A. H. and Joseph S. Madachy.  Mathematical Diversions.
Dover, New York, 1975.

Pizarro, Antonio, "Computer-generated Magic Squares", Mathematics
Teacher 79 (September 1986):471-76.

         ----------------end-of-author's-documentation---------------

                        Software Library Information:

                   This disk copy provided as a service of

                        The Public (Software) Library

         We are not the authors of this program, nor are we associated
         with the author in any way other than as a distributor of the
         program in accordance with the author's terms of distribution.

         Please direct shareware payments and specific questions about
         this program to the author of the program, whose name appears
         elsewhere in  this documentation. If you have trouble getting
         in touch with the author,  we will do whatever we can to help
         you with your questions. All programs have been tested and do
         run.  To report problems,  please use the form that is in the
         file PROBLEM.DOC on many of our disks or in other written for-
         mat with screen printouts, if possible.  The P(s)L cannot de-
         bug programs over the telephone.

         Disks in the P(s)L are updated monthly, so if you did not get
         this disk  directly from the P(s)L,  you should be aware that
         the files in this set may no  longer be the current versions.

         For a copy of the latest monthly software library newsletter
         and a list of the 2,000+ disks in the library, call or write

                        The Public (Software) Library
                              P.O.Box 35705 - F
                           Houston, TX 77235-5705
                               (713) 665-7017

