Recreational Math I: 4×4 squares: Some sequences work better than others

I was experimenting with Danny Dawson’s 4×4 magic square script, and began to consider writing my own script. But I just thought I would do a few runs for my own research. I wanted to thank Mr. Dawson for his fine work which I am obviously gaining knowledge from, but his comments page thought I was a spam bot, and rejected my comments. Oh well ….

The central topic of discussion here centers on building an algorithm for a computer program that can search for and find all or most squares, centering on initial construction. But the discussion on pairings work for magic squares generally.

Some number pairings work better on the 4×4 square than others. What I mean by number pairings are two sequential numbers being placed next to each other along a column or row of the magic square. Dawson’s script allows me to place any numbers on the magic square, and it would output all of the magic squares that fit the arrangement of numbers I suggested by filling in the rest. I only worked with two numbers, and it would suggest to me complete squares which work with that placement of a pair of numbers. Some number pairs resulted in more than one magic square, while other pairs gave no squares.

It would tell me that in a computer algorithm for such squares, if an “unsuccessful” pair of numbers show up next to each other in a magic square made by a brute force algorithm such as Dawson’s, the smart thing to do is to detect this situation and abandon the square’s construction, thus saving computer procesing time, an amount of time Dawson attested to as being potentially long, on the order of hours at best, to decades at worst.

My research was far from thorough, but I think I took into account most situations where the pairings would show up, barring left-right reflections, rotations, or up-down reflections of the same square.  It is possible I may have missed some, due to clues that seemed to be left behind by some of the successful combinations. And I only considered pairings of sequential numbers, not just any pairings of numbers, of which there are (16 × 15)/2 = 120 combinations.

First, the combinations of sequential numbers that were NOT successful: “3  4”, “7  8”, “9  10”, “11  12” and “13  14”. Finding these pairs next to each other resulted in nothing output in all of the ways they might show up that I’ve tried. This is likely not the true situation, since when I tried “5  6”, only one unique square was found (and no others); while an attempt to try the famous Durer pun “1514” on two adjacent squares resulted in nothing until I moved the “15  14” to the centre columns of the top row. No other unique solutions were found for the Durer pun. None at all.

If a programmer were serious to find such “rare” solutions, then he or she would not consider ignoring these sequential pairs. On the other hand, if missing a half dozen or so squares is not important, then one is wise to look for these sequences in a row or column and abandon all such squares to save time, rather than making a square that is destined to fail.

In fact, it would be worth considering to check for these pairings before checking for “magic”, although both the pairings and magic can be done on-the-fly, during construction as a way of bailing out early and moving on.

All other successful pairings:

• 1 2, and 2 3 both gave generous numbers of squares
• 4 5: gave patterns reminiscent of the Durer square
• 5 6: only 1 square was found in my trials
• 6 7, 8 9, 10 11, 12 13: all gave generous numbers of squares
• 14 15: only worked if these numbers appeared in the middle columns of the top row (means that the bottom row and both left and right sides should work also; in addition, the “15 14” combination should work in the same way) (11 solutions)
• 15 16: Gave a few solutions, but only in the first and second cells of the first row, as far as I can tell.

Obviously, the five “failed” pairings given above are not the whole picture. Of the 120 possible pairs of numbers between 1 and 16 that can exist, there are obviously more pairs that would result in no square being formed, thus saving more time.

Recreational Math I: Magic Squares: the “really good” kind – Part 4

How to Make a Random Square

I have noticed that it has been difficult to elucidate a method for systematically creating even-ordered magic squares of any but the most basic kind. I don’t know why this is, since the art has been alive in Europe for at least 600 years, and probably longer in other cultures. There are a few methodologies out there, but they are perfunctory. Such as, this method offered by Reichmann (1957), which tells us little more than to write the numbers down from 1 to 16 and reverse the order of the diagonals:

``` 1  2  3  4        16  2  3 13
5  6  7  8  ====>  5 11 10  8
9 10 11 12         9  6  7 12
13 14 15 16         4 14 15  1
```

