Friday, August 21, 2015

Magic Squares

For some reason almost two years went by at LOADSTAR before I had another program (on LOADSTAR #72). It might have been LOADSTAR 128 taking up my time; it might have been that I was learning how to program better and use the programming tools we were publishing. Jeff Jones and Scott Resh had come on board and Jeff was teaching himself assembly language, which Scott was a wizard at. I remained the BASIC programmer.

 
  I just looked at the program and it asks if you want to generate some 5x5 magic squares or read a tutorial that explains how they're made. The Read It below gives you an algorithm for making 5x5 squares, but it's completely different from the one used by the program. I don't know why I did it that way, but you get two algorithms for the price of one. The staircase method (below) is probably the easiest to remember and dazzle your friends with. Ask them to make a 5x5 square where every row, column and diagonal adds up to the same number and it's doubtful they'll be able to do it. But memorize the sequence below and you can come up with as many as you want while they watch.
 
  Here is the Read It from 1990.
 


  I remember the first time I heard of Magic Squares and how they’re made. It was in a child’s puzzle book and the problem was to take the numbers from 1 through 9 and place them on a Tic-Tac-Toe grid so that each possible Tic-Tac-Toe added up to the same number, 15. Three rows, three columns and two diagonals.
It wasn’t easy. Mainly I remembered the method that the book gave for solving the problem, and for many years I had a smug feeling that I knew everything about Magic Squares. This is the method I learned.

(1) Enter the numbers in order.
1 2 3
4 5 6
7 8 9
 (2) Swap the corners.
9 2 7
4 5 6
3 8 1
 (3) Then move every number clockwise around the center number, 5.
4 9 2
3 5 7
8 1 6
 Done! I didn’t even think about higher order Magic Squares (4x4, 5x5, 6x6, etc.) until I picked up a book by Jim Moran called THE WONDERS OF MAGIC SQUARES. It seemed impossibly complex at first, but it soon began to sink in and before long I was saying “Aha!” on practically every page.
Magic Squares, and how to make them, have been studied by mathematicians and puzzlers for more than 2000 years. They wanted “algorithms”, or step-by-step methods, for constructing them. Moran’s book lists fifteen or so methods, one of which I adapted for the Run It program for this feature.
The earliest mention of Magic Squares was in China and India, where they were often carved on stone houses, or on pendants and amulets. “Magic” is a very good name for these squares, at least in a historical sense.
Benjamin Franklin was a Magic Square freak, and often bragged that he could construct 8x8’s as fast as he could write the 64 numbers. Obviously, he knew an algorithm or two.
Generally, Magic Squares are divided into two categories, odd-order and even-order. I’m going to talk about odd-order squares (3x3, 5x5, 7x7, 9x9, etc.) only, because their algorithms will work for any size, while even-order squares require different algorithms, depending on their size.
Each size of square has a constant, which is the number that all rows, columns and diagonals add up to. The formula for this constant is
Constant = (n * (n*n+1))/2

One Magic Square is actually four if you think about it, since you can simply rotate the whole square three times. But there are also many other ways to completely rearrange the numbers to form totally new squares. Would you believe that there are an estimated 275 MILLION (!) possible 5x5 squares?
The algorithm used in the Run It program is a fairly sophisticated method, developed by Jim Moran. It’s based on an early method that involves constructing two squares that aren’t magical, then adding them together to make a square that is. Run the program to see this method explained.
Most of the other methods involve what is known as the “staircase method”. This method will create one Magic Square, which can be changed into other squares by a little manipulation, such as rotation.
Here are the rules for the “staircase method” for a 5x5.

(1) Place the first number, 1, in the middle box of the first row.
(2) Place each succeeding number in the box diagonally upward to the right, unless this box is occupied by a previously placed number.
(3) When the box is “blocked”, place the next number in the box directly below the last number placed.
(4) Keep going till the square is filled.

The first question is, “Where do I put 2? Upwards to the right of 1 is off the grid!” This is what you do. Whenever a box you want to go to is off the grid, imagine that there’s another grid right next to the main one. In the rules above, 2 would be placed in the 5th row, 4th column of that imaginary grid. Instead, place the number 2 in the 5th row, 4th column of your main grid. If it’s blocked, then follow rule (3).
This means that 2 goes in row 5, column 4; 3 goes in row 4, column 5; 4 goes in row 3, column 1, etc. Here is the final grid constructed by this method.
  
17  24  1   8   15
23  5   7   14  16
4   6   13  20  22
10  12  19  21  3
11  18  25  2   9
 The first blocked move came when you tried to place the 6. The 1 was in the way. So 6 goes below 5. Study this till you see the pattern.
There are several variations on the “staircase” method. Here are the rules for one variation.

(1) Place the first number, 1, in the box to the right of the center box.
(2) Fill in the boxes by advancing diagonally upward and to the right. (Same as the other method.)
(3) In case of a blocked move, place the number in the box TWO PLACES TO THE RIGHT of the last number placed.
A blocked move will occur every five numbers. The resulting square will look like this.

3   16  9   22  15
20  8   21  14  2
7   25  13  1   19
24  12  5   18  6
11  4   17  10  23
 Notice that in both of the squares we’ve made, there is a pattern formed by numbers that add up to 26. Number 1 is diametrically OPPOSITE to 25. 2 is OPPOSITE to 24. 3 is OPPOSITE to 23, and so on.
Another way of looking at this is that a Magic Square is “balanced”. If we were to place weights corresponding to the numbers in each box and attach a chain to the middle of the middle box, we could lift the whole square and it would balance about that point. This is only true for squares made with the “staircase” method.
There are a couple of quick ways to make variations on a square, once you’ve made it (besides rotation).

(1) Swap Column 1 with Column 5. Then swap Row 1 with Row 5.
(2) Swap Rows 1 and 2 with Rows 4 and 5. Then swap Columns 1 and 2 with Columns 4 and 5.

There are several more algorithms for constructing Magic Squares which I don’t have the room for, including variations on the algorithm used in the Run It program.
I heartily recommend Jim Moran’s book, THE WONDERS OF MAGIC SQUARES, published by Vintage Books, a subsidiary of Random House, New York, 1981. It contains more than you’ll ever want to know about Magic Squares.
Maurice Kraitchik’s MATHEMATICAL REC­REATIONS, published by Dover Books, is also a great source for Magic Square lore.

Back to 2015. I think a program that generates thousands of magic squares is pretty neat. It shows what a computer is good at if programmed correctly. But I can imagine you wondering if I will ever get to any really useful programs in this project.

The answer is no. I never programmed anything you might call useful. But please stick with me and I think you will find some very interesting stuff coming up. I was a puzzle magazine nut in those days and the C-64 was the perfect platform for turning pencil puzzles into interactive, ego-less, record-keeping tools for solving, or in some cases, generating puzzles. Really! It gets better.

In fact, tomorrow night's program could be considered useful if you are like me and take a half dozen pills every morning and night. Tune in and drop out.