丁怡心，廖勇毅

（廣州民航職業(yè)技術(shù)學院，廣州 510800）

0 引言

n階幻方，就是把數(shù)字1到n2但放在n×n的正方形格子中，并且要滿足每行、每列及兩個對角線數(shù)字之和相等。

圖1 三階幻方

幻方不但是傳統(tǒng)的數(shù)學游戲，還被應用到哲學、美術(shù)、教育及前沿科學技術(shù)中。對于幻方的構(gòu)造方法有很多，包括針對奇階幻方的Merzirac法與Loubere法，針對偶階幻方有Hire法、Strachey法以及YinMagic法。

幻方構(gòu)造方法的研究目前已非常成熟且成體系［2，3，4，5，6，7，8］，然而對于搜索幻方所有解的研究目前尚是空白。要搜索所有解只能通過窮舉，對于高階幻方搜索空間太大，窮舉難以實現(xiàn)或是不可能實現(xiàn)。文章研究如何降低搜索空間提高窮舉效率。

1 幻方搜索空間

n階幻方的搜索空間為n2的階乘，見表1，3階幻方的搜索空間是362880個，對于現(xiàn)代計算機是可以輕松完成的任務，然而4階以上幻方的搜索空間開始爆炸式增長，任務變得不可完成。

表1 n階幻方搜索空間

2 分治窮舉法

對于n階幻方，由于每行數(shù)之和相等，所以每行之“和”的值為所有n2個數(shù)之和除于n，即：

下面以3階幻方為例，根據(jù)公式（1），3階幻方每行數(shù)之和為15，以此為約束，從9個數(shù)中先取3個和為15的數(shù)放在第1行，再從剩下6個數(shù)中取3個和為15的數(shù)放在第2行，剩下的3個數(shù)放在第3行。如圖2所示，文章稱之為候選中間解。

圖2 三階幻方候選中間解

從9個數(shù)中取3個放在第1行，再從剩下6個數(shù)取3個放在第2行，剩下3個數(shù)放在第3行，整個過程產(chǎn)生的組合個數(shù)為C39×C36×C33，于是n階幻方產(chǎn)生的候選中間解數(shù)見公式（2）。

然后對候選中間解的每行分別進行全排列，以尋找所有滿足n階幻方條件的解。算法流程如圖3所示。

圖3 算法盒圖

根據(jù)公式（2）算得3階幻方所有組合有1680個。其中滿足每行之和相等的候選中間解有12個。

對n階幻方每個候選中間解的每行進行全排列產(chǎn)生的搜索空間為個見公式（3），則3階幻方一個候選中間解產(chǎn)生的搜索空間為3!×3!×3!=216，于是總搜索空間為12×216=2592。其中滿足3階幻方要求的最終解有8個。

算法的分治思想體現(xiàn)在把一個規(guī)模為n2的階乘分解成n個規(guī)模為n的階乘，縮小了問題的規(guī)模，減小了搜索空間。

圖4 三階幻方所有候選中間解

圖5 三階幻方所有解

3 搜索空間對比

根據(jù)分治窮舉法的算法思想，n階幻方的搜索空間大小為候選中間解數(shù)乘以每個候選中間解產(chǎn)生的搜索空間。其中每個候選中間解產(chǎn)生的搜索空間可由公式（3）算得。

通過表1與表2的對比，分治窮舉法極大地縮小了搜索空間。

表2 分治窮舉法搜索空間

4 關(guān)鍵代碼

算法1遞歸函數(shù)，通過逐行組合獲取所有候選中間解。

輸入：square方陣二維數(shù)組，n幻方維數(shù)，line行號。

a）NEXT-COMBINATION（square,n,line）

b） if SUM（square［line］）==lineSum

c） if line==n-2

d） NEXT-PERMUTATION（square,0,n）

d） else

e） NEXT-COMBINATION（square,line+1）

f） return

g） NEXT-COMBINATION（square,n,line）

算法2遞歸函數(shù)，通過逐行排列搜索候選中間解的所有最終解。

輸入：square方陣數(shù)組，start參與全排列的開始位置，end參與全排列的結(jié)束位置。

a）NEXT-PERMUTATION（square,start,end）{

b）if start==end-1//遞歸出口

c） if end

d） NEXT-PERMUTATION（square,end,end+N）

e） else if CHECK-SQUARE（square）==TRUE

f） squareCount++

g） PRINT-MAGIC-SQUARE（square）

h） return;

i）for i=start to end

j） SWAP（square,i,start）

k） NEXT-PERMUTATION（square,start+1,end）

l） SWAP（square,i,start）

5 實驗

使用配置為i5CPU/16G內(nèi)存的電腦對兩種算法的3階、4階幻方進行測試，測試結(jié)果見表3。

表3 實驗數(shù)據(jù)對比

實驗對比表明分治窮舉法確實顯著提高了搜索效率，而且問題規(guī)模越大效果越明顯。

6 結(jié)語

對于問題：搜索n階幻方的所有解。隨著n的變大搜索空間出現(xiàn)爆炸式增長，本文提出分治窮舉法，把搜索空間從n2的階乘分解成n個n的階乘，顯著地縮小了搜索空間。并通過實驗對比表明分治窮舉法極大地提高了搜索效率。