Numinations — April, 2000

Magic Squares

© 2000, by Gary D. Campbell

   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.