Magic Square Problems

Amagic square is an arrangement of numbers in a square so that every row, every column and each of the two long diagonals adds up alike. Dudeney calls it a very ancient branch of puzzledom, with an immense but scattered literature, and divides the study of it into three parts: construction, enumeration and classification. Construction, he says, is so well understood that there is no longer any difficulty in making squares of any size. Enumeration had hardly moved in two hundred years: there is one square of the third order, three cells by three, and Frenicle had published all 880 of the fourth order in 1693, but the number of any higher order was unknown.

Classification he treats with some suspicion, comparing it to a man who divided the human race into those who take snuff and those who do not. Still, two kinds of square were generally thought special, and he explains them with four examples of the fourth order, whose numbers are 1 to 16 and whose lines add up to 34.

The first is a Simple square, magic and nothing more. The second is Semi-Nasik: the opposite short diagonals of two cells each also add up to 34 together, as $14 + 4 + 11 + 5$ and $12 + 6 + 13 + 3$. The third is also Associated: every number and the number placed symmetrically opposite it through the centre add up to 17. The fourth is Nasik, named by a Mr Frost after the town in India where he lived, and also called diabolic or pandiagonal. In it the broken diagonals add up to 34 as well, as $15 + 14 + 2 + 3$, so that if the square is repeated in all directions like wallpaper, any four-by-four block marked off anywhere is magic.

Dudeney counted all 880 squares under these heads, and also under twelve types, according to where the complementary pairs (1 and 16, 2 and 15, and so on) lie. His table, from an article in The Queen for January 1910, is this.

Each of the 880 can be turned and reflected into seven others, which are not counted as different, so there are 7,040 squares of the fourth order in all.

Every count in the table was checked here by a program that lists all 7,040 squares, reduces them to the 880 that are different, and sorts them. It finds 48 Nasik squares, 384 more that are Semi-Nasik and 448 Simple, and all 48 Associated squares among the Semi-Nasik ones. Sorting by the positions of the complementary pairs gives exactly twelve types, with exactly Dudeney’s numbers in each, including the type that is split between 96 Semi-Nasik and 208 Simple squares. His four examples are of the kinds he names. The rest of the chapter adds new conditions to the square, as he did in The Canterbury Puzzles with coins and postage stamps.

No. 399. The Troublesome Eight

No. 400. The Magic Strips

No. 401. Eight Jolly Gaol Birds

No. 402. Nine Jolly Gaol Birds

No. 403. The Spanish Dungeon

No. 404. The Siberian Dungeons

No. 405. Card Magic Squares

No. 406. The Eighteen Dominoes

Before the next two puzzles Dudeney introduces magic squares for the other three operations of arithmetic. The multiplying square, he says, was mentioned once at the end of the eighteenth century and forgotten until he revived it in Tit-Bits in 1897; he first discussed the dividing square in The Weekly Dispatch in 1898, and the subtracting square appears here for the first time. Here are his squares of the third order.

In a subtracting square the constant comes from taking the first number of a line from the second and the result from the third, or more simply from taking the middle number from the sum of the two ends: $2 + 4 - 1 = 5$. In a dividing square the product of the ends is divided by the middle number: $3 \times 2 / 1 = 6$. The subtracting square is made from the adding square by reversing the two diagonals, and its constant is the adding constant divided by 3, the number of cells in a side. The multiplying square has constant 216, and is built from numbers in geometrical progression instead of arithmetical: the rows of 1, 3, 9 / 2, 6, 18 / 4, 12, 36 go into the cells in the same order as 1 to 9 go into the adding square. Reversing its diagonals gives the dividing square, whose constant 6 is the cube root of 216. Both of the new kinds are associated, the subtracting square by addition and the multiplying and dividing squares by multiplication. His squares of the fifth order follow the same laws, with the border centres exchanged as well as the diagonals reversed.

Every one of these squares was checked: the constants are 15, 5, 216 and 6 in the third order and 65, 13, 60,466,176 and 36 in the fifth, each adding constant is $n$ times the subtracting one, each multiplying constant is the $n$th power of the dividing one, and each pair of squares uses the same numbers. The odd orders, Dudeney says, are easy, and he leaves the even orders to the reader with two problems.

No. 407. Two New Magic Squares

No. 408. Magic Squares of Two Degrees

The last puzzles of the section are about magic squares of prime numbers, which Dudeney first raised in The Weekly Dispatch in 1900. In his day 1 was usually counted among the primes, and he counts it. He reports the work of American mathematicians on the smallest possible constants. The nine smallest such primes, 1 to 23, add to 99 and would give a constant of 33, yet the smallest constant a square of the third order can have is 111. Squares of every order up to the twelfth had been made from the lowest series of primes that could possibly serve, except the fourth order, where the lowest possible series does not work. The twelfth order was the first in which an unbroken run of primes from 1 upwards had been made into a magic square. He gives a table of these results from The Monist for October 1913, by W. S. Andrews and H. A. Sayles; beyond the third order the table is reported here, not checked.

