關(guān)于構(gòu)造任意奇數(shù)階幻方的新方法

周小安+趙宇

摘要： 關(guān)鍵詞： 中圖分類號(hào)： 文獻(xiàn)標(biāo)志碼： A文章編號(hào)： 2095-2163

Abstract： Magic square originated thousands of years ago in China，which is one of the research objects of combinatorial designs. In a square matrix，if the sums of every row，every column and two diagonals are equal， this square matrix is called magic square. Currently， the achievements in the research of magic square have been widely used in image encryption，image scrambling，etc. This paper introduces a new continuous numbering method to structure arbitrary odd order magic square，which is more flexible than traditional construction methods.The new method can not only increase the forms of odd order magic square， but also parallelly structure magic square and reduce the time of structuring it.

0引言

幻方具有非常悠久的歷史，雖然古老但卻是最流行的數(shù)字游戲之一。一個(gè)n階幻方的構(gòu)造方法是將整數(shù)1、2、3、…、n2共n2個(gè)連續(xù)自然數(shù)，填入到n × n的方陣中，使得每行、每列以及每條對(duì)角線上的數(shù)字之和都等于同一個(gè)常數(shù)。幻方是組合設(shè)計(jì)的重要研究對(duì)象之一[1]。

《易經(jīng)》中記載的洛書(shū)是世界上最早的幻方，之后幻方逐漸傳入世界各地，引起了廣泛關(guān)注，并在許多方面取得了研究成果?；梅娇蓱?yīng)用于哲理思想的研究、美術(shù)設(shè)計(jì)、智力開(kāi)發(fā)、科學(xué)技術(shù)等方面[2]。尤其是在科學(xué)技術(shù)中，隨著計(jì)算機(jī)的快速發(fā)展，幻方在信息隱藏[3]、數(shù)字圖像[4]、認(rèn)證與加密[5-6]、量子信息[7]等方面應(yīng)用前景十分廣闊。

1使用改進(jìn)的連續(xù)擺數(shù)法構(gòu)造奇數(shù)階幻方

1.1連續(xù)擺數(shù)法

連續(xù)擺數(shù)法是較為古老的幻方構(gòu)造方法，適用于奇數(shù)階幻方的構(gòu)造，一般把數(shù)字1放在幻方中第一行最中間的方格中，然后從這里開(kāi)始，按對(duì)角線方向（比如說(shuō)按從左下到右上的方向）把其余各數(shù)按從小到大的順序依次放入其它格子中，如果到達(dá)頂部，則轉(zhuǎn)向底部；如果到達(dá)右側(cè)，則轉(zhuǎn)向左側(cè)；如果需要放入的格子中已經(jīng)有數(shù)存在或者到達(dá)了右上角，則需要退至前一格的下方[1]。

按照上述法則建立的5階幻方如圖1所示。

這個(gè)方法可以推廣到一般情況，即起始數(shù)1不一定要放在第一行的中間，而下一個(gè)數(shù)字也不一定要放在上一個(gè)數(shù)的右上方格中，為此本文提出了改進(jìn)的連續(xù)擺數(shù)法來(lái)構(gòu)造奇數(shù)階幻方。

1.2改進(jìn)的連續(xù)擺數(shù)法

1.2.1算法設(shè)計(jì)步驟

改進(jìn)的連續(xù)擺數(shù)法構(gòu)造n階幻方的步驟如下：

步驟1以奇數(shù)階幻方中心位置為坐標(biāo)原點(diǎn)，建立坐標(biāo)系；

步驟2將幻方中任意一格的位置用坐標(biāo)來(lái)表示，坐標(biāo)范圍從（-n-12，-n-12）到（n-12， n-12）；

步驟3定義“起始向量”，表示1的位置；

步驟4定義“偏移向量”，表示一個(gè)數(shù)的位置到下一個(gè)數(shù)位置所指的方向，依次按順序填寫(xiě)其它數(shù)字；

步驟5當(dāng)遇到要填入的格子中已經(jīng)被其它數(shù)字占據(jù)，用“中斷向量”重新計(jì)算該數(shù)字的坐標(biāo)并填入計(jì)算后的空格；

步驟6重復(fù)步驟4和步驟5，直到所有數(shù)字均填入方格中。

1.2.2算法設(shè)計(jì)過(guò)程

