奇边魔方¶
大小为$N \times N$ 的魔方是一个填满 1 到$N^2$ 整数的矩阵,使得每一行、每一列和主对角线上的数字之和相同,并且等于$N(N^2 + 1)/2$ 。
解题算法¶
连体法 填满一个大小为$N$ 的魔方(其中$N$ 是奇数),包括以下步骤:
1.选择顶行中间的一个单元格,接受该单元格$n=1$ 2.在选定的单元格中放置$n$ 3. 如果$n = N^2$ ,则正方形已填满,可以退出程序。否则将$n$ 增加 1 4.移动到当前单元格右上方的单元格。在矩阵外移动时,移动到第一列或最后一行。如果新单元格中已填入非零数字,则返回并向下(垂直)移动 1 个单元格。 5.返回步骤 2
In [ ]:
Pkg.add(["Colors", "LinearAlgebra"])
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 )
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]:
让我们检查一下我们是否得到了精确的魔方。这是所有列的总和:
In [ ]:
sum.( eachcol( magic_square ) )
Out[0]:
所有行的总和
In [ ]:
sum.( eachrow( magic_square ) )
Out[0]:
主对角线上的数字之和:
In [ ]:
using LinearAlgebra
sum( diag( magic_square) )
Out[0]:
边对角线上的数字之和:
In [ ]:
sum( diag( magic_square') )
Out[0]:
让我们同时检查所有条件:
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;
如果我们设置一个偶数值$N$ ,这些条件将无法满足(结果将是false
)。
结论¶
我们实现了一个有一定局限性的构造魔方的程序。它体现了一种相当简单的算法,学习它对培养编程直觉绝对有用。