幻方问题

幻方（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的矩阵参数就是给这里用的。

参考

由n阶幻方问题引发的思考
【算法导论】幻方算法