這里，下面將詳述給出改進(jìn)連續(xù)擺數(shù)法構(gòu)造5階幻方的過(guò)程。先以5階幻方中心位置為坐標(biāo)原點(diǎn)，建立坐標(biāo)系，每一點(diǎn)的坐標(biāo)如圖2所示。

接著確定1的位置，連續(xù)擺數(shù)法是基于對(duì)稱性的方法，即以5階幻方為例，1～25的中間數(shù)字是13，所以假設(shè)要讓13固定在幻方的中心點(diǎn)，那么1就只能選擇除中心點(diǎn)外的其它位置。為此，研究定義一個(gè)起始向量（x0，y0），表示1的起始位置，x0、y0滿足條件（x0，y0） ≠ （0，0）。

確定好1的位置后，還需要定義一個(gè)偏移向量（u，v），表示一個(gè)數(shù)的位置到下一個(gè)數(shù)位置所指的方向。當(dāng)然，偏移向量的選擇在理論上可以是任意的，但是卻需要滿足如下條件：

首先，u和v都不能等于0，否則無(wú)法產(chǎn)生偏移；其次，必須要保證（1+n2）/2固定在幻方的中心點(diǎn)，那么選取偏移向量時(shí)就要避免讓（1+n2）/2之前的數(shù)字占據(jù)中心位置，就需要據(jù)此原理求解數(shù)個(gè)特征方程，這里暫時(shí)不考慮這個(gè)問(wèn)題。至此，研究將針對(duì)起始向量和偏移向量展開(kāi)全面的分析論述。

假設(shè)階數(shù)n=5，起始向量（x0，y0） = （0，-1），偏移向量（u，v） = （2，1），那么1的位置如圖3所示，2的坐標(biāo)由1的坐標(biāo)加上偏移向量所得，即（0，-1） + （2，1） = （2，0），將2填入到圖3中對(duì)應(yīng)位置，3、4、5采用相同的方法依次填入。需要說(shuō)明的是，3的坐標(biāo)由2的坐標(biāo)加上偏移向量所得，即（2，0） + （2，1） = （4，1），在幻方中顯然沒(méi)有對(duì)應(yīng)的坐標(biāo)存在，這里需要把超出范圍的坐標(biāo)進(jìn)行“模n加”運(yùn)算使該坐標(biāo)在該幻方中尋得對(duì)應(yīng)位置。具體來(lái)說(shuō)，就是坐標(biāo)（4，1）的橫坐標(biāo)超出范圍，將（4，1） - （5，0） = （-1，1），于是找到3在幻方中的位置，填入圖3中。對(duì)4和5的處理也采取和3類似的方式。endprint

下一步就是確定6的位置。無(wú)論是從計(jì)算6的坐標(biāo)位置還是從圖3直接來(lái)看，研究發(fā)現(xiàn)不管起始向量和偏移向量的取值是多少，理論上計(jì)算得到的6的位置上已經(jīng)有1存在了，這和連續(xù)擺數(shù)法的周期性有關(guān)。那么要想確定6的位置，必須引入一個(gè)中斷向量（xt，yt），表示發(fā)生沖突時(shí)的偏置量。具體來(lái)說(shuō)，就是將數(shù)字正準(zhǔn)備填入某一方格時(shí)，卻遭遇該方格中已存在數(shù)字的情形，這時(shí)即需改變?cè)摂?shù)字坐標(biāo)的計(jì)算方法，將中斷向量代替偏移向量，重新計(jì)算該數(shù)字的坐標(biāo)。

繼續(xù)用圖3中的例子來(lái)說(shuō)明，當(dāng)用偏移向量計(jì)算得到的6的位置里已經(jīng)存在1了，這時(shí)需要將中斷向量代替偏移向量，重新計(jì)算6的坐標(biāo)，即用5的坐標(biāo)加上中斷向量。那么如何確定中斷向量的大??？

經(jīng)過(guò)推導(dǎo)可知，中斷向量的值與起始向量有關(guān)，中斷向量（xt，yt）滿足方程（1）：（xt，yt）=2×（x0，y0）（1）在該例中，（x0，y0） = （0，-1），所以（xt，yt） = （0，-2），這時(shí)計(jì)算得到的6的坐標(biāo)為5的坐標(biāo)加上中斷向量，即（-2，-2） + （0，-2） = （-2，-4），再利用“模5加”運(yùn)算得到6的坐標(biāo)為（-2，1），填入幻方中。

緊接著，繼續(xù)用偏移向量完成其后順承數(shù)字的填寫(xiě)，直到遇到下次被“占位”時(shí)才使用中斷向量。于是可以將7、8、9、10依次填入幻方中，如圖4所示。

