What is a magic square?

There is an ancient Chinese legend that goes something like this. Some three thousand years ago, a great flood happened in China. In order to calm the vexed river god, the people made an offering to the river Lo, but he could not be appeased. Each time they made an offering, a turtle would appear from the river. One day a boy noticed marks on the back of the turtle that seemed to represent the numbers 1 to 9. The numbers were arranged in such a way that each line added up to 15. Hence the people understood that their offering was not the right amount.

The markings on the back of the turtle were in fact a magic square. A magic square is a square grid filled with numbers, in such a way that each row, each column, and the two diagonals add up to the same number. Here's what the magic square from the Lo Shu would have looked like. It has three rows and three columns, and if you add up the numbers in any row, column or diagonal, you always get 15.

Mathematical properties

When mathematicians talk about magic squares, they often talk about the order of the square. This is just the number of rows or columns that the magic square has. For example, a 3 by 3 magic square has three rows and three columns, so its order is 3.

In a typical magic square, you start with 1 and then go through the whole numbers one by one. For example, a magic square of order 3 contains all the numbers from 1 to 9, and a square of order 4 contains the numbers 1 to 16. Not surprisingly, magic squares made in this way are called normal magic squares.

In the Lo Shu magic square, which is a normal magic square, all the rows, all the columns and the two diagonals add up to the same number, 15. We call this number the magic constant, and there's a simple formula you can use to work out the magic constant for any normal magic square. For a magic square of order n, the magic constant is

M(n) = n(n²+1)/2.
So, for a square of order 3, we have
M(3) = 3(3²+1)/2 = 15
It is easy to derive this formula: a magic square of order n has exactly n rows, and each row adds up to the magic constant M(n). So nM(n) is the value you get when you add up all the entries in the square. But since every number between 1 and n² appears exactly once in the square, you know that the total number is also equal to
1+2+3+ ... + n².
And, as many of you may know, this sum is equal to n²(n²+1)/2. Putting all this together, you get
nM(n) = n²(n²+1)/2,
so
M(n) = n(n²+1)/2.

It turns out that normal magic squares exist for all orders, except order 2. There's only one magic square of order 1 and it isn't particularly interesting: a single square with the number 1 inside! You can work out for yourself why the square of order 2 does not exist. Mathematicians normally regard two magic squares as being the same if you can obtain one from the other by rotation or reflection. Counted in this way, there is only one magic square of order 3, which is the Lo Shu magic square shown above. There are 880 distinct magic squares of order 4 and 275,305,224 of order 5. Nobody knows how many distinct magic squares exist of order 6, but it is estimated to be more than a million million million!

De La Loubere and the Siamese Method

You might now be wondering whether there is an easy way to make a magic square without resorting to guesswork. Luckily, there is. De La Loubere was the French ambassador to Siam (now Thailand) at the end of the seventeenth century. On his return to France he brought with him a method for constructing magic squares with an odd number of rows and columns, otherwise known as squares of odd order.

Begin by finding the middle cell in the top row of the magic square, and write the number 1 in it. Continue writing the numbers 2, 3, 4, and so on, each in the diagonally adjacent cell north-east of the previously filled one. When you reach the edge of the square, continue from the opposite edge, as if opposite edges were glued together. If you encounter a cell that is already filled, move to the cell immediately below the cell you have just filled, and continue as before.

When all the cells are filled, the two main diagonals and every row and column should add up to the same number, as if by magic!

Here is a partial construction of a 5 by 5 magic square. Starting from 1, I have filled in the numbers up to 10. There is no space northeast of the 1, so I have put the 2 in the bottom row, followed by the 3. Again, because the 3 is on the edge, the 4 goes on the opposite side. The 6 should go in the cell where the 1 is, but because this cell is occupied, I put the 6 immediately below the 5 and continued up to 10. Try completing the square and then try making some of your own.

While this, known as the Siamese method, is probably the best known method for making magic squares, other methods do exist. The German schoolmaster Johann Faulhaber published a method similar to the Siamese method before it was discovered by De Le Loubere. Another way is the Lozenge method by John Horton Conway, a prolific British mathematician. Proving that these methods work can be done using algebra, but it's not easy!

Magic squares of even order

Although the Siamese method can be used to generate a magic square for any odd number, there is no simple method that works for all magic squares of even order. Fortunately, there is a nice method that we can use if the order of the square is an even number divisible by 4. (For those that are interested, the LUX method was invented by J. H. Conway to deal with even numbers that are not divisible by 4).

