幻方（Magic Square）是一种将数字安排在正方形格子中，使每行、列和对角线上的数字和都相等的方法。这里简单记录下n阶幻方的生成算法，想要了解更多可以去百度百科。
n阶幻方具体可分为奇数阶幻方，4n阶幻方以及4n+2阶幻方
奇数阶幻方
阶数为奇数的幻方，最经典的填法是罗伯法，步骤可以总结为七言绝句：
image.png
后面两句其实我也没看懂。。。不过没关系，只看前两句照样可以填出幻方，这里稍微解释一下：
image.png
如上图所示（忽略丑感），1填在第一行正中央，然后按阶数n斜填，超顶就回到底，超底就会到顶。填完一斜往下挪一位，元素+1，再重复上述步骤。用Lua代码实现如下：
-- @params number n：n阶方阵的阶数
-- @params table tMatrix：n阶方阵的元素，默认是连续递增的整数
function OddMagicSquare(n, tMatrix)
if not tMatrix then --不存在则从1开始赋值
tMatrix = {}
for nRow = 1, n do
tMatrix[nRow] = {}
for nCol = 1, n do
tMagicSquare[nRow][nCol] = (nRow - 1) * n + nCol --顺序赋值
end
end
end
local tMagicSquare = {}
for nRow = 1, n do
tMagicSquare[nRow] = {}
end
-- 罗伯法
-- 先填上行正中央，
-- 依次斜填切莫忘。
-- 上格没有顶格填，
-- 顶格没有底格放。
local nMidCol = (n + 1) / 2
tMagicSquare[1][nMidCol] = tMatrix[1][1]
local function _HandleOutData(nValue)
if nValue < 1 then nValue = n end
if nValue > n then nValue = 1 end
return nValue
end
local nRow = 1
local nCol = nMidCol
local nCount = 1
for i = tMatrix[1][2], tMatrix[n][n] do
nCount = nCount + 1
if nCount > n then --n次之后进行下一轮
nCount = 1
nRow = nRow + 1
else
nRow = nRow - 1
nCol = nCol + 1
end
nRow = _HandleOutData(nRow)
nCol = _HandleOutData(nCol)
tMagicSquare[nRow][nCol] = i
end
return tMagicSquare
end
为什么要传一个矩阵参数？当然是为了后面做准备。
4n阶幻方
即阶数为4的倍数。这类幻方可由海尔法得到，有两个步骤：
1. 先把数字按顺序填。然后，按4×4分割
2. 每个小方阵对角线上的数字换成，大方阵中和它中心对称的位置的数
挺简单明了的，具体的图就不贴了，可以在后面的参考中看，有具体的图。
Lua实现如下：
-- 海尔法：
-- 先把数字按顺序填。然后，按4×4分割
-- 每个小方阵对角线上的数字换成，大方阵中和它中心对称的位置的数
-- @params number n：n阶方阵的阶数
function DoubleEvenMagicSquare(n)
local tMagicSquare = {}
for nRow = 1, n do
tMagicSquare[nRow] = {}
for nCol = 1, n do
tMagicSquare[nRow][nCol] = (nRow - 1) * n + nCol --顺序赋值
end
end
local nSum = n*n + 1 --顺序排列且中心对称，相加等于定值
local nRow, nCol
for i=1,n,4 do
for j=1,n,4 do
for k=0,3 do
nRow = i+k
nCol = j+k
tMagicSquare[nRow][nCol] = nSum - tMagicSquare[nRow][nCol]
nCol = j+3-k
tMagicSquare[nRow][nCol] = nSum - tMagicSquare[nRow][nCol]
end
end
end
return tMagicSquare
end
4n+2阶幻方
阶数为偶数且非四的倍数，算是最难处理的一种了。可以用斯特拉兹法生成，分为三个步骤：
1. 分为四个同阶的奇数阶，由小到大依次为上左子阵（i），下右子阵（i+v），上右子阵（i+2v)，下左子阵（i+3v），4个子方阵对应位置元素相差v，其中v=n*n/4，然后按罗伯法处理。
2. 上左、下左两个方阵，从中间行、中间格开始，按自左向右的方向，标出K格；其它行则标出最左边的K格。交换两个方阵标出来的数字。如图：
image.png
3. 上右、下右两个方阵，从中间列开始，自右向左，标出K-1格（K等于1不作处理）交换两个方阵标出来的数字。如图：
image.png
Lua代码实现如下：
-- 斯特拉兹法
-- 1.分为四个同阶的奇数阶，由小到大依次为上左子阵（i），下右子（i+v），上右子阵（i+2v)，下左子阵（i+3v），
-- 即4个子方阵对应元素相差v，其中v=n*n/4。然后按罗伯法处理
-- 2.4K+2阶幻方，求出K。
-- 3.上左、下左两个方阵，从中间行、中间格开始，按自左向右的方向，标出K格；其它行则标出最左边的K格。交换两个方阵标出来的数字
-- 4.上右、下右两个方阵，从中间列开始，自右向左，标出K-1格。交换两个方阵标出来的数字
function SingleEvenMagicSquare(n)
local tMagicSquare1 = {}
local tMagicSquare2 = {}
local tMagicSquare3 = {}
local tMagicSquare4 = {}
local nSubLen = n/2
local nDiffValue = n*n/4
local nFirstMatrixValue
for nRow=1,nSubLen do
tMagicSquare1[nRow] = {}
tMagicSquare2[nRow] = {}
tMagicSquare3[nRow] = {}
tMagicSquare4[nRow] = {}
for nCol=1,nSubLen do
nFirstMatrixValue = (nRow - 1) * nSubLen + nCol
tMagicSquare1[nRow][nCol] = nFirstMatrixValue
tMagicSquare2[nRow][nCol] = nFirstMatrixValue + 2*nDiffValue
tMagicSquare3[nRow][nCol] = nFirstMatrixValue + 3*nDiffValue
tMagicSquare4[nRow][nCol] = nFirstMatrixValue + nDiffValue
end
end
tMagicSquare1 = OddMagicSquare(nSubLen, tMagicSquare1)
tMagicSquare2 = OddMagicSquare(nSubLen, tMagicSquare2)
tMagicSquare3 = OddMagicSquare(nSubLen, tMagicSquare3)
tMagicSquare4 = OddMagicSquare(nSubLen, tMagicSquare4)
local nKey = (n-2)/4
local nSubMidSide = (nSubLen + 1) / 2
local nTemp
-- 步骤3
for nCol = nSubMidSide, nSubMidSide + nKey - 1 do
nTemp = tMagicSquare1[nSubMidSide][nCol]
tMagicSquare1[nSubMidSide][nCol] = tMagicSquare3[nSubMidSide][nCol]
tMagicSquare3[nSubMidSide][nCol] = nTemp
end
for nRow = 1, nSubLen do
if nRow ~= nSubMidSide then
for nCol = 1, nKey do
nTemp = tMagicSquare1[nRow][nCol]
tMagicSquare1[nRow][nCol] = tMagicSquare3[nRow][nCol]
tMagicSquare3[nRow][nCol] = nTemp
end
end
end
-- 步骤4
if nKey > 1 then
for nRow = 1, nSubLen do
for nCol = nSubMidSide, nSubMidSide - (nKey - 2), -1 do
nTemp = tMagicSquare2[nRow][nCol]
tMagicSquare2[nRow][nCol] = tMagicSquare4[nRow][nCol]
tMagicSquare4[nRow][nCol] = nTemp
end
end
end
local tMagicSquare = {}
for nRow = 1, n do
tMagicSquare[nRow] = {}
for nCol = 1, n do
if nRow <= nSubLen and nCol <= nSubLen then
tMagicSquare[nRow][nCol] = tMagicSquare1[nRow][nCol]
elseif nRow <= nSubLen and nCol > nSubLen then
tMagicSquare[nRow][nCol] = tMagicSquare2[nRow][nCol - nSubLen]
elseif nRow > nSubLen and nCol <= nSubLen then
tMagicSquare[nRow][nCol] = tMagicSquare3[nRow - nSubLen][nCol]
else
tMagicSquare[nRow][nCol] = tMagicSquare4[nRow - nSubLen][nCol - nSubLen]
end
end
end
return tMagicSquare
end
上面OddMagicSquare的矩阵参数就是给这里用的。
网友评论