Документация Engee
Notebook

Магический квадрат с нечетным размером сторон

Открыть пример в Engee

Магический квадрат размером $N \times N$ – это матрица, заполненная целыми числами от 1 до $N^2$ таким образом, чтобы сумма чисел вдоль каждой строки, каждого столбца и главных диагоналей были одинаковыми и равнялись $N(N^2 + 1)/2$.

Алгоритм решения задачи

Сиамский метод заполнения магического квадрата размера $N$ (где $N$ нечетное число) состоит из следующих шагов:

  1. Выбрать ячейку в середине верхнего ряда, принять $n=1$
  2. Разместить $n$ в выбранной ячейке
  3. Если $n = N^2$, значит квадрат заполнен и можно выходить из процедуры. Иначе увеличить $n$ на единицу
  4. Сместиться в ячейку, находящуюся выше и правее текущей. Перейти в первый столбец или в последнюю строку при выходе за пределы матрицы. Если новая ячейка уже заполнена ненулевым числом, вернуться и вместо этого сместиться на 1 клетку ниже (по вертикали).
  5. Вернуться к шагу 2
In [ ]: 
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 )

7×7 Matrix{Int64}:
 39  48   1  10  19  28  30
 47   7   9  18  27  29  38
  6   8  17  26  35  37  46
 14  16  25  34  36  45   5
 15  24  33  42  44   4  13
 23  32  41  43   3  12  21
 31  40  49   2  11  20  22
In [ ]: 
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!()
Out[0]:
39 47 6 14 15 23 31 48 7 8 16 24 32 40 1 9 17 25 33 41 49 10 18 26 34 42 43 2 19 27 35 36 44 3 11 28 29 37 45 4 12 20 30 38 46 5 13 21 22

Проверим, что мы получили именно магический квадрат. Вот сумма по всем столбцам:

In [ ]: 
sum.( eachcol( magic_square ) )
Out[0]:
7-element Vector{Int64}:
 175
 175
 175
 175
 175
 175
 175

Сумма по всем строкам:

In [ ]: 
sum.( eachrow( magic_square ) )
Out[0]:
7-element Vector{Int64}:
 175
 175
 175
 175
 175
 175
 175

Сумма чисел на главной диагонали:

In [ ]: 
using LinearAlgebra
sum( diag( magic_square) )
Out[0]:
175

Сумма чисел на побочной диагонали:

In [ ]: 
sum( diag( magic_square') )
Out[0]:
175

Проверим все условия сразу:

In [ ]: 
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;
No description has been provided for this image

Если мы зададим четное значение $N$, эти условия не будут выполняться (результат будет false).

Заключение

Мы реализовали процедуру построения магического квадрата с некоторыми ограничениями. Она воплощает довольно простой алгоритм, и его изучение определенно полезно для воспитания интуиции в области программирования.