Instead of saying "numbers that are divisible by 4", mathematicians usually say "numbers of the form 4k". For example, 12 is of the form 4k, because you can replace k with 3. Using the same idea, numbers that give a remainder of 2 when you divide them by 4 can be called numbers of the form 4k + 2.

So start by picking the order of the square, making sure that it's of the form 4k, and number the cells 1 to (4k)² starting at the top left and working along the rows. Then split the square up into 4 by 4 subsquares, and mark the numbers that lie on the main diagonals of each subsquare. In the example, these are the coloured numbers; the order of the square is 4, so the only 4 by 4 subsquare is the square itself.

Now switch the lowest marked number with the highest marked number, the second lowest marked number with the second highest marked number, and so on. Another way of saying this is that if the magic square has order n, swap the numbers that add up to n² + 1. In this particular example, the order is 4, so we have to swap the numbers that add up to 17: 1 and 16, 4 and 13, 6 and 11, 7 and 10.

If you flip this magic square over, it is identical to the one drawn by the famous German artist, Albrecht Dürer. You can see it in the corner of his engraving Melencolia.

Here is an example of an 8 by 8 magic square constructed using the same method. The square was split into four 4 by 4 squares, and the diagonals were coloured. The coloured numbers that add up to 65 were switched: 1 was swapped with 64, 4 was swapped with 61, and so on.

A Knight's Tale

As any chess player will know, an order 8 magic square has the same number of cells as a chessboard. This similarity means that we can create a special type of magic square based on the moves of a chesspiece.

The knight is an interesting piece, because unlike the other pieces, it does not move vertically, horizontally or diagonally along a straight line. Instead, the knight moves in an L-shape as shown in the diagram. But is it possible for a knight that moves in this way to visit every square on the chessboard exactly once?

One of the first mathematicians to investigate the knight's tour, as the problem has become known, was the great Swiss mathematician Leonhard Euler. His work inspired others to take up the challenge.

Using the concept of the knight's tour William Beverley managed to produce a magic square, as shown below. Cells are numbered in sequence, as the knight visits them. Although the rows and columns all add up to 260, the main diagonals do not, so strictly speaking it is a semi-magic square. In fact, a magic square based on a knight's tour is often called a magic tour, so what Beverley produced in 1848 is a semi-magic tour!

At first glance, it seems that the following magic square by Feisthamel fits the bill. The rows, columns and diagonals all sum to 260. Unfortunately, it is only a partial knight's tour, as there is a jump from 32 to 33.

So when is it possible to turn a knight's tour into a magic square? In 2003, Stertenbrink and Meyrignac finally solved this problem by computing every possible combination. They found 140 semi-magic tours, but no magic tours. Checkmate!

Latin Squares

Latin squares are the true ancestors of Sudoku. You can find examples of Latin squares in Arabic literature over 700 years old. They were discovered by Euler a few centuries later, who saw them as a new type of magic square, and it's thanks to him that we call them Latin squares.

Latin squares are grids filled with numbers, letters or symbols, in such a way that no number appears twice in the same row or column. The difference between a magic square and a Latin square is the number of symbols used. For example, there are 16 different numbers in a 4 by 4 magic square, but you only need 4 different numbers or letters to make a 4 by 4 Latin square.

Here's an example of a Latin square, with the numbers 1 to 4 in every row and column. If you look at the first row and the first column, you'll notice that the numbers occur in sequence: 1, 2, 3, 4. When this happens, we say that the Latin square is in standard form or normalised. Any Latin square can be turned into standard form by swapping pairs of rows and pairs of columns.

There is only one normalised Latin square of order 3, and there are only 4 distinct ones of order 4, but a staggering 377,597,570,964,258,816 of order 9. In 1979 J.R. Nechvatal worked out a complicated formula giving the number of distinct normalised Latin squares of any order. To this day no-one has been able to derive from this, or any other formula, how fast this number grows as the order of the square gets large.

If we combine the two Latin squares below, we get a new square with pairs of letters and numbers. No pair is repeated, but the grid contains every single combination. We call this new square an Euler Square or a Graeco-Latin Square, and the two squares that formed the Euler square are called mutually orthogonal.

+

=

Latin squares and Euler squares have a wide variety of applications within and outside of mathematics, including experiment designs and organising round-robin tournaments. For instance, let's suppose that Albert the scientist wants to test four different drugs (called A, B, C and D) on four volunteers. To make it a fair test, he decides that every volunteer has to be tested with a different drug each week, but no two volunteers are allowed the same drug at the same time. Saying that each row represents a different volunteer and each column represents a different week, Albert can plan the whole experiment using a Latin square.