Well, only a limited number of magic squares are possible that way. You can reverse the order of the numbers, or write the numbers in order down the columns instead of the rows, followed by a similar reversal of the diagonals (these would not be considered to be unique solutions, since these methods amount to mirroring or rotating the square).

After some playing around with known 4×4 magic squares (thanks to the thorough resource offered here), and using some simple rules, I think I may have come upon a method on my own. I would suppose that it could not generate all magic squares possible, but I don’t intend to offer a complete solution. I estimate that I would be able to generate maybe another 10 or so magic squares with this method. The intent here is to allow the reader to create a 4×4 magic square sitting down at a table with little more than pencil and paper. I am sure this methodology is published elsewhere, but I wasn’t able to come up with anything.

I just have a few simple rules in coming up with the method. First of all, all of the 16 numbers are the result of a sum of two smaller numbers a and b, where a is a number from 1 to 4 such that a = {1, 2, 3, 4}, and b is a multiple of 4: b = {0, 4, 8, 12}. All 16 unique numbers generated will be the result of adding a number from set a to a number in set b.

The numbers 1, 2, 3 and 4 are the result of adding set a to 0 in set b.

The numbers 5, 6, 7, 8 come from adding set a to 4 in set b.

The numbers 9, 10, 11, 12 come from adding set a to 8 in set b.

And the numbers 13, 14, 15, 16 come from adding set a to 12 in set b.

My solution is inspired by Reichmann’s (1957) work on odd-ordered matrices. This solution on even-ordered matrices is quite different than for odd-ordered matrices, but the idea of adding two matrices and getting a magic square appealed to me, so I went with that basic idea.

The first matrix uses numbers from set a, in the following pattern:

```4  3  2  1
1  2  3  4
1  2  3  4
4  3  2  1
```

These numbers may be randomized, but I’ll just stick to numeric order for now. The second matrix is composed of the numbers of set b arranged in a pattern reminiscent of the Durer square:

```12  0  0 12
4  8  8  4
8  4  4  8
0 12 12  0
```

The sum of the two matrices has all the magic of the Durer square, and consist of the unique numbers 1 to 16:

```16  3  2 13
5 10 11  8
9  6  7 12
4 15 14  1
```

In fact, it is the Durer square itself. Now that we know it works, what about mixing things up? Take note of the patterns. Let the first matrix represent numbers {a, b, c, and d} belonging to set a; and {e, f, g, and h} belonging to set b. whatever randomization is chosen, the numbers must fit the following scheme:

```a  b  c  d      e  h  h  e
d  c  b  a      f  g  g  f
d  c  b  a   +  g  f  f  g
a  b  c  d      h  e  e  h
```

a, b, c, and d may be any permutation of the numbers 1 to 4, without apparent limitation. The second and third rows on teh first matrix are the reversals of the first and fourth. The second matrix, however is much more restricted. Considering e and f to be one pair; g and h to be another pair: 12 can only be paired on the same row with 0; and 4 only be paired with 8. Otherwise, no joy.

So, on with a randomized square: let a = {3, 1, 4, 2} and b = {8, 0, 12, 4}

```3  1  4  2     8  4  4  8     11  5  8 10
2  4  1  3     0 12 12  0      2 16 13  3
2  4  1  3  + 12  0  0 12  =  14  4  1 15
3  1  4  2     4  8  8  4      7  9 12  6
```

What about a = {2, 4, 1, 3}, and b = {4, 12, 0, 8}

```2  4  1  3      8  4  4  8     10  8  5 11
3  1  4  2     12  0  0 12     15  1  4 14
3  1  4  2  +   0 12 12  0  =   3 13 16  2
2  4  1  3      4  8  8  4      6 12  9  7
```

You may also treat sets a and b oppositely, while randomizing. This time the restriction is on matrix a — 4 pairs with 1, and 2 pairs with 3:

```3  2  2  3     8 12  0  4     11 14  2  7
4  1  1  4     4  0 12  8      8  1 13 12
1  4  4  1  +  4  0 12  8  =   5  4 16  9
2  3  3  2     8 12  0  4     10 15  3  6
```

