These are called magic squares. A magic square of order n (integers from 1 to n*n) has only one possible sum: (n*n+1)*n/2.

Odd and even order squares must be constructed by different approaches. For odd orders, the most common algorithm is a recursive scheme devised by de la Loubere about 300 years ago. For even orders, one procedure is the Devedec algorithm, which treats even orders not divisible by 4 slightly differently from those which are divisible by 4 (doubly even).

For squares with odd-length sides, the following algorithm builds a magic square:

Put 1 in the middle box in the upper row. From then on, if it's possible to put the next number one box diagonally up and to the right (wrapping around if the edge of the grid is reached), do so, otherwise, put it directly below the last one.

17 24 1 8 15 23 5 7 14 16

4 6 13 20 22

10 12 19 21 3 11 18 25 2 9

...or even

47 58 69 80 1 12 23 34 45 57 68 79 9 11 22 33 44 46 67 78 8 10 21 32 43 54 56 77 7 18 20 31 42 53 55 66

6 17 19 30 41 52 63 65 76

16 27 29 40 51 62 64 75 5 26 28 39 50 61 72 74 4 15 36 38 49 60 71 73 3 14 25 37 48 59 70 81 2 13 24 35

See archive entry knight.tour for magic squares that are knight's tours.

To get a 4x4 square, write the numbers in order across each row, filling the square...

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

then use the following pattern as a mask
. X X . X . . X X . . X . X X .

Everywhere there is an X, complement the number (subtract it from

n*n+1). For the 4x4 you get
1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16

For n even (n>4):

Make an initial magic square by writing an n/2 magic square four times (the same one each time). Now, although this square adds up right we have the numbers 1 to n*n/4 written four times each. To fix this, simply add to it n*n/4 times one of the following magic squares:

if n/2 is odd (example: n/2=7),

3 3 3 0 0 0 0 2 2 2 2 2 1 1 (there are int(n/4) 3s, int(n/4-1) 1s on each 3 3 3 0 0 0 0 2 2 2 2 2 1 1 row) 3 3 3 0 0 0 0 2 2 2 2 2 1 1 0 3 3 3 0 0 0 2 2 2 2 2 1 1 (this is row int(n/4)+1. It starts with just 3 3 3 0 0 0 0 2 2 2 2 2 1 1 the one 0) 3 3 3 0 0 0 0 2 2 2 2 2 1 1 3 3 3 0 0 0 0 2 2 2 2 2 1 1 0 0 0 3 3 3 3 1 1 1 1 1 2 2 (the lower half is the same as the upper half 0 0 0 3 3 3 3 1 1 1 1 1 2 2 with 3<->0 and 1<->2 swapped. This guarantees 0 0 0 3 3 3 3 1 1 1 1 1 2 2 that each number 1-n*n will appear in the 3 0 0 0 3 3 3 1 1 1 1 1 2 2 completed square) 0 0 0 3 3 3 3 1 1 1 1 1 2 2 0 0 0 3 3 3 3 1 1 1 1 1 2 2 0 0 0 3 3 3 3 1 1 1 1 1 2 2

if n/2 is even (example: n/2=4),

0 0 3 3 2 2 1 1 (there are n/4 of each number on each row) 0 0 3 3 2 2 1 1 0 0 3 3 2 2 1 1 0 0 3 3 2 2 1 1 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2

References

"Magic Squares and Cubes" W.S. Andrews The Open Court Publishing Co. Chicago, 1908

"Mathematical Recreations" M. Kraitchik Dover New York, 1953

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access