A magic square is an arrangement of the numbers from 1...N2 in an N x N matrix, with each number occurring exactly once, and such that the sum of the entries of any row, any column, or either main diagonal is equal to the magic constant defined as:
M2 = N·(N2 + 1)/2
The simplest magic square is the 1 x 1 magic square whose only entry is the number 1. The next simplest is the 3 x 3 magic square:
8 1 6 3 5 7 4 9 2
A technique known as the Siamese method can be used to generate magic squares with odd sizes (3, 5, 7, 9,...). It begins by placing a 1 in any location. Then, sequentially, numbers are added in squares one unit above and to the right. The process wraps around as if the square pattern repeats on all sides. When a square is encountered, which is already filled, the next number is placed below the previous one and the process continues until all squares are filled.
Another method known as the big X method constructs magic squares of doubly even order sizes (4, 8, 12, 16,...). In this method, all squares are filled in sequence. The X's are the diagonals of each 4 x 4 block of squares. The order of the entries, in these diagonals, is reversed. In an 8 x 8 magic square, the diagonal numbers are 1, 4, 5, 8,..., 60, 61, and 64; so entry 1 is replaced with 64, 4 with 61, 5 with 60, and so on.
A method known as the LUX method constructs magic squares of singly even order sizes (6, 10, 14, 18,...). For a size N, compute m = (N-2)/4. Then create a 2m+1 x 2m+1 array with m+1 rows of Ls, 1 row of Us, and m-1 rows of Xs. Interchange the middle U with the L above it. Now generate the magic square of order 2m+1 using the Siamese method applied to the array of letters (starting in the center letter of the top row), but fill each set of four squares corresponding to a lettered block by the next group of sequential digits using the pattern identified by the letter. The L, U, X patterns are:
L: 4 1 2 3 U: 1 4 2 3 X: 1 4 3 2
Zeno 1.2 is an interpreter for the Zeno programming language. It is an easy to learn and is suitable for educational purposes.
const N : int := 20
type matrix : array[N,N] of int
program
var mat : matrix
var n : int
put "size"...
get n
assert n <= N
if (n mod 2 > 0) then
odd_order( mat, n )
put "odd_order "...
elsif (n mod 4 = 0) then
doubly_even( mat, n )
put "doubly_even "...
else
singly_even( mat, n )
put "singly_even "...
end if
if is_magic( mat, n ) then
put "is magic"
else
put "failed"
end if
put_square( mat, n )
put "The sum of each row and column is ", (n*(n*n+1)) div 2
end program
% siamese method for any odd value N
procedure odd_order( var mat : matrix, N : int )
assert (N mod 2 > 0) % N must be odd
var i, j, N3, t : int
N3 := ( N - 3 ) div 2
for i := 1...N do
for j := 1...N do
t := (i + j*2 - 2) mod N
mat[i,j] := (1 + t + N*((N3 + i + j) mod N))
end for
end for
end procedure
% big X method for sizes 4, 8, 12, 16 ...
procedure doubly_even( var mat : matrix, n : int )
var i, j : int
var nsq1 : int := n*n + 1
var val : int := 0
for i := 1...n do
for j := 1...n do
incr val
if ( ( ((i div 2) mod 2 > 0) and ((j div 2) mod 2 > 0) ) or
( ((i div 2) mod 2 = 0) and ((j div 2) mod 2 = 0) ) ) then
mat[i,j] := nsq1 - val
else
mat[i,j] := val
end if
end for
end for
end procedure
% LUX method for sizes 2, 6, 10, 14 ...
procedure singly_even( var mat : matrix, N : int )
var i, j, s3, t, s, m : int
var js, is : int := 0
m := (N - 2) div 4
s := (m*2) + 1
s3 := (s - 3) div 2
for i := 1...N do
if ((i mod 2) > 0) then
incr is
end if
js := 0
for j := 1...N do
if ((j mod 2) > 0) then
incr js
end if
t := ((((is + (js*2) - 2) mod s) + s*((s3 + is + js) mod s ) ) * 4 ) + 1
if ((i mod 2) > 0) then % is top of 4-block?
if ( (is > m+2) or % is X
( (is = m+2) and (js ~= m+1) ) or % or L?
( (is = m+1) and (js = m+1) ) ) then
if (j mod 2 > 0) then
mat[i,j] := t
else
mat[i,j] := t + 3
end if
else
if (j mod 2 > 0) then
mat[i,j] := t + 3
else
mat[i,j] := t
end if
end if
else % is bottom of 4-block
if (is < m+3) then % is L or U?
if (j mod 2 > 0) then
mat[i,j] := t + 1
else
mat[i,j] := t + 2
end if
else
if (j mod 2 > 0) then
mat[i,j] := t + 2
else
mat[i,j] := t + 1
end if
end if
end if
end for
end for
end procedure
% sends square to text output
procedure put_square( var mat : matrix, n : int )
var i, j : int
for i := 1...n do
for j := 1...n do
put mat[i,j]:5...
end for
put ""
end for
end procedure
% test rows, columns, and diagonals all sum to same value
function is_magic( var mat : matrix, n : int ) : boolean
var i, j : int
var row, col, dia1, dia2 : int
var M2 : int := n*(n*n + 1) div 2
% check rows, columns, diagonals
dia1 := 0
dia2 := 0
for i := 1...n do
row := 0
col := 0
dia1 := dia1 + mat[i,i]
dia2 := dia2 + mat[n+1-i,i]
for j := 1...n do
row := row + mat[i,j]
col := col + mat[j,i]
end for
if (row ~= M2) or (col ~= M2) then
return false
end if
end for
if (dia1 ~= M2) or (dia2 ~= M2) then
return false
end if
return true
end function
size? 6 singly_even is magic 32 29 4 1 24 21 30 31 2 3 22 23 12 9 17 20 28 25 10 11 18 19 26 27 13 16 36 33 5 8 14 15 34 35 6 7 The sum of each row and column is 111
AbCd Classics - free on-line books