Magic square with odd-sized sides¶
A magic square of size $N \times N$ is a matrix filled with integers from 1 to $N^2$ such that the sum of the numbers along each row, each column and the main diagonals is the same and equals $N(N^2 + 1)/2$.
Algorithm for solving the problem¶
Siamese method of filling a magic square of size $N$ (where $N$ is an odd number) consists of the following steps:
- Select a cell in the middle of the top row, accept the cell $n=1$
- Place $n$ in the selected cell
- If $n = N^2$, then the square is filled and you can exit the procedure. Otherwise increase $n$ by one
- Move to the cell above and to the right of the current cell. Move to the first column or to the last row when moving outside the matrix. If the new cell is already filled with a non-zero number, return and shift 1 cell lower (vertically) instead.
- Return to step 2
Pkg.add(["Colors", "LinearAlgebra"])
N = 7
magic_square = Matrix{Int}(zeros(N,N))
n = 1
i = 1
j = N ÷ 2
while n <= N^2
magic_square[i, j] = n
n += 1
newi, newj = mod1((i-1), N), mod1((j+1), N)
if magic_square[newi, newj] > 0
i = mod1( i+1, N )
else
i, j = newi, newj
end
end
display( magic_square )
gr()
heatmap( magic_square, c=:Greens, size=(200,200), cbar=:false,
xticks=false, yticks=false )
# Вычислим координаты, текст и цвет надписей
vec_coords = CartesianIndices( size(magic_square) )
ax = first.( Tuple.(vec_coords[:]) )
ay = last.( Tuple.(vec_coords[:]) )
az = reshape( magic_square, 1, : )
acol = [ n > (N^2)÷2 ? (:white) : (:black) for n in az ]
# Нанесем на график надписи
for (x,y,z,c) in zip(ax,ay,az,acol)
annotate!( x, y, text("$(convert(Int64, round(z)))",9,"Helvetica",c) );
end
plot!()
Let's check that we got exactly the magic square. Here is the sum of all columns:
sum.( eachcol( magic_square ) )
The sum of all rows:
sum.( eachrow( magic_square ) )
Sum of the numbers on the main diagonal:
using LinearAlgebra
sum( diag( magic_square) )
Sum of the numbers on the side diagonal:
sum( diag( magic_square') )
Let's check all the conditions at once:
using Colors
verdict = all( vcat( sum.( eachcol( magic_square ) ),
sum.( eachrow( magic_square ) ),
sum( diag( magic_square) ),
sum( diag( magic_square') ) ) .== N*(N^2 + 1) ÷ 2 )
if verdict == true display( colorant"green" ) else display( colorant"red" ); end;
If we set an even value $N$, these conditions will not be fulfilled (the result will be false
).
Conclusion¶
We have implemented a procedure for constructing a magic square with some limitations. It embodies a rather simple algorithm, and learning it is definitely useful for cultivating intuition in programming.