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

丁怡心，廖勇毅

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

0 引言

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

圖1 三階幻方

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

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

1 幻方搜索空間

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

表1 n階幻方搜索空間

2 分治窮舉法

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

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

圖2 三階幻方候選中間解

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

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

圖3 算法盒圖

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

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

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

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

圖5 三階幻方所有解

3 搜索空間對(duì)比

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

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

表2 分治窮舉法搜索空間

4 關(guān)鍵代碼

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

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

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ù)，通過(guò)逐行排列搜索候選中間解的所有最終解。

輸入：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 實(shí)驗(yàn)

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

表3 實(shí)驗(yàn)數(shù)據(jù)對(duì)比

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

6 結(jié)語(yǔ)

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