基于t進(jìn)制Morse睭edlund序列的奇數(shù)階魔方求解算法

趙江甫

【摘要】本文主要研究了求解奇數(shù)階魔方的算法.首先給出了t進(jìn)制MorseHedlund序列的概念及性質(zhì)，然后利用此序列給出了一種求解奇數(shù)階魔方的新算法，并利用C程序語言實(shí)現(xiàn).

【關(guān)鍵詞】魔方；奇數(shù)階；MorseHedlund序列

1引 言

n階魔方是1～n2個整數(shù)排成的一個n×n方陣，且每一行、每一列，及兩條對角線上n個數(shù)字之和都相同.可以證明3階以上的魔方都存在[1].魔方按照階數(shù)是奇數(shù)、4的倍數(shù)、2的奇數(shù)倍分為三大類.本文重點(diǎn)研究求解奇數(shù)階魔方的算法.目前已經(jīng)有很多求解魔方的算法，如遞歸算法[2]、勞伯利算法、哈利算法[3-4]、輔助矩陣算法[5]等，這些算法各有利弊，本文利用t進(jìn)制MorseHedlund序列給出了一種新的求解奇數(shù)階魔方算法.

2t進(jìn)制MorseHedlund序列

定義1[6] 將十進(jìn)制數(shù){0，1，2，…，n}分別用t進(jìn)制數(shù)的形式表示出來，然后將各位數(shù)之和模t所得的余數(shù)記為a0，a1，a2，…，an，稱此序列{an}為t進(jìn)制的MorseHedlund序列.例如，

定義2 將矩陣中某一行的元素向右移動一列，將最后一個元素放在第一列，稱為一次右循環(huán).例如，將1 2 3 4 5 6進(jìn)行一次右循環(huán)，即為6 1 2 3 4 5；進(jìn)行兩次右循環(huán)即為5 6 1 2 3 4 ；若進(jìn)行6次右循環(huán)，則又還原到初始狀態(tài).

根據(jù)定義1可知，t進(jìn)制的MorseHedlund序列具有如下性質(zhì)：

性質(zhì)1 序列{an}中的每一項(xiàng)的取值都屬于{0，1，2，…，t-1}，且有重復(fù).

性質(zhì)2 設(shè)d（k）表示{an}中取值為k的項(xiàng)數(shù)，則當(dāng)n=t2-1時(shí)，d（0）=d（1）=…=d（t-1）=t.

3利用MorseHedlund序列求解奇數(shù)階魔方

現(xiàn)利用MorseHedlund序列求解（2k+1）×（2k+1）階魔方，算法如下：

（1）求出0，1，2，…，（2k+1）2-1對應(yīng)的2k+1進(jìn)制MorseHedlund序列a0，a1，a2，…，（2k+1）2-1；

（2）將（1）中所得的MorseHedlund 序列中的所有取值為m的項(xiàng)按照出現(xiàn)的先后順序排成一列，記為序列{a（m）ij}，j=1，2，…，k+1，m=0，1，2，…，2k；

（3）將序列{a（m）ij}，j=1，2，…，2k+1，m=0，1，2，…，2k填入第m+1行，并進(jìn)行m+1次右循環(huán)，即可得到如下矩陣：

（4）將序列{a（m）ij}，j=1，2，…，5，m=0，1，2，3，4填入第m+1行，并進(jìn)行m+1次右循環(huán)，即余數(shù)為0的行，即a（0）ij.

（5）將余數(shù)為4的行，即序列a（4）ij所在的行移動至最中間行，即第3行； 其余行，按照余數(shù)遞減的方式依次填充，即序列a（3）ij所在的行填入第4行，當(dāng)填至最后一行時(shí)，從第一行開始繼續(xù)遞減填入，即余數(shù)為0的行，即a（0）ij.

4結(jié)束語

本文充分利用MorseHedlund序列的概念與性質(zhì)，給出了一種求解奇數(shù)階魔方的全新算法.此算法通俗易懂，充分體現(xiàn)了數(shù)學(xué)美.但是此算法只能解決奇數(shù)階的魔方，對于偶數(shù)階的魔方無效.對于偶數(shù)階、奇數(shù)階的魔方都已經(jīng)各有多種求解算法，如何通過一種統(tǒng)一的算法解決所有階魔方；同一階魔方可能有多種解法，如何求解N階魔方個數(shù)等問題都有待于進(jìn)一步研究.

【參考文獻(xiàn)】

[1]de Campos L M，Huete J F.Approximating causal orderings for Bayesian networks using genetic algorithms and sumulated annealing[C]//Proceeding of the Eighe IPMU Conference，2000：333-340.

[2]耿宏，姚佳佳，李艷.基于輔助矩陣的“魔方陣”求解算法.計(jì)算機(jī)工程與應(yīng)用.2008，44（31）：64-71.

[3] A.Adler，S.-Y.R.Li.Magic cubes and Prouhet sequences[J].Amer.Math.Monthly 1977，84 （8）： 618-627.