No. 409. The Baskets of Plums

No. 410. The Mandarin’s T Puzzle

No. 411. A Magic Square of Composites

No. 412. The Magic Knight’s Tour

The Troublesome Eight

The puzzle asks for a different number in each cell, not a different figure or a different whole number, and a number may be a fraction. Dudeney’s square adds up to 15 in all eight lines, and all nine numbers are different.

With the figures 1 to 9 there are eight magic squares, all turns and reflections of one, and in every one of them the 8 is in a corner, as a program confirms. The reason is quickly seen. The four lines through the centre (middle row, middle column, both diagonals) add to $4 \times 15 = 60$, and between them they hold every number once and the centre three times more, so $45 + 3c = 60$ and the centre is 5. Then each line through the centre forces each number to make 10 with the number opposite it. So with 8 in the middle of the top row, 2 is in the middle of the bottom row, and if the top left corner holds $t$, the rest follows: $$\begin{array}{ccc} t & 8 & 7-t\\ 12-2t & 5 & 2t-2\\ 3+t & 2 & 10-t \end{array}$$ Every line adds up to 15 whatever $t$ is. For whole numbers of 1 or more, the middle row needs $t$ to be 2, 3, 4 or 5, and each of those repeats a number: $t = 2$ puts a second 8 on the left, and so on. So fractions are needed, and Dudeney’s square is $t = 4\tfrac12$. Allowing 0, though, $t = 6$ works in whole numbers:

and $t = 1$ gives its reflection. Whether 0 counts as a whole number is a matter of taste; Dudeney clearly meant it not to.

Answer $4\frac12$, 8, $2\frac12$ / 3, 5, 7 / $7\frac12$, 2, $5\frac12$

The Magic Strips

Thirteen pieces. There are six places between the seven figures where a strip can be cut, and the secret is to keep one strip whole and cut each of the other six once, each in a different place. The thirteen pieces can then be put together in many ways, one of which is this.

Every row, column and diagonal adds up to 28. Dudeney points out that the bottom row can be moved to the top and the square is still magic, and so on row after row, and that the columns can be moved across in the same way.

A program confirms all of this, and shows that thirteen really is the fewest. It considered every way of making seven rows of seven from pieces, each piece a run of consecutive numbers, with the pieces making up seven whole strips. With twelve pieces or fewer, no choice of rows even makes every column add up to 28, let alone the diagonals. With thirteen pieces there is exactly one choice of seven rows that does, and it is Dudeney’s: the whole strip and the six strips each cut once at a different place. The rows can then be stacked in any order that keeps both diagonals right. Of the 5,040 orders, 1,112 make a magic square, so the “large number of ways” is 1,112. Moving rows from the bottom to the top, and columns across, keeps each of these magic, as Dudeney says.

Answer Thirteen pieces: one strip whole, the others cut once each, in different places

Eight Jolly Gaol Birds

There are eight ways of forming the magic square, all turns and reflections of one arrangement, with the empty cell counting as nothing. Only four of them can be reached at all, and only two of those in the fewest possible moves, which is nineteen. Dudeney’s orders of moves are these, each number being the man who steps into the empty cell.

In the first every man moves, but in the second No. 3 never leaves his cell, so No. 3 is the obstinate prisoner and the second square is the one No. 7 chose.

A program searched every position the prisoners can reach. There are eight magic arrangements, four of them reachable, and the fewest moves to any is nineteen, reached by exactly these two squares. Both of Dudeney’s plays are legal and end as he says. The program also asked, for each prisoner, how many moves are needed if he never moves at all. With No. 3 fixed it is still nineteen; with No. 1 fixed it is twenty-five; with any other man fixed no magic square can be formed at all. So the obstinate man could only have been No. 3.

Answer No. 3; 19 moves: 4, 1, 2, 4, 1, 6, 7, 1, 5, 8, 1, 5, 6, 7, 5, 6, 4, 2, 7

Nine Jolly Gaol Birds

The pitfall is to suppose that the pair must stay together to the end. They are allowed to, but nothing forces them, provided that the man stepping off on the final move steps into an empty cell. With the pair together the fewest moves is seventeen; if they separate at the end, sixteen. The trick is to put the man from the centre on the back of a corner man, work the pair into the centre, and let one step off last.

Dudeney’s four solutions, the pair in brackets as the number they count for:

