Copyright © University of Cambridge. All rights reserved.
I share an office with Charlie Gilderdale, author of "Magic squares for special occasions". His article describes an algorithm (method) for creating a 4 by 4 magic square with a particular date across the top. One day in February, Charlie was trying to use this algorithm to produce a magic square with top row 10 2 20 01, to use at a workshop on that date. He had no problem producing one, but he was being fussy: he wanted his square to contain no negative numbers, and have no number used more than once. With some dates, this is quite easy to do, by experimenting a little at the points where the algorithm gives a choice. However for this particular date, I spent half the morning running systematically through hundreds of possibilities before I found one of the four with no repeats.
One of the good things about a neatly described algorithm is that a computer can be taught to follow it. This algorithm involves a choice at four points: a computer can quickly run through the algorithm for each possibility, check it, and print out only those squares which meet Charlie's requirements. Such a program is quite straightforward to write: with many algorithms of this type, it is quicker to write a program and run it than to do things by hand.
This program is written in Python. Python is a reasonably straightforward language which is not too difficult for a beginner to learn, but is also quite sophisticated and powerful. It is free, and runs on PCs (under MS-DOS, Windows, OS/2), Macs, and many brands of UNIX. You can download it or read much more about it.
So, let's look at how this program works. You will probably find it helpful to have Charlie's article in front of you. As in Charlie's article, the numbers in the square are represented by the letters a to p. I will present the program as it is, and try and explain each line as we go along, and then at the end I will try and summarise what's going on.
def up_to(last): return range(last+1) def has_no_repeats(square): for i in up_to(15): for j in up_to(i-1): if square[i]==square[j]: return 0 return 1
a,b,c,d = 10,2,20,01
for m in up_to(b+c): p = b+c-m
for g in up_to(a+p): j = a+p-g
for f in up_to(d+m): k = d+m-f
n = g+k-b if n< 0: continue
o = f+j-c if o< 0: continue
for h in up_to(a+m): l = a+m-h e = j+k-h i = f+g-l if e< 0 or i< 0: continue
if has_no_repeats([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p]): print a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p
Here is the program all in one go:
def up_to(last): return range(last+1) def has_no_repeats(square): for i in up_to(15): for j in up_to(i-1): if square[i]==square[j]: return 0 return 1 a,b,c,d = 10,2,20,01 for m in up_to(b+c): p = b+c-m for g in up_to(a+p): j = a+p-g for f in up_to(d+m): k = d+m-f n = g+k-b if n< 0: continue o = f+j-c if o< 0: continue for h in up_to(a+m): l = a+m-h e = j+k-h i = f+g-l if e< 0 or i< 0: continue if has_no_repeats([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p]): print a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p
So, the computer sets gaily off, taking its first value for m, its first value for g, its first value for f and its first value for h. As it goes along, it works out the values for all the other letters as well. If they're all positive, it succeeds in getting to the last two lines, and if they're all different, it'll print them out as well. It will then go back and try the next value of h. Once it has tried all the values of h, it will go back to the start of the f loop, and try the next value of f (and all the values of h that could work with that value of f). It will still be on its first values for m and g!
You can perhaps visualise this a bit better if you picture a tree which forks four times along each branch:
The picture shows just a bit of the tree, and there will probably be more branches at each fork, but hopefully you can get the idea:
The computer explores all the possibilities, starting with taking the topmost branch at each fork. Each time it reaches the end of a branch, or a problem, it goes back to the last fork, and takes the next branch. Eventually it will get down to the twig in the bottom right, having printed out all the branches which actually worked!
I did promise to explain the first six lines at some point:
def up_to(last): return range(last+1) def has_no_repeats(square): for i in up_to(15): for j in up_to(i-1): if square[i]==square[j]: return 0 return 1
You can download the program (you'll need Python first) and play with it. It would be interesting to know which dates have no magic square to suit Charlie. His article gives one restriction: are there others? If you are feeling adventurous, you could try extending the program to run through a series of dates: do use Ask NRICH if you need help with this.
This is not the only way to write a program to follow this algorithm. A future article will show how a recursive function can be used instead of all the loops.