The reason I say these squares are limited to about 10 or so, is because as you can see, the individual rows or columns end up being about the same — at best, a shuffling or reversal the same rows found in the Durer square. There are at best 24 such squares, not subtracting tilted (squares the same when laid on its side) or reflected squares (where the squares are mirror images of each other). All that might be said, is that we may have discovered all the ways a magic square may be constructed with the same “hyper-magic” as the Durer square, which may be a pretty cool thing to say actually. It’s just that my goal was more ambitious at the start. I will refer to the set of 4×4 hypermagic squares built on the same rules as “the Durer series.”

Any known magic square, however, is the result of a unique combination of the basic squares built on sets a and b. Respectively, I will call the matrices A and B.  This allows us to work backwards from a 4×4 square we know is magic, and discern any patterns. The above squares were done that way. What patterns can be observed for the following square, which this website offers as #379 out of 900 or so others?

```                Matrix "A"      Matrix "B"
13 12  6  3     1  4  2  3     12  8  4  0
10  5 11  8     2  1  3  4      8  4  8  4
7 16  2  9  =  3  4  2  1  +   4 12  0  8
4  1 15 14     4  1  3  2      0  0 12 12```

One may discern a pattern here, but it is not all that obvious, especially for the square built on set b. It doesn’t seem to resolve itself into simple rules and patterns the way the Durer series of squares did. Also, you might have noticed that this square is not quite as “magic” as the Durer series, though all rows, columns, and both diagonals give you 34.

But I do notice that in matrix A the last column is a reversal of pairs of the first column. Also, the third column is built on the middle numbers of the first column, and the second column are built on the middle numbers of the last column.

What of Matrix B? The first and last columns are reversals (of all 4 numbers, not of pairs), the second and third both start with the middle two numbers, then first, then last from their adjacent end columns: “e f g h” becomes: “f g e h”.

When I tried to build on these rules, I got duplicate numbers in my squares (and with that, some missing numbers). It would appear that the observable number patterns in such squares are limited to getting you maybe 4 to 8 unique squares, then you have to make a new set of rules each time. With over 900 squares discovered (give or take a duplicate or two), that’s a lot of rules. The total number of 4×4 squares, both magic and not, are equal to 16! = 21 trillion possible squares. Finding all possible magic squares, weeding out any duplicates, reflections, and sideways duplicates would seem a tad non-trivial. Even at the website I referred to for these squares, it has been shown that the number “924” claimed as the number of possible 4×4 magic squares, might be too high, due to some duplicates found. Their scripts took just under 25 seconds to generate and check these squares — but just to check them for magic, less so for duplication, which sounds like it would take more computer time.

Recreational Math I: Magic Squares: the “really good” kind – Part 3

Notice that to show the rules for making these kind of magic squares, I used only odd-ordered square matrices as examples. What about matrices of even numbers of rows and columns? The rules for these vary.

The famous Durer magic square, with the year of the engraving cleverly made a part of a magic square, has a certain organization in its construction, as well as a certain symmetry. The numbers are constructed, in sequence:

```_   3   2   _        _   3   2   _
_   _   _   _        5   _   _   8
_   _   _   _  ====> _   6   7   _
4   _   _   1        4   _   _   1

_   3   2   _       16   3   2  13
5  10  11   8        5  10  11   8
9   6   7  12  ====> 9   6   7  12
4   _   _   1        4  15  14   1```

So, you start from the bottom right and proceed in a horseshoe to the top then the bottom left. The next diagram places the numbers 5-8 in a pattern that is left-to-right u-shape. Then the same u-shape for the numbers 9-12 from left to right, except this time it’s upside-down. Finally ending as we started, the same horseshoe shape (except right side up) from right to left.

Durer’s square has many things about it, apart from its magic number (34) which works on all the attendant diagonals, rows and columns. The middle 4 squares add up to 34 (10 + 11 + 6 + 7 = 34); the four corners add to 34 (16 + 13 + 4 + 1 = 34), and all corner foursomes add to 34: (16 + 3 + 5 + 10); (2 + 13 + 11 + 8); (9 + 6 + 4 + 15); and (7 + 12 + 14 + 1).

The numbers at the ends of the two middle rows add to 34:

