基于分治法搜索幻方所有解

丁怡心，廖勇毅

（廣州民航職業技術學院，廣州 510800）

0 引言

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

圖1 三階幻方

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

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

1 幻方搜索空間

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

表1 n階幻方搜索空間

2 分治窮舉法

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

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

圖2 三階幻方候選中間解

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

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

圖3 算法盒圖

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

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

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

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

圖5 三階幻方所有解

3 搜索空間對比

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

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

表2 分治窮舉法搜索空間

4 關鍵代碼

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

輸入：square方陣二維數組，n幻方維數，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遞歸函數，通過逐行排列搜索候選中間解的所有最終解。

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

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內存的電腦對兩種算法的3階、4階幻方進行測試，測試結果見表3。

表3 實驗數據對比

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

6 結語

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