==> arithmetic/magic.squares.s <==
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