Let’s Numinate about Magic Squares. A Magic Square is an n x n
square matrix of cells. Each cell contains a number from 1 to the
number of cells in the square. What makes any such matrix a Magic
Square is that the numbers in the cells of each row, column, and
diagonal all add up to the same total. The simplest Magic Square is a
one by one matrix with a 1 in its single cell. Each of its rows,
columns, and diagonals (all consisting of that single cell) add up to
one. It is the “trivial” Magic Square.
The next larger matrix is a two by two. There are three ways to
assign the integers 1 through 4 to its cells (not counting equivalent
rotations and reflections of the matrix): You have to begin with one
of its corner cells (since all of its cells are corner cells), so you
put the number 1 into that cell. The number 2 may then go into an
adjacent corner, or the opposite corner. If 2 goes into the opposite
corner, the numbers 3 and 4 may go into either of the remaining
corners, but these two cases are symmetrical. If 2 goes into a corner
adjacent to the original one, then 3 and 4 may go into the two
remaining cells in two distinct ways. This gives a grand total of
three distinct ways to fill in the cells. If you draw this out on
paper (or can imagine it in your mind), you will see that each of these
fails the test of being a Magic Square.
So, the simplest matrix with an odd number of cells along one side
is a Magic Square by default, and the simplest even numbered square
cannot be made into a Magic Square. What about larger odd and even
numbered squares? I know of an algorithm for assigning the numbers to
the cells of odd Magic Squares, but I don’t know of an algorithm to
construct Magic Squares with an even number of cells. We have already
seen that the 2 x 2 Magic Square doesn’t exist.
One procedure for creating an odd Magic Square is to fill in the
cells starting with the top middle cell. You go from one cell to the
next by moving diagonally up and to the right with wraparound. From
the top row you wrap around to the bottom row, and from the right
column you wrap around to the left column. There are two special
cases: When the next cell already has a number in it, and when you are
at the upper right corner. In both of these cases, you simply drop
down one cell. Try this with a 3 x 3 matrix. The number 1 goes into
the top middle cell. Moving up and to the right, you wrap around so
that the number 2 goes in the bottom right corner. Again, moving up
and to the right, you wrap around to the center cell in the left column
and insert the number 3. Now, moving up and to the right, we encounter
the first cell, so we drop down and 4 goes into the lower left corner.
The numbers 5 and 6 go into the next two cells to the upper right (the
only cells in this example that don’t wrap around). Since 6 is in the
upper right corner, we again drop down a cell, so the 7 goes below the
6. Next, 8 requires wraparound into the upper left cell, and 9 wraps
around to the bottom center. If you check, each row, column, and
diagonal now adds up to 15. This is the simplest non-trivial Magic
Square.
As the size of the square grows larger, it appears that there are
more and more solutions. The first odd sized Magic Square has the
trivial solution, and the 3 x 3 Magic Square has only one solution, if
you don’t count rotations and reflections. However, the 5 x 5 and
larger odd Magic Squares have not only the solution generated
(guaranteed?) by the above algorithm, they have increasingly more
besides. I wonder if any of these are algorithmic, or are they each
unique puzzles?
In finding a solution for an n x n square, the first thing you need
to know is the magic total. For a square of size n, this appears to
be: (n x n x n + n)/2. I wonder if a Magic Square of any size can be
found to have a magic total different than this?
Let’s see how one might go about finding at least one solution for
Magic Squares of any size. The first thing to do is find a minimum
Magic Square. We have already constructed the 3 x 3, so let’s try to
find a solution for the 4 x 4 Magic Square. Here is one “algorithm”
for filling it in: Number it sequentially from 1 to 16, visiting the
cells as follows: Put 1 into the top left corner. Put 2 into the cell
to the right of the bottom left corner, and 3 into the cell to its
right. Put 4 into the top right corner. Now, put 5 two cells below 4,
and 6 diagonally up and to the left of 5. Put 7 just to the left of 6,
and 8 diagonally down and to the left of 7. Continue numbering the
remaining cells so that 9-12 are symmetrical to 5-8 (9 goes above 5, 10
goes below 6, etc.), and 13-16, starting at the bottom left, are
symmetrical to 1-4.
You now have one solution to the 4 x 4 Magic Square. Now you can
make larger squares by putting “rings” around smaller squares. A 5 x 5
square is a 3 x 3 square with a one cell ring around it. Likewise, a 6
x 6 square is merely a 4 x 4 square with a one cell ring around it.
All you have to do is find a solution for the ring, and slip it on.
This is how I built my first 6 x 6 Magic Square. First, I noted that
the ring would be 20 cells in circumference. The magic total needed to
be (6 x 6 x 6 + 6)/2 = 111. I guessed that 10 would need to be added
to each cell of the inner 4 x 4 matrix. That increased its Magic total
from 34 to 74, leaving 37 to be added by every two cells opposite each
other in the ring. One member of each pair of these cells would
contain a number from 1-10, and the other member a number from 27-36.
The final constraint on numbering these cells is that the total of each
side needs to be the new Magic total of 111. I made a few other
guesses and then set about with trial and error until I came up with a
ring having the following sequence: (starting at the upper left and
proceeding clockwise) the top row was 9, 27, 35, 31, 1, 8 (then
continuing down the right side), 33, 32, 7, 3, 28 (and right to left
across the bottom), 36, 6, 2, 10, 29 (and back up the left side), 34,
30, 5, 4. This solution is not unique, because pairs of cells along
any of the sides could simply be exchanged with another pair along the
same side.
Above, I made the statement that there was only one solution to the
3 x 3 Magic Square. Other than by brute force, how might this be
proved? It would appear to be a two-step proof. The first step is to
look at the possibilities where the magic total is 15, and the second
step is to prove that no other magic total is possible. Given the
magic total of 15, there are only two triplets that contain the numbers
1, 3, 7, and 9 (for example, 1+5+9 and 1+6+8 are the only triplets
containing 1 that add to 15). However, there are three triplets that
contain the numbers 2, 4, 6, and 8, and there are four triplets that
contain the number 5. Looking at a 3 x 3 matrix, we see that the
center cell needs to be part of four triplets, the corner cells need to
be part of three, and the side cells part of two.
Therefore, 5 must go into the center cell. The even numbers must go
into the corners, and the odd numbers must go into the sides. Thus
constrained, we immediately see that 1 must go opposite 9, 3 opposite
7, 6 opposite 4, and 8 opposite 2. Any choice of placement for the odd
numbers completely constrains our choice of placement for the even
numbers, and vice versa. Also, each choice for either type of numbers
is simply a rotation or reflection of any other choice that meets the
constraints. So, we must conclude that there is only one distinct
solution for the magic total of 15.
Is another magic total possible? Notice that the number in the
center cell must form the magic total with four different pairs, or all
eight of the other numbers. Let’s see if a pattern emerges when we
pick a different number for the center cell. No matter which number we
pick for the center, the first step is to arrange the other eight
numbers into pairs that each give the same total. In fact, the total
can be computed. It’s the sum of the numbers divided by four, which is
(45-C)/4, where 45 is the sum of 1 through 9, and C is the number
chosen for the center cell. If C is any even number, this doesn’t
divide evenly. If C is 3 or 7, it also doesn’t divide evenly. Only
when C is 1, 5, or 9 do we get an integer result (11, 10, or 9). With
11 (and 1 in the center), the magic total is 12. With 9 (and 9 in the
center), the magic total is 18. Both of these magic totals are even.
With an odd number in the center, there must be one other odd number
and one other even number in each triple, or the sum cannot be even.
This leads to the following contradiction: Each number of the four
pairs will be put into cells on opposite sides of the center cell. One
number of a pair is odd and the other is even. This means that one
side of the matrix will have two even numbers in its corner cells, the
side opposite it will have two odd numbers in its corner cells, and the
two remaining sides (also opposite each other) will have one odd and
one even corner cell. With an odd and an even already part of these
sides, the third number must be odd (to produce an even total). That
means an odd number across from an odd number, and we have no such
pair, nor would it sum to an even magic total if we did.
Further Numination on this topic would surely involve computer
programs and developing algorithms to search for solutions of larger
and larger squares. If you try to put a “ring” around the 3 x 3
square, you will realize that it helps to narrow your search by
recognizing patterns and constraints. Even a computer couldn’t search
all the possibilities for squares larger than 4 x 4. The number of
ways a square can be filled in is n! (“n factorial” equals 1 x 2 x 3
… x n). If a computer could examine a billion squares a second, it
would take almost half a billion years to check all the 5 x 5 squares
(5 x 5 = 25. 25! > 10 to the 25th). So, computer programs would have
to employ patterns and constraints to narrow their searches, and this
would require considerable Numination from their designers.
Although protected by Copyright, the author grants
permission to reprint this article in a non-profit publication, or copy
it over the Internet, with its Title, Copyright, and this notice.
Notification to the author and courtesy copies of the publication would
be appreciated. For other publication, please contact the
author.