任意阶幻方的统一构造
天津诺迪亚公司任初农
摘要：本文通过建立幻方构造的统一模型，提出了任意阶幻方构造的充要条件，并实现了对奇阶、偶阶统一的任意阶幻方构造。
一、引言
洛书是世界公认的组合数学最早史料，它发端了幻方问题。洛书的传说源于大禹治水，至今已有四千多年。现存最早记载洛书九数排列形式的典籍是公元前一世纪汉宣帝时博士戴德的《大戴礼》。
关于幻方的研究已有上千年的历史，至今它仍是组合数学的一个研究课题，构造上也取得了各种奇阶或偶阶的方法。但是，一方面，将奇阶、偶阶幻方统一起来的构造却没有出现，能否实现奇数阶与偶数阶的一体化的统一构造是一个至今尚未解决的问题。最接近的成果是采用正交拉丁方进行幻方的构造，而通过这种方法却造不出六阶幻方，因为六阶的正交拉丁方并不存在，即欧拉的三十六军官问题无解——印度数学家玻斯等人已在五十年代证明，除N=2，N=6外，N阶正交拉丁方均存在。另一方面，各种幻方的构造方法又相互孤立，表面上不存在沟通它们的共同原理。本文正是力图针对这两个方面的问题，寻找出任何一种已知或未知的构造方法都必须遵循的幻方构造充要条件，并实现统一的任意阶幻方构造。
二、两个基本定义
1、幻方定义
定义1、将从a0开始的N2个复数分成N个数组（N为大于2的整数），如果在每一数组内，相邻两元素之差均为k，各相邻数组之间的首尾元素之差均为t（a0、k、t均为复数），采用这N个数构成的N阶方阵，如果其每行、每列及两条对角线上的N个元素之和均相等，为S，则称该方阵为N阶幻方，并称S为该幻方的幻和。
传统的自然数幻方只是这种广义幻方在a0、k、t均为1时的一个子集。
2、原方阵定义
定义2、将定义1中所述N2个数排列成下列方阵，称之为原方阵。
a0 a0 +k ……a0 +nk
a0 +nk+t a0 +(n+1)k+t ……a0 +(n+n)k+t
a0 +2nk+2t a0 +(2n+1)k+2t ……a0+ (2n+n)k+2t
……………………
a0 +nnk+nt a0 +(nn+1)k+nt ……a0+ (nn+n)k+nt 原方阵元素通项为：a i,j=a0+(nk+t)i+kj，其中，i、j分别为元素所在行、列，可取值0，1，2，……，n（n=N-1）（计算机的C语言变量分大小写，VB语言则不分，应注意）。
在原方阵中，a0为首元素；t为相邻两行之间的首尾距；相邻两列的同行元素之差k为列距；相邻两行的同列元素之差nk+t为行距；位于a0至a0+ (nn+n)k+nt 所组成的对角线上的元素称为第一对角线元素；位于a0 +nk至a0 +nnk+nt所组成的对角线上的元素称为第二对角线元素。
为推导方便，此处定义的i、j从0开始取值（与计算机所使用的C语言及VB语言中的数组定义相同），而与一般矩阵中i、j从1开始取值有别。原方阵并不是幻方，但却可以它为基础构造幻方。
三、原方阵的第一步研究
1、两个坐标系的建立
（1）j-i坐标系
以原方阵首行（行号i=0）、首列（列号j=0）分别为轴，j、i的增加方向为轴的方向建立j-i坐标系，见图1。
（2）x-y坐标系
将原方阵看作正方形，以正方形的两条对称轴分别作为x轴、y轴（它们的方向分别与j、i的增加方向相同），建立x-y坐标系，见图1。以后关于对称的讨论就是以x-y坐标系论形，以j-i坐标系论数。
在j-i坐标系中，如果i1+i2=n，则第i1行与第i2行为x-y坐标系中的对称行。如果j1+j2=n，则第j1列与第j2列为x-y坐标系中的对称列。即第i行的对称行为第n-i行，第j列的对称列为第n-j列。
当N为奇数时，原方阵具有中行、中列，且它们分别与x轴、y轴重合。在j-i坐标系中，中行行号为i=n/2，中列列号为j=n/2。在x-y坐标系中，y轴两边各列的x坐标分别为±k、±2k、……、±nk/2，x轴两边各行的y坐标分别为±(nk+t)、±2(nk+t)、……、±n(nk+t)/2。
当N为偶数时，原方阵无中行、中列。y轴两边各列的x坐标分别为±0.5k、±1.5k、±2.5k、……、±[(n+1)/2 - 0.5]k，x轴两边各行的y坐标分别为±0.5(nk+t)、±1.5(nk+t)、±2.5(nk+t)、……、±[(n+1)/2-0.5](nk +t)。
2、几个和式
（1）幻方的幻和
由原方阵定义可导出幻和
n n
S=(1/N)∑ (∑a
i,j )=(n+1){a
+n[(n+1)k+t]/2}
j=0 i=0
即： S=N[(N-1)(Nk+t)+2a
] / 2 （2）原方阵第一对角线元素和
n
S 1=∑a
i,i
=(n+1){ a
+n[(n+1)k+t]/2}=S
i=0
（3）原方阵第二对角线元素和n
S 2=∑a
n-j,j
=(n+1){ a
+n[(n+1)k+t]/2}=S
j=0
（4）N为奇数时，原方阵的中行元素和
n
S mr =∑a
n/2,j
=S
j=0
（5）N为奇数时，原方阵的中列元素和
n
S mc=∑a i,n/2=S
i=0
3、两个关于幻和的定理
定理1、在原方阵中，叠置同阶拉丁方后，每组拉丁号相同的原方阵元素的和均为幻和S。
证明：
原方阵中元素通项a i,j=a0+(nk+t)i+kj
n n
故有S=S1=∑a i,i=∑[a0+(nk+t)i+ki ]
i=0 i=0
n n
即 S=(n+1) a0+(nk+t)∑i+k∑i ……①
i=0 i=0
而，对于原方阵中一组拉丁号相同的N个元素，必然有：它们的行号互不相同，列号互不相同。对这N个元素求和，有
n n
∑a i,j=∑[a0+(nk+t)i+kj ]= (n+1) a0+(nk+t)∑i+ k∑j
i=0 j=0
与①式比较，可知，∑a
=S 证毕。
i,j
定理２、在原方阵中，关于中心对称的N个元素之和必为幻和S。
证明：
在原方阵中，与a i,j中心对称的元素为a n-i,n-j。
a i,j+a n-i,n-j =a0+(nk+t)i+kj+ a0+(nk+t)(n-i)+k(n-j)
=2 a0+(N-1)(Nk+t)
当N为偶数时，N个两两关于中心对称的元素之和为：
N/2 ×[2 a0+(N-1)(Nk+t)]=S
当N为奇数时，N-1个两两关于中心对称的元素及方阵中心元素之和为：(N-1)/2×[2 a0+(N-1)(Nk+t)]+ a n/2,n/2
=(N-1)/2 ×[2 a0+(N-1)(Nk+t)] + a0 +[(N-1)k +t](N-1)/2 +k(N-1)/2
=S
证毕。
四、以原方阵为基础构造任意阶幻方
1、原方阵与幻方的比较
由上可知，分别处于原方阵的第一、第二对角线及中行、中列上的N个元素的和均为幻和。要由原方阵构造幻方，还需对其余行、列元素的和进行分析。
原方阵第i行的元素和：
n
R i =∑a i,j=(n+1)[a0+(nk+t)i+nk/2]
j=0
原方阵第j列的元素和：
n
C j =∑a i,j=(n+1)[a0+n(nk+t)/2+kj]
i=0
幻和与原方阵行元素和之差：
D i =S- R i =(n+1)(nk+t)(n-2i)/2
幻和与原方阵列元素和之差：
E j =S- C j =(n+1)k(n-2j)/2
而对于原方阵中第i行、第j列的对称行、对称列，则有：
D n-i =S- R n-i =S-(n+1)[a0+(nk+t)(n-i)+nk/2] = - D i
E n-j =S- C n-j =S-(n+1)[a0+n(nk+t)/2+k(n-j)]= - E j
即有
S- R i+D n-i =0
S- R n-i+D i =0
S- C j+E n-j =0
S- C n-j+E j =0
这就为在对称行及对称列之间进行元素调整，实现幻方的构造提供了可能。下面讨论如何进行这种调整。
一对行对称元素的差值为：
δr= a n-i,j -a i,j=[a0+(nk+t)(n-i)+kj] - [a0+(nk+t)i+kj]
即δr=(nk+t)(n-2i)
一对列对称元素的差值为：
δc= a i,n-j -a i,j=[a0+(nk+t)i+k(n-j)]- [a0+(nk+t)i+kj]
即δc=k(n-2j)
将原方阵行元素和、列元素和调整为幻和，即是使得调整后：
R’i =S= R i +D i= R i +(n+1)(nk+t)(n-2i)/2
即R’i = R i +Nδr/2……②
C’j =S= C j +E j= C j +(n+1)k(n-2j)/2
即C’j = C j +Nδc/2……③
通过以上推导，可得下列定理：
定理3、对N>2的偶数阶原方阵，分别在它的所有对称行、对称列中互易N/2对轴对称元素，并同时保证第一对角线上的元素和、第二对角线上的元素和均不改变。由此构造的N阶方阵必为幻方。
对于确定的N2个元素构成的幻方，不管它们的具体构造如何不同，它们的幻和都是相同的，因此，在数值上，一个幻方的每一行的行和、每一列的列和都可分别分解成②式、③式。故有下列定理：
定理4、对于N>2的任意阶原方阵，无论它的每一行、每一列上的元素在原方阵范围内进行了什么调整，只要：（1）这种调整都是相当于与对称行或对称列互易N/2对轴对称元素值；（2）且第一对角线元素和、第二对角线元素和均未改变；（3）且当N为奇数时，中行元素和、中列元素和均未改变。由此构成的方阵必为N阶幻方。
定理４实际上就是N2个原方阵元素构造幻方的充分必要条件。它揭示了幻方构造的实质。但并不一定便于直接构造幻方，尤其是奇阶幻方。
下面提出的定理给出定理４实际应用的一种简洁方案。
２、任意阶幻方的统一构造
定理５、如果有一个N阶原方阵，它的通项为a
i,j = a
+[(N-1)k+t]i+kj，其中i、
j取值０，１，２，……，N-1，N>2，通过半N变换法调整这个方阵中的元素位置，可以构造N阶幻方，其幻和为：
S=N[(N-1)(Nk+t)+2a
]/2
定理中所规定的半N变换法如下：
（1）当N为偶数时，将原方阵的每一对对称行、每一对对称列中的N/2对对称元素分别进行位置互易。
（2）当N为奇数，且N=4m+1 (m=1, 2, 3……)时：
①将原方阵中除中行外的每一行中的一个元素分别与中行上与它同
列的那个元素进行位置互易；将原方阵中除中列外的每一列中的一个
元素分别与中列上与它同行的那个元素进行位置互易；
②在新形成的中行元素、中列元素不再改变位置的前提下，分别将原
方阵的每一对对称行、每一对对称列中的（N-1）/2对对称元素进行
位置互易。
（3）当N为奇数，且N=4m-1 (m=1, 2, 3,……)时：
①任选下述四组旋转调整中的一组对第一对角线、第二对角线及中行、
中列上的元素进行位置调整。
A组：将第一对角线、第二对角线上的元素分别围绕方阵中心旋转
3π/4放置，将中行、中列上的元素分别围绕方阵中心旋转 -π/4
放置。
B组：将第一对角线、第二对角线上的元素分别围绕方阵中心旋转
–3π/4放置，将中行、中列上的元素分别围绕方阵中心旋转π/4放
置。
C组：将第一对角线、第二对角线上的元素分别围绕方阵中心旋转
π/4放置，将中行、中列上的元素分别围绕方阵中心旋转–3π/4放
置。
D组：将第一对角线、第二对角线上的元素分别围绕方阵中心旋转
-π/4放置，将中行、中列上的元素分别围绕方阵中心旋转3π/4放
置。
②在新形成的第一对角线、第二对角线、中行及中列元素不再改变位
置的前提下，分别将原方阵中的每一对对称行、每一对对称列中的
（N-3）/2对对称元素进行位置互易。
（4）在（1）、（2）两类变换中（N为偶数或N=4m+1时），为保证第一、二对角线上的元素和均不改变，应满足下列条件之一：
①对角线位置上的元素不参加位置调整；否则调整后仍在原对角线上；
否则处于同行（或同列）的两组对角线元素同时参加位置调整，以
保证对对角线元素和影响相互抵消。
②由定理1中所述的拉丁号相同的元素组成新对角线。
③由定理2中所述的N个中心对称元素组成新对角线。
（5）元素的行调整不会改变列和，列调整不会改变行和，所以，一个元素最多可进行两次位置互易。两次互易的元素在先行后列调整时，必须
分别是原方阵中的行对称、列对称元素，在先列后行调整时，必须分
别是原方阵中的列对称、行对称元素。
3、定理5的证明
对定理5的证明可以分为两部分：（1）原方阵能为这种变换提供足够的元素。
（2）这种变换能符合定理4的要求。
（1）第一部分证明
这部分证明特别针对极端苛刻的情形，即在构造中最少引入双重互易。事实上，双重互易元素的引入越多，原方阵中涉及位置更换的元素就越少，元素的供需矛盾更易于解决。
证明中，采用两条对角线将原方阵分成上下左右四区，当某两个对称行（列）作行（列）元素互易时，尽可能将互易元素分成对称对数，分别靠近两条对角线在上下（左右）两区安排，接近方阵中心，元素不够时，再引入左右（上下）两区中的相同对称行（列）的元素对作从方阵左右（上下）边界开始并关于y(x)轴的最大可能的对称对数安排。以上利用方阵的几何对称性，使得不参加行互易的元素能尽可能用于列互易中，反之，不参加列互易的元素也能尽可能用于行互易中，最大限度地避免两种互易时的元素选择冲突，而在此后如果仍然存在选择冲突，才通过双重互易加以解决。这种方法可以最少量地引入双重互易，但具体应用定理5时，对双重互易的多少并无限制，所以并非一定要采用此法。
①N=4m+1（即N为双偶基奇数时）[参见图4.(3)]
在半N变换法（2）①中，将一个元素与中行（或中列）中与它同列（或同行）的那个元素进行位置互易，即是完成了“1/2对”行对称（或列对称）元素的位置互易（这一点将在（2）中证明，此处先引用）。进行完这一类调整后，原方阵还能提供位置对称互易调整的元素数目为：
l1=N2-(2N-1)-2(N-1)=N2-4N+3
而按定理4，对每一对对称行、对称列还需互易N/2 -1/2对元素，即总共还需互易的元素数目为：
l2=2(N-1)(N/2-1/2)=N2-2N+1
供需之差为：l1-l2= -2(N-1)
所以，只要将其余参加互易的元素中的2(N-1)个元素进行行与列的双重互易，即可补此不足。例如：将两条对角线上的元素进行中心对称互易。
又因为N/2-1/2为偶数
所以，能实现在行调整中，元素关于列的对称选择，以及在列调整中，元素关于行的对称选择。
②N=4m-1（即N为单偶基奇数时）[参见图4.(4)]
进行旋转调整之后，原方阵还能提供位置对称互易调整的元素数目为：l1=N2-(4N-3)=N2-4N+3
在待证定理中，两条对角线及中行中列元素的位置旋转，即是完成了每一行中的3/2对行对称元素及每一列中的3/2对列对称元素的位置互易（这一点将在(2)中证明，此处先引用）。按定理４，对每一对对称行、对称列还需互易N/2-3/2对元素，即总共还需互易的元素数目为：
l2=2(N-1)(N/2-3/2)=N2-4N+3
供需之差为：l1-l2=0
所以，即使不引入双重调整，也能满足调整之需。
又因为N/2-3/2为偶数
所以，能实现在行调整中，元素关于列的对称选择，以及在列调整中，元素关于行的对称选择。
③N=4m（即N为双偶数时）[参见图3.第二行第三图]
l1=N2
l2=2N·N/2=N2
l1-l2=0
又因为N/2为偶数
所以，能实现在行调整中，元素关于列的对称选择，以及在列调整中，元素关于行的对称选择。从而满足调整之需。
④N=4m+2（即N为单偶数时）[参见图4.(2)]
l1=N2
l2=2N·N/2=N2
l1-l2=0
但因为N/2为奇数
所以，不能实现在行调整中，元素关于列的对称选择，以及在列调整中，元素关于行的对称选择，这种不对称将使行调整与列调整相互制约，产生冲突。
又因为，可以实现不能找到这种对称的元素在行调整中每行出现一个，在列调整中每列出现一个。
所以，只需引入N个（当N>6时）或2N个（当N=6时）元素，作不改变两条对角线元素和的双重调整，便可避开冲突，满足调整之需。
（2）第二部分证明
当N为偶数时，定理5中所述的互易方法显然是符合定理4的。
当N为双偶基奇数时，由定理1可知，新中行和与新中列和仍为幻和。
当N为单偶基奇数时，中行、中列分别变成了两条新的对角线；两条对角线分别变成了新中行、新中列。由“三”中“2、几个和式”可知新中行和、新中列和、新第一对角线和、新第二对角线和都为幻和。
所以N为奇数时，只需对（1）的①、②中留待证明部分加以证明即可。
①此步证明，将一个元素与中行（或中列）中与它同列（或同行）的那个元素进行位置互易，即是完成1/2对行对称（或列对称）元素的位置互易。可将这种互易称为行半对称互易（或列半对称互易）：
第i行中的一个元素与中行上与它同列的那个元素进行位置互易，即是a i,j 与a n/2,j互易。
a n/2,j-a i,j=[a0+(nk+t)n/2+kj]- [a0+(nk+t)i+kj]=(nk+t)(n-2i)/2=δr/2
所以，a i,j与a n/2,j的互易相当于完成了1/2对行对称元素的互易。
同理可证a i,n/2-a i,j=δc/2 ，则①证毕。
②此步证明，在定理5中，两条对角线及中行、中列元素元素的位置旋转，即是完成每一行中的3/2对行对称元素及每一列中的3/2对列对称元素的位置互易。
以A组为例，见图2 ，对于非中行的某一行（或非中列的某一列），旋转调整仅改变其处于中列（或中行）及对角线上的三个元素，由原方阵元素的通项公式可知：
新第i行与原第i行元素和之差为：
a n/2,j+a i,j+ a i,n/2 - a i,j - a i,n/2 - a i,n-j =3δr /2
新第n-i行与原第n-i行元素和之差为：
a n-i,n/2+a i,j+ a n/2,n-j - a n-i,j - a n-i,n/2 - a n-i,n-j = -3δr /2
即，新i行、新n-i行是由原i行、原n-i行互易3/2对行对称元素值形成。同理可证，新j列、新n-j列是由原j列、原n-j列互易3/2对列对称元素值形成的。
同A组证明，可证B组、C组、D组调整。
4、关于定理5的第一个引理
由于双重调整在幻方阶数增加时带来了元素利用率的提高，采用类似定理5的证明方法，可证下列引理：
引理1、半N变换法的第（2）项中所述方法适用于N>3且N≠7的所有奇数阶的原方阵构造幻方。第（3）项所述方法适用于N≥3且N≠5的所有奇数阶的原方阵构造幻方。
五、任意阶幻方统一构造的优化方案及算法
1、幻方构造方案图
根据定理5，对于同阶幻方，可以作出各种不同的方案。为了表示一个N 阶幻方构造方案，可以采用下面这套符号标记元素的位置调整：“│”表示元素的行对称互易；
“─”表示元素的列对称互易；
“┼”表示元素作双重互易。一个进行双重互易的元素必然涉及它在原方阵中的两个轴对称元素和一个中心对称元素的位置改变，其可能情况有三种：①即这四个元素均选择作双重互易，此时无论先行后列调整还是先列后行调整，其实质都是这四个元素作中心对称互易，对这种情况可改用符号“╲”或“╱”作调整标记。②或即先行后列调整。③或即先列后行调整。
“┬”或“┴”表示元素的行半对称互易；
“┤”或“├”表示元素的列半对称互易；
“⊕”表示元素位置正向旋转调整；
“?”表示元素位置负向旋转调整；
未作上述标记的元素不进行位置调整。
图3列举了一些按照定理5作成的幻方构造方案。
2、关于定理5的第二个引理
由原方阵中4个行对称及列对称元素a i,j……a i,n-j
…………
a n-i,j……a n-i,n-j
进行双重调整时的和值变化讨论可知，两对轴对称元素和存在下列关系：
a i,j + a n-i,n-j = a i,n-j + a n-i,j
故有：
引理2、在半N变换法的第（5）项中：或也可为先列后行调整，虽然这时行调整互易的是原方阵中的中心对称元素，而不是行对称元素；或也可为先行后列调整，虽然这时列调整互易的是原方阵中的中心对称元素，而不是列对称元素。
3、任意阶幻方统一构造的优化方案
半N变换法不但解决了任意阶幻方的统一构造问题，采用这种方法还可找到众多的统一构造的方案。下面举出其中一种为代表，它是以下述四个子方案为基础的，见图4。而这四个子方案具有较多的公共部分和较少的双重互易。
这四个方案的共同特点是都有一个“※”型骨架，即“×”代表在对角线及其附近安排正常的对称行及对称列的调整，而“·”代表在x轴及y轴附近安排补充调整。当原方阵为偶数阶或双偶基奇数阶时，对角线上元素作中心对称调整，对后者的每一行、每一列均有一个元素作半对称调整。当原方阵为单偶基奇数阶时，其x轴、y轴及两条对角线上的元素按规则进行旋转调整。
4、任意阶幻方统一构造优化方案的一个算法
根据上述方案，可作出主要的构造分界函数图，见图5。从而写出算法。
（1）N=4m（双偶阶）
1）0 →i，0 →j
2）调用骨架算法
3）如果j≠n，则j+1 →j，转2）
4）如果i≠n，则i+1 →i，0 →j，转2）
5）结束
（2）N=4m+2（单偶阶）
1）0 →i，0 →j
2）调用骨架算法
3）如果i 如果i=j-m且i 则a i,j ←→a n-i,j，转5） 如果i=j+m 则a i,j ←→a i, n-j，转5） 如果i=n+m+1-j 则a i,j ←→a n-i,j，转5） 4）如果i>n/2且j 则a i,j ←→a i,n-j 5）如果j≠n，则j+1 →j，转2） 6）如果i≠n，则i+1 →i，0 →j，转2） 7）结束 （3）N=4m+1（双偶基奇数阶） 1）0 →i，0 →j 2）调用骨架算法 3）如果i 如果j 则a i,j ←→a n/2,j，转6） 如果j>n/2且（i=n-m-j或i=n+m-j） 则a i,j ←→a i,n/2，转6） 5）当i>n/2时 如果j>n/2且（i=j-m或i=j+m） 则a i,j ←→a n/2,j，转6） 如果j 则a i,j ←→a i,n/2 6）如果j≠n，则j+1 →j，转2） 7）如果i≠n，则i+1 →i，0 →j转2） 8）结束 （4）N=4m-1（单偶基奇数阶） 1）0 →i，0 →j 2）如果i=j，则a i,j→b i ，转6) 3）如果i=n-j，则a i,j →c j ，转6) 4）如果i=n/2，则a i,j→d j ，转6) 5）如果j=n/2，则a i,j→e i ，转6) 6）如果j≠n，则j+1 →j，转2) 7）如果i≠n，则i+1 →i，0 →j，转2) 8）0 →i，0 →j 9）调用骨架算法 10）如果i 如果i=j+m或i=n+m-j 则a i,j ←→a n-i,j，转12） 如果i=j-m且i 则a i,j ←→a i,n-j，转12） 11）如果i>n/2且j 则a i,j ←→a i,n-j 12）如果j≠n，则j+1 →j，转9） 13）如果i≠n，则i+1 →i，0 →j，转9） 14）0 →i 15）b i→a n-i,n/2 ，c i →a n/2,n-i ，d i→a i,i ，e i→a i,n-i 16）如果i≠n，则i+1 →i，转15） 17）结束 （5）骨架算法 1）如果i 如果i=j或i=n-j，则a i,j ←→a n-i,n-j，转3） 如果[i 如果j 3）结束 笔者根据这个算法，用C语言及VB编写了程序。在计算机上运行时，按提示分别输入N、a0、k、t四个参数，便可立即输出N阶幻方，从而自动实现了任意阶乃至广义任意阶幻方的统一构造。 通讯地址：天津市和平区福安大街新文化花园新丽居2号楼D座10层诺迪亚公司任初农邮政编码：300021 联系电话：022-********-211 个人主页：https://www.doczj.com/doc/ef4871022.html, 电子邮箱：cnren@https://www.doczj.com/doc/ef4871022.html,
相关主题
文本预览