The Thirty-Six Officers Problem

Euler did a considerable amount of work on Latin squares, and even came up with some methods for constructing them. Euler easily found methods for constructing odd-order Graeco-Latin squares and squares for which the order is a multiple of 4, but he could not produce a Graeco-Latin square of order 6.

He even posed a famous problem which could only be solved by making a Graeco-Latin square of order 6. The problem of the 36 officers goes like this: is it possible to arrange six regiments, each consisting of six officers of different ranks, in such a way that no row or column contains two or more officers from the same regiment or with the same rank?

Euler never solved this problem. In fact, he believed that it was impossible to make a Graeco-Latin square if the order is of the form 4k + 2.

Just over a hundred years ago, Euler's prediction was partly proved right. A French mathematician called Gaston Tarry checked every possible combination for a 6 by 6 Euler square and showed that none existed.

Finally in 1960, Bose, Shrikhande and Parker managed to prove that Euler squares exist for all orders except 2 and 6. But bearing in mind that they had computers at their disposal, spare a thought for Tarry who had to do everything by hand!

Sudoku

If you catch a train in London, you'll see plenty of commuters with a pen in their hand, a newspaper on their lap and one thing on their mind — Sudoku.

Sudoku or Su Doku are a special type of Latin squares. They are usually 9 by 9 grids, split into 9 smaller 3 by 3 boxes. The aim of the game is to fill every cell with one of the numbers from 1 to 9, so that each number appears exactly once in each row, column and 3 by 3 box. To help you complete the puzzle, a few numbers are already given as clues.

The person credited with the invention of Sudoku is Howard Garns. The first puzzle appeared in the magazine Dell pencil puzzles and word games in 1979 and was called Number Place. The puzzle gained popularity in Japan during the 1980s, and was picked up in 2004 by the British newspaper The Times. Sudoku is Japanese for single number and the name is now a registered trademark of a Japanese puzzle publishing company.

It's difficult to tell how many distinct completed Sudoku grids there are, but mathematicians Bertram Felgenhauer and Frazer Jarvis used an exhaustive computer search to come up with the number 6,670,903,752,021,072,936,960, which was later confirmed by Ed Russell.

Solving Sudoku requires logical thinking and a systematic approach. Normally, sufficiently many numbers are given as clues in the initial grid — the one you start the puzzle with — to ensure that there is only one solution. The more numbers are filled in initially, the easier the puzzle becomes of course. So real Sudoku addicts probably prefer a small number of initial clues. But what is the minimal number of clues that have to be given to ensure that there is exactly one — and no more — solution? This is a good question, and one that so far mathematicians have been unable to answer, though there is good reason to believe that the number is 17.

And what if we turn this question around? Given an individual completed grid, how many minimal initial grids are there which have this grid as a solution? Here we mean those initial grids from which no more number can be removed without making several solutions possible. Again, mathematicians do not know the answer to this question.

But let's have a look at how to go about solving a Sudoku puzzle. Here's one I created to illustrate one of the basic techniques, known as scanning.

Looking at the middle three boxes, we have a 3 in the left-hand box and one in the middle box, but we still need to put a 3 in the right-hand box. So where should it go? Well, it can't go in the top row, because there's already a 3 in that row. For the same reason, it can't go in the bottom row, which leaves the middle row. There's only one free cell in the middle row, so the 3 has to go in it.

Now if we look at the bottom three boxes, one of the rows already has 6 numbers. I've called the empty cells A, B and C (in order from left to right), and the numbers that are missing are 3, 7 and 8. If you look at cell C, the only number that can go in it is 7. That's because the column that C lies in already contains 3 and 8.

Finding A and B is now pretty simple. There's already a 3 in the same column as B, so B has to be 8. That means A must be 3. Solving the rest of the puzzle is a bit trickier, but well worth the effort.

The Sudoku craze has swept across the globe, and it shows no signs of slowing. Several variations have developed from the basic theme, such as 16 by 16 versions and multi-grid combinations (you can try a duplex difference sudoku in the Plus puzzle). But as with magic squares and Latin squares, the popularity of Sudoku will depend on whether they can continue to offer new challenges.

---

About the author

Hardeep Aiden is a graduate of the Department of Mathematics at Imperial College, London. Apart from mathematics, he is interested in languages and linguistics, and is currently learning Japanese, French and British sign language.