基于t进制Morse睭edlund序列的奇数阶魔方求解算法

赵江甫

【摘要】本文主要研究了求解奇数阶魔方的算法.首先给出了t进制MorseHedlund序列的概念及性质，然后利用此序列给出了一种求解奇数阶魔方的新算法，并利用C程序语言实现.

【关键词】魔方；奇数阶；MorseHedlund序列

1引 言

n階魔方是1～n2个整数排成的一个n×n方阵，且每一行、每一列，及两条对角线上n个数字之和都相同.可以证明3阶以上的魔方都存在[1].魔方按照阶数是奇数、4的倍数、2的奇数倍分为三大类.本文重点研究求解奇数阶魔方的算法.目前已经有很多求解魔方的算法，如递归算法[2]、劳伯利算法、哈利算法[3-4]、辅助矩阵算法[5]等，这些算法各有利弊，本文利用t进制MorseHedlund序列给出了一种新的求解奇数阶魔方算法.

2t进制MorseHedlund序列

定义1[6] 将十进制数{0，1，2，…，n}分别用t进制数的形式表示出来，然后将各位数之和模t所得的余数记为a0，a1，a2，…，an，称此序列{an}为t进制的MorseHedlund序列.例如，

定义2 将矩阵中某一行的元素向右移动一列，将最后一个元素放在第一列，称为一次右循环.例如，将1 2 3 4 5 6进行一次右循环，即为6 1 2 3 4 5；进行两次右循环即为5 6 1 2 3 4 ；若进行6次右循环，则又还原到初始状态.

根据定义1可知，t进制的MorseHedlund序列具有如下性质：

性质1 序列{an}中的每一项的取值都属于{0，1，2，…，t-1}，且有重复.

性质2 设d（k）表示{an}中取值为k的项数，则当n=t2-1时，d（0）=d（1）=…=d（t-1）=t.

3利用MorseHedlund序列求解奇数阶魔方

现利用MorseHedlund序列求解（2k+1）×（2k+1）阶魔方，算法如下：

（1）求出0，1，2，…，（2k+1）2-1对应的2k+1进制MorseHedlund序列a0，a1，a2，…，（2k+1）2-1；

（2）将（1）中所得的MorseHedlund 序列中的所有取值为m的项按照出现的先后顺序排成一列，记为序列{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行，并进行m+1次右循环，即可得到如下矩阵：

（4）将序列{a（m）ij}，j=1，2，…，5，m=0，1，2，3，4填入第m+1行，并进行m+1次右循环，即余数为0的行，即a（0）ij.

（5）将余数为4的行，即序列a（4）ij所在的行移动至最中间行，即第3行； 其余行，按照余数递减的方式依次填充，即序列a（3）ij所在的行填入第4行，当填至最后一行时，从第一行开始继续递减填入，即余数为0的行，即a（0）ij.

4结束语

本文充分利用MorseHedlund序列的概念与性质，给出了一种求解奇数阶魔方的全新算法.此算法通俗易懂，充分体现了数学美.但是此算法只能解决奇数阶的魔方，对于偶数阶的魔方无效.对于偶数阶、奇数阶的魔方都已经各有多种求解算法，如何通过一种统一的算法解决所有阶魔方；同一阶魔方可能有多种解法，如何求解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]耿宏，姚佳佳，李艳.基于辅助矩阵的“魔方阵”求解算法.计算机工程与应用.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.