計(jì)算該5階幻方每行、每列及對(duì)角線數(shù)字的和均為65，符合幻方的規(guī)律。

經(jīng)過(guò)嘗試和推導(dǎo)，可以將改進(jìn)的連續(xù)擺數(shù)法推廣到任意奇數(shù)階幻方，用來(lái)構(gòu)造階數(shù)更多的幻方。由于起始向量和偏移向量是隨機(jī)選取的，兩者組合后可以構(gòu)造出許多種完全不同的幻方圖樣，如果事先不知道這兩個(gè)向量，就極難復(fù)制出一樣的幻方。

2改進(jìn)連續(xù)擺數(shù)法的通項(xiàng)公式

如果從1到n2逐個(gè)去填入幻方的話，顯然可得時(shí)間復(fù)雜度即為O（n2），而且需要知道一個(gè)數(shù)的坐標(biāo)才能推算出下一個(gè)數(shù)的坐標(biāo)，所以有必要推導(dǎo)出通項(xiàng)公式，可以直接計(jì)算出一個(gè)數(shù)的坐標(biāo)，直接填入幻方中，提高構(gòu)造幻方的效率。

參考文獻(xiàn)：

[1]吳鶴齡. 幻方及其他-娛樂(lè)數(shù)學(xué)經(jīng)典名題[M]. 北京：科學(xué)出版社，2005.

[2] 高治源. 幻方的應(yīng)用前景[J]. 延安教育學(xué)院學(xué)報(bào)，2000（1）：44-46.

[3] 丁瑋，齊東旭. 數(shù)字圖像變換及信息隱藏與偽裝技術(shù)[J]. 計(jì)算機(jī)學(xué)報(bào)，1998，21（9）：838-843.

[4] ARONOV B， ASANO T， KIKUCHI Y， et al. A generalization of magic squares with applications to digital halftoning[M]//FLEISCHER R， TRIPPEN G：ISAAC 2004， LNCS 3341.Berlin/Heidelberg： Springer-Verlag， 2004：89-100.

[5] XIE T， CHEN H， KANG L. A unified method of magic square-based two-way certificate authentication and key transferring：China，02114288.2 [P].2002.

[6] XIE T. A magic square based signing method for identification and authentication：China， 200410046922.2[P].2004.

[7] RAMZAN M， KHAN M K. Distinguishing quantum channels via magic squares game[J]. Quantum Information Processing， 2010， 9（6）： 667-679.

[8] ZHANG Jie，LU Yang， YANG Shu， et al. NHPPbased software reliability model considering testing effort and multivariate fault detection rate[J]. Journal of Systems Engineering and Electronics， 2016，27（1）： 260-270.

[9] 馬颯颯，王光平，趙守偉. 基于時(shí)間序列的軟件可靠性預(yù)測(cè)模型研究[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（11）：2520-2523.

[10]賈治宇，康銳. 軟件可靠性預(yù)測(cè)的ARIMA方法研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2008，44（35）：17-19.

[11]何書(shū)元. 應(yīng)用時(shí)間序列分析[M]. 北京： 北京大學(xué)出版社，2003.

[12]黃雄波. 多周期時(shí)序數(shù)據(jù)的傅氏級(jí)數(shù)擬合算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用，2015，24（7）：142-148.

[13]黃雄波. 基于自相關(guān)函數(shù)的非平穩(wěn)時(shí)序數(shù)據(jù)的辨識(shí)改進(jìn)[J]. 微型機(jī)與應(yīng)用，2016，35（13）：10-14，18.

[14]劉思峰，楊英杰. 灰色系統(tǒng)研究進(jìn)展（2004-2014）[J]. 南京航空航天大學(xué)學(xué)報(bào)，2015，47（1）：1-18.

[15]黨耀國(guó)，王俊杰，康文芳. 灰色預(yù)測(cè)技術(shù)研究進(jìn)展綜述[J]. 上海電機(jī)學(xué)院學(xué)報(bào)，2015，18（1）：1-7，18.

[16]鄭咸義，姚仰新，雷秀仁，等. 應(yīng)用數(shù)值分析[M]. 廣州： 華南理工大學(xué)出版社，2008.

[17]李慶揚(yáng)，關(guān)治，白峰彬. 數(shù)值計(jì)算原理[M]. 北京： 清華大學(xué)出版社，2005.endprint