The first two produce Diagram A and the last two Diagram B; Dudeney’s text says “the second and third” for the second pair, a slip that replaying the moves settles. In these the pair must move at least twice, to reach the centre. The burdened man’s work can only be cut to one move by keeping the pair together, at the cost of a seventeenth move.

A program searched every choice of pair, with both endings. The fewest moves are 17 with the pair together and 16 with a man stepping off at the end, and the only pairs that achieve 16 are the centre man, No. 5, on the back of a corner man, 1, 3, 7 or 9. The least work for the pair is two moves in a sixteen-move solution and one move in a seventeen-move solution, and all four of Dudeney’s plays are sound.

Answer 16 moves, 5 on a corner man, the pair separating at the end; 17 if the burdened man is to move only once

The Spanish Dungeon

Dudeney’s advice is to work backwards: first choose the magic square that needs the least readjustment, then find the way to it. His square leaves prisoners 4, 8, 13 and 14 in their original cells and is reached in thirty-seven moves:

The clever prisoner, he says, was No. 6, who with No. 10 did most of the work, each changing cell five times, while No. 12, who was lame, had to move only once. All of this is right, except that No. 14 does move, twice, before coming home. But thirty-seven is not the fewest. This square takes thirty-five:

Here No. 1 never moves at all, Nos. 4, 6 and 8 end where they began, and No. 10 does the most work, with four moves. The empty cell counts as nothing, so the numbers in the new square are really 0 to 15, and every line adds up to 30.

The thirty-five is the fewest possible over every magic square. Since the empty cell counts as nothing, adding 1 to every cell turns a solution into an ordinary square of 1 to 16 with 1 where the empty cell is, so there are 7,040 candidate arrangements, one for each square of the fourth order. As in the fifteen puzzle, half of them can never be reached, which leaves 3,520. The number of moves is at least the total distance of the prisoners from their new cells, and for 1,348 of those squares that total is 36 or less. A program searched each of these exactly, allowing up to 36 moves, and only the square above can be reached so quickly; it needs exactly 35. The same search finds that Dudeney’s own square cannot be reached in fewer than his 37, so his prisoner did well with the square he chose.

Answer 35 moves, to 1, 10, 15, 4 / 13, 6, 3, 8 / 2, 9, 12, 7 / 14, 5, empty, 11 (Dudeney, 37)

The Siberian Dungeons

The only block of sixteen cells in the prison is the square formed by cells 17 to 24 above cells 5 to 8 and 13 to 16, so the magic square must be formed there. Keeping some men in their cells saves moves but may block others. For example, a magic square can be formed with 6, 7, 13 and 16 unmoved, but then cells 14 and 15 can be neither left nor entered. Dudeney gives this solution in fourteen moves, found by Mr G. Wotherspoon, each move from one cell to another:

Dudeney thought fourteen the theoretical minimum, and so did Mr Wotherspoon, but neither gave a proof. Here is one. There are 7,040 magic squares the men could form in the block. Every man not already in his final cell must move at least once, so a square that leaves $u$ men where they started needs at least $16 - u$ moves, and only a square leaving three or more men in place could possibly be formed in thirteen moves or fewer. Just thirteen squares do. A program searched each of them exactly, with every move any distance through empty cells, and none can be formed in thirteen moves. The same search finds Wotherspoon’s square in fourteen moves and not in thirteen, as a check. So fourteen is the fewest. The program also confirms Dudeney’s remark: two magic squares keep 6, 7, 13 and 16 in place, and in neither do 14 and 15 stay put, so neither can be formed.

Answer Fourteen moves, Wotherspoon’s solution; no square can be formed in fewer

Card Magic Squares

The three new squares add up to 9, 18 and 27, and the old one to 15, all different. Three aces and one ten are left over. A check confirms that every square is magic and that no value is needed more than four times, counting the nine cards of the first square.

Answer Squares adding 9, 18 and 27 as above; three aces and a ten unused

The Eighteen Dominoes

The pips in every column, row and long diagonal add up to 18, and the eighteen dominoes are all different. The limits Dudeney states are easy to confirm. The eighteen dominoes with fewest pips hold 76 between them, and the six rows share out all the pips, so a row must hold at least $76/6$, that is 13. The eighteen with most pips hold 140, which allows at most 23 a row. His square for 13 was also checked, and is right.

Answer The square above, adding up to 18 in all fourteen lines

Two New Magic Squares

The subtracting square uses 1 to 16, has constant 8, and every pair of numbers placed symmetrically through the centre differs by 4. The dividing square has constant 9, and every such pair gives 3 on division. Both were checked in every line.

Answer The two squares above: subtracting constant 8, dividing constant 9

Magic Squares of Two Degrees

This is Dudeney’s square. Every row, column and diagonal adds up to 260, and when each number is replaced by its square they all add up to 11,180.

