Today (4/7/15) I wrote a simple program that takes an input set of numbers or generates them randomly if none are provided, and then attempts hill-climbing toward a "better" set of magic square numbers, with the goal of finding a solution. Although in its current implementation it will get stuck in local minima, it was written in an hour and purely for fun. It is enjoyable to plug random numbers into the bestGrid array and watch the behaviour of the algorithm as it iteratively attempts to improve the distance to goal. So far, I haven't coaxed it into finding any real solutions.
Magic Squares are an interesting subject I was reminded of today when Scientific American published an article. I first became familiar with them through Martin Garnder's books, which I enjoyed reading as a child. The puzzle is, in short, to find natural numbers that can be placed in a square grid such that the sum of any row, column, and diagonal are equal. The classic simple solution for a 3x3 square is
6 7 2 1 5 9 8 3 4
whose magic number is 15 and for which a parametric equation exists. It is as follows:
a+b a-(b+c) a+c a-(b-c) a a+(b-c) a-c a+(b+c) a-b
To generate the above square, let a = 5, b = 1, and c = -3. A website filled with information about current progress on the subject can be found here. It is difficult to find solutions for these squares if we restrict the values of a, b, and c to also be squares. In fact, nobody has ever found a solution for a 3x3 square of squares, although solutions of larger sizes have been identified. Ajai Choudhry found a 3x3 square of squares with 7 correct sums:
7656² 14543² 16764² 18127² 14916² 264² 12804² 10824² 16433²
This problem also shares connections with other research fields and at least one famous problem. For example, it can be shown by studying the diagonal from top-left to bottom-right that the following must hold:
If we let
then we can readily observe a permutation of a familiar formula:
And by Wiles' proof of Fermat's Last Theorem, Noam Elkies showed that for n greater than 2 this is impossible. This helps explain why all 3x3 solutions contain perfect squares. More interestingly, it reveals a deep relationship between magic squares and elliptic curves. Unfortunately, this about exhausts my knowledge of cutting-edge magic square research. If you are interested in the subject, take a look at the comprehensive site linked above.