```16   3   2  13
5  10  11   8
9   6   7  12
4  15  14   1
```

and the numbers at the tops and bottoms of the two middle columns add to 34:

```16   3   2  13
5  10  11   8
9   6   7  12
4  15  14   1
```

If we take another symmetrical combination: a rightward-slanting rectangle whose corners are 2, 8, 9, and 15, these also add to 34:

```16   3   2  13
5  10  11   8
9   6   7  12
4  15  14   1
```

The leftward-slanting rectangle, whose corners are 5, 3, 12, and 14 also add to 34:

```16   3   2  13
5  10  11   8
9   6   7  12
4  15  14   1```

Starting from 2 and proceeding in an “L”-shape to the left to the number 5, and continuing counter-clockwise in the same manner gets us the corners of a tilted square whose numbers 2, 5, 15, and 12, add to 34:

```16   3   2  13
5  10  11   8
9   6   7  12
4  15  14   1```

Starting from “3” and doing likewise yields the numbers 3, 9, 14, and 8, also adding to 34:

```16   3   2  13
5  10  11   8
9   6   7  12
4  15  14   1```

And what about this talk about “symmetry”? By this, we mean that we may take pairs of numbers at the start and end of any row, and they add up to the same number in a symmetrical place elsewhere. 16 + 3 = 4 + 15, taking the top and bottom of the first and second column. Likewise can be done for the last two columns: 2 + 13 = 14 + 1. The middle two rows have the same property: 5 + 10 = 9 + 6; and 11 + 8 = 7 + 12. On a larger scale, the sums of the middle two rows of columns 1 and 2 are the same as the tops and bottoms of columns 3 and 4: 11 + 8 = 7 + 12 = 16 + 3 = 4 + 15. Likewise, the sums of the middle two rows of columns 3 and 4 are the same as the tops and bottoms of columns 1 and 2: 2 + 13 = 14 + 1 = 5 + 10 = 9 + 6. These two groups of symmetrical numbers are illustrated below in red and green:

```16   3   2  13
5  10  11   8
9   6   7  12
4  15  14   1```

The sums of 15 (green) and 18 (red) across each row form this pattern

```16   3   2  13
5  10  11   8
9   6   7  12
4  15  14   1```

The downward symmetry is also interesting. Here, the sum of 25 is in gold and the sum of 9 is in blue. In the process, we can discern the patterns that we used to construct the square in the first place:

```16   3   2  13
5  10  11   8
9   6   7  12
4  15  14   1```

This is an incredible amount of magic, but if you follow the order of filling (horseshoes are right-to-left, u-shapes are left-to-right, along with the peculiar pattern of filling u’s and horseshoes), there really are four possible patterns that have these “hyper-magic” qualities, but you lose the “1514” idea in two of them:

``` 8  11  10   5      12   7   6   9       4  15  14   1
13   2   3  16       1  14  15   4      12   6   7   9
1  14  15   4      13   2   3  16       5  11  10   8
12   7   6   9       8  11  10   5      16   3   2  13
```

Of course, you could reverse all of the numbers in the rows of the first two squares to get your “1514” back.

Every time I look at that darned Durer square, I keep seeing more patterns. I think there comes a point where one has to leave the remaining observations up to the reader.

There is yet another 4×4 square, and with it we can increase the magic, if that can even be conceivable after all I have said. But there is a square with even more magic than the Durer square. R. J. Reichmann mentioned it in his book “The Fascination of Numbers”, first published in 1957. The square could be constructed like this:

```-   -   3   -        -   -   3   6        -  10   3   6        15  10   3   6
4   -   -   - ====>  4   5   -   - ====>  4   5   -   9  ====>  4   5  16   9
-   -   2   -        -   -   2   7        -  11   2   7        14  11   2   7
1   -   -   -        1   8   -   -        1   8   -  12         1   8  13  12
```

This square has all the magic of the Durer square and then some. One thing this new square has over the Durer square is that any four numbers in square formation will add to 34, from anywhere in the square. These include the foursomes:

```10  3     16   9     11   2       4   5
5  16      2   7      8  13      14  11
```