The main key is a pretty law. If eight numbers add up to 260 and their squares to 11,180, then the eight numbers that make 65 with them do the same. The first half is plain, since $8 \times 65 - 260 = 260$, and for the squares $$\sum (65 - x)^2 = 8 \times 65^2 - 130 \sum x + \sum x^2 = 33{,}800 - 33{,}800 + 11{,}180.$$ For example, 1, 18, 23, 26, 31, 48, 56 and 57 add up to 260 and their squares to 11,180, and so do 64, 47, 42, 39, 34, 17, 9 and 8. In each of the sixteen small squares of four cells the two diagonals add up to 65, and the rows and columns go in complementary pairs. The numbers of the second, first, fourth and third rows, rearranged, fall into columns of four consecutive numbers taken cyclically, four columns running one way and four the other:

The difficulty is to find the laws that govern these groups, the pairing of complements within the small squares, and the diagonals. Dudeney thought the square the most elegant thing in magics, and believed none could be made of any order below 8. A program confirms his square and finds that none exists of order 3 or 4; the whole of his belief was proved by Christian Boyer and Walter Trump in 2002, who showed that no such square exists of any order below 8.

Answer The square above, adding to 260, and its squares to 11,180

The Baskets of Plums

If the number in every basket is prime, no sharing among some children, each getting the same number of plums, is possible, since giving the whole basket to one child or one plum each to as many children as there are plums does not count. So the puzzle is to make a magic square of nine different primes.

Square A has the smallest constant possible, 111. But it is barred by the trap: every basket “contained plums”, and one plum is not plums. The picture also shows more than 7 plums in each basket, which strictly bars C as well. Numbers between about 20 and 250 are well within reason, and B is one of many such squares. Some readers thought the numbers could not be in arithmetical progression, and D answers them: 199, 409 and so on to 1,879, all prime, with a common difference of 210.

All four squares were checked: each is magic, with constants 111, 213, 219 and 3,117, and every number is prime if 1 counts. A search over every magic square of three, which always has the form $c + a$, $c - a - b$, $c + b$ / $c - a + b$, $c$, $c + a - b$ / $c - b$, $c + a + b$, $c - a$, confirms that 111 is the smallest constant counting 1 as a prime. Without 1, as primes are counted today, the smallest is 177:

This would also serve for the plums, with no basket suspiciously small except the one with five.

Answer Nine different primes in a magic square, such as B: 83, 29, 101 / 89, 71, 53 / 41, 113, 59

The Mandarin’s T Puzzle

Dudeney’s square is Nasik, and he says that of all 28,800 Nasik squares of the fifth order it is the only one, with its reflection, that meets the condition. The puzzle was suggested to him by Dr C. Planck. He adds that there are many other ways of arranging the numbers, leaving either the 2 or the 3 off the T.

A program found all the Nasik squares of five, confirming that there are 28,800, and that his square and its reflection are the only two with primes on the T. For ordinary magic squares, where only the two long diagonals need add to 65, Dudeney’s remark falls short. The prime left off the T may be any of the ten except 23: a square exists for each of the other nine, and none leaves out 23.

Answer The square above, the only Nasik square of the kind with its reflection

A Magic Square of Composites

The problem is to find the smallest prime that is followed by at least nine composite numbers before the next prime, and it comes before reaching 150: after 113 the next prime is 127. The numbers 114 to 122 make this square.

Dudeney also shows how to find such a run without tables. Take the numbers 2 to 10, whose only prime factors are 2, 3, 5 and 7, and add their product, 210, to each. The results, 212 to 220, are all composite. He says every one is divisible by its difference from 210, which is not quite right: 214 is not divisible by 4, nor 218 by 8, nor 219 by 9. What is true is that each shares a prime factor with its difference from 210, which is enough to make it composite. For sixteen numbers, the primes up to 17 multiply to 510,510, and 510,512 to 510,527 are all composite, as a check confirms.

His smallest runs are also right. The first run of sixteen composites starts at 524 and of twenty-five at 1,328, as he says, and a run of thirty-six is not found below 10,000: the first starts at 15,684.

Answer 114 to 122, in the square above

The Magic Knight’s Tour

This is Dudeney’s best attempt.

A check confirms that the knight visits every square once, that 64 is a knight’s move from 1, so the tour closes on itself, and that every row and column adds up to 260. The diagonals add up to 264 and 256, the slight error he admits.

His pious opinion was right. The question stayed open until 2003, when an exhaustive computer search by Stertenbrink found every semimagic knight’s tour of the chessboard, one whose rows and columns add up to 260. There are 140 different ones, and in none do both diagonals add up to 260, so no magic knight’s tour of the chessboard exists.

Answer No perfect solution exists; the best has diagonals of 264 and 256