Магический квадрат с нечетным размером сторон¶
Магический квадрат размером N×NN×N – это матрица, заполненная целыми числами от 1 до N2 таким образом, чтобы сумма чисел вдоль каждой строки, каждого столбца и главных диагоналей были одинаковыми и равнялись N(N2+1)/2.
Алгоритм решения задачи¶
Сиамский метод заполнения магического квадрата размера N (где N нечетное число) состоит из следующих шагов:
- Выбрать ячейку в середине верхнего ряда, принять n=1
- Разместить n в выбранной ячейке
- Если n=N2, значит квадрат заполнен и можно выходить из процедуры. Иначе увеличить n на единицу
- Сместиться в ячейку, находящуюся выше и правее текущей. Перейти в первый столбец или в последнюю строку при выходе за пределы матрицы. Если новая ячейка уже заполнена ненулевым числом, вернуться и вместо этого сместиться на 1 клетку ниже (по вертикали).
- Вернуться к шагу 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!()
Проверим, что мы получили именно магический квадрат. Вот сумма по всем столбцам:
sum.( eachcol( magic_square ) )
Сумма по всем строкам:
sum.( eachrow( magic_square ) )
Сумма чисел на главной диагонали:
using LinearAlgebra
sum( diag( magic_square) )
Сумма чисел на побочной диагонали:
sum( diag( magic_square') )
Проверим все условия сразу:
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;
Если мы зададим четное значение N, эти условия не будут выполняться (результат будет false
).
Заключение¶
Мы реализовали процедуру построения магического квадрата с некоторыми ограничениями. Она воплощает довольно простой алгоритм, и его изучение определенно полезно для воспитания интуиции в области программирования.