中南大学
毕业论文（设计）任务书
毕业论文（设计）题目： 广义拉丁方的构造和应用研究
题目类型[1] 理论研究 题目来源[2] 教师为学生选题
毕业论文（设计）时间从 2004.3.1 至 2004.6.10
1. 毕业论文（设计）内容要求：
该论文设计要求：1.熟悉和掌握拉丁方的基本理论和构造方法及染色问题的解法，认真阅读指定的3篇论文。 2. 对以下问题编程进行数据实验：（1）对文献[1]提出的方法用计算机编程实现, 在10以内检验：（2）将其问题和方法推广到立体三个方向, 并研究之；(3) 数据实验要进行编程和调试等工作，要较好的掌握设计使用的语言工具， 3.完成实验的设计后，应对发现的规律进行研究，包括对其中一种进行较为细致的研究，4. 设计完成后，按学校毕业论文的要求完成毕业论文的写作。
____________________________________ _ ____________________________________________________________ ________________________________________________ ________________________________________________ ________________________________________________________________________ ____________________________________________________________ _____________________________________________________________ _____________________________________________ ____________________________ _____________ ___________________ _ [1] 题目类型: ①理论研究②实验研究③工程设计④工程技术研究⑤软件开发
[2] 题目来源: ①教师科研题②生产实际题③模拟或虚构题④学生自选题
文献查阅指引
1. 王建中，《染色问题…》，湖南教育学院学报，1988.5 1999.2
_2. Chen Xiaosong. Ways of Constructing Optimal Magic Cube of Order nWhen ( n, 2357)=1. Journal of Central south university of Technology. (English Edition) 2002.1(Vol.9)
_3. 陈小松, n (( n, 235)=1)阶高级幻立方的构造方法. 湖南教育学院
学报 ， 1990.5
_
________________________________________ _______________ _______________________________________________________ ____________ ________________ ________________________________________________________ ____________ _________________________________________________________________ __________ _ _______________ _ _______ __ ___________
3. 毕业论文（设计）进度安排
|
阶段
|
阶 段 内 容
|
起止时间
|
|
一、
|
调研、确定题目并查阅有关文献
|
2.23 – 3.10
|
|
二、
|
选择有关的外文参考文献完成英译中
|
3.11- 3.31
|
|
三、
|
数据实验及程序设计和调试，对有关问题进行钻研
|
4.1- 5.20
|
|
四、
|
撰写论文并根据指导老师意见完成对论文进行修改
|
5.21- 5.30
|
|
五、
|
作论文答辩准备和参加论文答辩.
|
5.31- 6.5
|
指导教师（签名） 时间： 2004.3.1
专业室（所）主任（签名） 时间：
主管院长（签字） 时间：
目 录
摘要 …………………………………………………………………………………………… 1
Abstract ……………………………………………………………………………………… 2
第一章 引言 ………………………………………………………………………………… 3
1.1 拉丁方的起源 ……………………………………………………………………… 3
1.2 简易拉丁方的应用 ………………………………………………………………… 4
第二章 广义拉丁方的构造和应用研究 …………………………………………………… 5
2.1 拉丁方的探讨 ………………………………………………………………………… 5
2.1.1 拉丁方问题的产生意义与应用 ………………………………………………… 5
2.1.2 一般拉丁方的定义 ……………………………………………………………… 6
2.2 正交拉丁方的探讨 …………………………………………………………………… 6
2.2.1 正交拉丁方定义的得出与应用 ………………………………………………… 6
2.2.2 正交拉丁方的性质 ……………………………………………………………… 8
2.3 完备拉丁方的定义与性质 …………………………………………………………… 9
2.4 相关于拉丁方的数论领域知识分析 ………………………………………………… 10
2.4.1 数论的现状 ……………………………………………………………………… 10
2.4.2 重要性质定理 …………………………………………………………………… 10
2.4.3 域的概念 ………………………………………………………………………… 11
2.5 最佳拉丁方的入门 …………………………………………………………………… 13
2.5.1 最佳拉丁方问题的提出 ………………………………………………………… 13
2.5.2 最佳拉丁方存在性公式透析 …………………………………………………… 13
2.6 二维方块染色问题与对应最佳拉丁方存在构造的深入研究 ……………………… 14
2.6.1 二维方块染色问题的提出及其相关规定 ……………………………………… 14
2.6.2 1 到 7阶方块染色的分析与对应最佳拉丁方的存在构造 …………………… 15
2.6.3 一种二维最佳拉丁方构造方法 ………………………………………………… 21
2.7 三维立体方块染色问题的深入研究与对应最佳立体拉丁方的思考 ……………… 22
2.7.1 三维立体拉丁方 ………………………………………………………………… 22
2.7.2 三维立体拉丁方的具体构造方法 ……………………………………………… 23
2.7.3 三维染色问题的提出及其相关规定 …………………………………………… 29
2.7.4 1 到 5阶立体方块染色分析与对应最佳立体拉丁方的思考 ………………… 31
第三章 染色及其对应最佳拉丁方分析的计算机算法实现 ……………………………… 34
3.1 二维方块染色分析计算机实现 …………………………………………………… 34
3.2 三维方块染色分析计算机实现 ……………………………………………………… 37
3.3 二维或三维方块子元素相关性分析计算机实现 …………………………………… 42
3.4 一种二维最佳拉丁方构造方法计算机实现 ………………………………………… 47
3.5 广义三维立体拉丁方的构造算法实现 ……………………………………………… 49
第四章 结论总结 …………………………………………………………………………… 51
致谢 …………………………………………………………………………………………… 52
参考文献 ……………………………………………………………………………………… 53
附录 …………………………………………………………………………………………… 54
==================================================================================================
==================================================================================================
摘 要
本文从幻方和拉丁方的起源与简易应用入手，对正交拉丁方与完备拉丁方构造的初步探讨和最佳拉丁方的引入。然后就王建中提出的染色问题与最佳拉丁方存在性的联系，在其对3，4，6阶方块染色问题过程与对应的最佳拉丁方不存在的具体化的基础上补充了5阶方块的染色的具体过程和对应的最佳拉丁方存在，并且由7阶方块推出了矛盾，即7阶最佳拉丁方存在但是7种颜色无法染色。随后设计了一个最佳拉丁方的构造方法。平面的拉丁方问题成熟后，自然过渡到三维空间，在加工拉丁方试验使之应用到三维空间的基础上把拉丁方定义推广至广义三维立体空间，并导出一种基于副斜线的n阶广义三维拉丁立方的构造方法并发现了新规律，即按此法构造的三维拉丁立方的第i行,j列,k层的元素为i,j,k之和（Jn内计算）。随后通过修改补充二维方块染色问题中的相关规约引理把平面上的染色问题拓展到三维立体空间，并且对一至五阶三维立体方块染色问题进行了细致研究，最后提出了广义立体空间上的最佳拉丁方存在性问题的一些初步的看法和思考。在研究以上问题中利用了C语言实现相关算法帮助分析并记录在文本之中。
关键词：拉丁方；最佳拉丁方；染色；广义三维立体拉丁方；广义三维立体最佳拉丁方
Abstract
In this paper the author begins the topic with the origin of the Magic Square and Latin Square, and carries out the initial discussion of the Orthogonal Latin Square when introduces the Perfect Latin Square. Next, according to the relation between the Dye Issue and existence of the Optimal Latin Square and the specific utility in 3,4,6 order squares worked out by Wang-JianZhong,the author complement the 5,7 order squares’ specific utility and prove the fact Wang-JianZhong’s way is not suitable for the square of 7 order on the base that 7 order Optimal Latin Square exists but 7 sorts of colors can’t dye 7 order square. What’s more a method how to construct an Optimal Latin Square is designed. After the ripe idea of the Latin Square in two-dimensional space, the question is naturally extended to the three-dimensional space. So the Latin Square experiment is improved in order to suit three-dimensional space. Meantime the definition of Latin Square is spread to the extensive three-dimensional space and a method how to construct a Three-Dimensional Latin Cube of order n on the base of the deputy diagonal lines is worked out, in which a new regular pattern, that is, these Three-Dimensional Latin Cubes’ element on the ith row, jth column and kth layer constructed by the method above is the sum of i, j and k(in Jn), is discovered Afterward the author extends the Dye Issue to the three-dimensional cube by amend and complement the relevant rules as well as lemmas, and analyzes the cube of order 1~5 carefully. Finally the author gives some elementary opinions and suppositions of Optimal Latin Cube’s existence in three-dimensional space. The relevant arithmetic which can help the analyses of the discussion all above realized in C programming language is also recorded in this paper.
Keyword: Latin Square; Optimal Latin Square; Dye; Extensive Three-Dimensional Latin Cube; Extensive Three-Dimensional Optimal Latin cube
=================================================================================================第一章 引言
1.1 拉丁方的起源
数学产生于人类生产实践。同时几乎所有的数学分文的产生与游戏或多或少地有着联系。组合数学与概率论相似，它们产生的历史与一些奇特的事情相关。概率论源于赌博问题，组合数学源于数学游戏。组合数学早期研究的内容是对象的安排数，及符合特定条件的安排是否存在。
一些著名的难题可以上溯几百年，一门学科既依赖于自身（有许多富有挑战性的难题，几代人努力尚未攻克），又与其他学科密切相关（其他学科对他提出新问题，征求解法），从这两层意义上看，组合数学比其他数学分支更得天独厚，尤其在电子计算机日益广泛渗入各领域的时代更是如此。电子计算机普及和发展，不仅用到数值计算的各种算法，而且还大量地用到非数值计算的算法 — 主要是组合算法。而设计与分析组合算法的基础就是组合数学。此外，管理科学、信息科学、人工智能、生命科学甚至人文学科中许多问题的求解也借助并促进了组合数学。而拉丁方是组合数学里的一个子课题，它主要应用于区组设计方面，西方人最早提出了拉丁方一词，实际上在我国早就有了拉丁方的记载，下面就来简单的谈谈它的脉络。
《周易》其著者己不可考,相传是伏羲、文王、孔丘所作。但这只是推测,实不尽可靠。
在《周易·系辞上》记载“河出图,洛出书,圣人则(效法)之”,但没有说明“河图、洛书”是什么意思。后人凭想象编造出许多神话,说“河出图”是河里跳出一匹“龙马”,背着一幅图,而“洛出水”是从洛水里爬出一支龟,背着书。到了宋朝,有人将“河出图,洛出水”与“九宫”联系起来。“九宫”是一种“纵横图”,西方人叫幻方(magic square).中国古代著作《大戴礼记》、《明堂》有“二,九,492357816四,七,五,三,六,一,八的记载。徐岳《数术记遗》中有“九宫算”,如图1-1
图1-1
中国古代几百年来,许多重要数学著作都宣扬数起源于“河图、洛书”的错误论点,如宋代《数书九章》、明代《算法统宗》及清代《数理精蕴》等。直到清乾隆年间《增删算法统宗》才删去河图、洛书之类神话。在世界上,十五世纪(我十四世纪)之初,拜占庭的摩索普拉斯将东方的纵横图首先介绍到欧州去。
纵横图开始时纯粹是一种数学游戏,在今天小学算术课本中出现过这种图形。但近代研究发现纵横图和组合分析有某种关系。它在图论、程序设计、组合分析等方面都有广泛应用。
在欧州,纵横图又叫幻方,开始时是在宫庭中的一种数学游戏。幻方是所谓拉丁方(latin square)的进一步演变发展产物。所谓“拉丁方”是这样定义的。定义:设Ｓ是一个含有ｎ
注：为了突出重要性，本文中意义重大的定义、问题、定理、性质、规定等标题都用粗体纂写。
个元素的集合。那么一个以Ｓ为基的ｎ阶拉丁方Ｌ=(ｌｉｊ)是Ｓ中元素排列成一个ｎ×ｎ方阵。每行(或每列)中的每个元素都不相同。例如,以Ｓ={1,2,3}为基的3阶拉丁方:
图1-2
这是一个最为基本的一般拉丁方，随着学科的发展，应用的需要，各种广义上的拉丁方被相继提出。
1.2 简易拉丁方的应用
拉丁方应用的价值是很可观的，很多科学的试验都会利用到拉丁方。比如说一种新型的工厂防酸材料被研制出来，现要用它对三种工厂常用的酸性物质进行测试，那么可以取一块正方形的此种材料，为了让试验准确地反映材料对三种酸的抗酸性，较为合理的科学方案应该把正方形材料划分成3×3方块，三种酸用1，2，3来代替，试验方案可以设计成如图1-2的样子，这样，试验结果就会较平均而客观。
以上都是一些初步的介绍，下面我们将进入第二章，对拉丁方及广义上的拉丁方的构造和应用进行详细的研究。
第二章 广义拉丁方的构造和应用研究
2.1 拉丁方的探讨
2.1.1 拉丁方问题的产生意义与应用
设有一块地用做某一作物的 A，B，C 三种不同品种的试验田。若该地划分成如图2-1的（a），（b），则可能由于自然条件的差异，使试验不准确，较合理的试验方案如图2-2，其特点是每行、每列都有一个A，B，C。
A
B
C
A B C
（a） （b）
图 2-1
A B C
C A B
B C A
图 2-2
又如治某种病的六种药 d1，d2，d3，d4，d5，d6 给六位病人进行试验，疗程为一星期。若采用表2-1 最简单的方案，其缺点是后服的药的疗效可能要好一些，因为前面服过的药已起作用。如若改为每人在六种中只服一种药，同样也存在缺点。可能有的药对某些病人有效，对另一些病人却无效。
表 2-1
|
星期
人
|
一
|
二
|
三
|
四
|
五
|
六
|
|
M1
|
D1
|
D2
|
D3
|
D4
|
D5
|
D6
|
|
M2
|
D1
|
D2
|
D3
|
D4
|
D5
|
D6
|
|
M3
|
D1
|
D2
|
D3
|
D4
|
D5
|
D6
|
|
M4
|
D1
|
D2
|
D3
|
D4
|
D5
|
D6
|
|
M5
|
D1
|
D2
|
D3
|
D4
|
D5
|
D6
|
|
M6
|
D1
|
D2
|
D3
|
D4
|
D5
|
D6
|
理想的方案是在这6天中每人都对这6种药进行试验，每天都有这6种药对六个人进行试验，而不是要么同一天里只做一种药的试验，要么一个人只对一种药做试验。自然导致构造一个6×6 的矩阵，可以把以上的讨论推广到由元素1，2，3，….，n构成的n×n方阵（aij）n×n，要求每行，每列中1，2，3，….，n各出现一次。这样的方阵就叫做拉丁方。
1 2 3 4 5 6
6 1 2 3 4 5
5 6 1 2 3 4
4 5 6 1 2 3
3 4 5 6 1 2
2 3 4 5 6 1
图2-3
如图2-3所示的方案就是比较高效的拉丁方方案（其中6个阿拉伯数字对应的就是6种不同的药）。
2.1.2 一般拉丁方的定义
定义2.1：n个不同的符号，通常就取整数1，2，….，n。在一个n×n的数组中，这n个整数中的每一个数在每一行恰好只出现了一次，并且在每一列中也只出现了一次，这n阶方块就称之为n阶拉丁方。
2.2 正交拉丁方的探讨
2.2.1 正交拉丁方定义的得出与应用
但在科学实验中，一个过程往往是由许多因素互相配合又互相制约产生整体效应的。如开始我所提到的作物试验问题来看，其生长条件还可以具体化为试验田的土壤颗粒的程度，酸碱度，日照，肥料等因素。药品试验也可能是很多种药搭配来测试疗效，还可能考虑到用药的药量以及其它增效与禁忌药物等诸多因素。这就引入了正交拉丁方的概念。
著名的数学家Euler在1782年提出并猜测了一个有名的“36军官问题”：有36名军官，恰好来自6个不同的军团并带有6种不同的军衔；每个军团的6名军官恰好分占6种不同军衔。现问：36 名军官排成6×6方阵，使每行以及每列的6名军官既来自于不同的军团，又具有不同的军衔，这能办到吗？
数学家们已经证实了这个问题的不存在性，这里只是为了引入正交拉丁方，所以36军官问题的证明过程我就不再累述。现如果我们把“36军官问题”按同样的意义缩小为“9军官问题”：如有9名军官，分别来自陆海空3个军种，每个军种恰有将校尉3种军衔，问：可否排成3×3方阵，使每行与每列的3名军官既来自不同的军种，又具有不同的军衔级别？
其实，把两个3阶拉丁方迭置成每个元素都是有序数偶的3×3数组，这数偶的第一分量i取自第1个拉丁方，第二的分量j取自第二个拉丁方，即有如下形式：
1 2 3 3 2 1
2 3 1 （ 迭置 ） 2 3 1
3 1 2 || 1 2 3
||
（1,3） （2,1） （3,2）
（2,2） （3,3） （1,1）
（3,1） （1,2） （2,3）
（陆，尉） （海，将） （空，校）
（海，校） （空，尉） （陆，将）
（空，将） （陆，校） （海，尉）
图2-4
其中每项（i，j），i = 1，2，3，对应于陆，海，空，j = 1，2，3，对应于将，校，尉。不难验证每行每列恰有3个军种也恰有3个军衔，这就排成了“9军官问题”的解答。
定义2.2：设A = （aij），B = （bij）是两个n阶拉丁方，如迭置后的n平方个有序偶对（aij，bij）全都为互异，则拉丁方A和B就称为正交的。
并非任意两个同阶拉丁方都可正交。如迭置下面两个3阶拉丁方即不正交。
3 2 1 1 3 2 （3,1） （2,3） （1,2）
2 1 3 （ ，） 3 2 1 （2,3） （1,2） （3,1）
1 3 2 2 1 3 （1,2） （3,1） （2,3）
图2-5
正交拉定方的实用性比单个拉丁方更优越，它能用于2个以上的因素的试验设计问题中。例如：设在某次拉力赛中试验赛车轮胎的磨损情况，现有4种牌号的轮胎：1，2，3，4。一般来说后轮与前轮磨损是不一样的（主动轮与被动轮的差别），左侧与右侧也不一样。为消除车轮位置的偏差，要求在使用A，B，C，D 四辆车的情况下（尽量使用较少的车又能客观的反应磨损情况），使每种牌子的车胎恰好用在每辆车上一次，且在每个位置上一次。可按表2-2进行试验。
表2-2（第i 行、第j 列的元素表示车胎的牌号）车胎磨损的一个拉丁方A试验设计
|
|
A号车
|
B号车
|
C号车
|
D号车
|
|
左前轮
|
1
|
2
|
3
|
4
|
|
右前轮
|
2
|
1
|
4
|
3
|
|
左后轮
|
3
|
4
|
1
|
2
|
|
右后轮
|
4
|
3
|
2
|
1
|
如在上例的基础上，还要加如4种牌号的刹车闸垫对轮胎的磨损的影响。一位缺乏科学知识的人会让A号车全部用1号刹车闸垫；B号车全部用2号刹车闸垫；C号车全部用3号刹车闸垫；D号车全部用4号刹车闸垫；这显然不合理。因为车辆的差异淹没了刹车闸垫对磨损的真实影响。为此要求用拉丁方来设计刹车闸垫试验，并且要求与轮胎的设计“配合”的不重复。也就是找出两种拉丁方设计，A =（aij）和B = （bij）。A拉丁方试验4种牌子的车胎，B拉丁方试验4种牌子的刹车闸垫。并且使有序对（aij，bij ）（i = 1，2，3，4；j = 1，2，3，4）都不相同。不妨取A拉丁方就如表2-2中的形式，B拉丁方取为表2-3中的形式。
表2-3 （第i 行、第j 列的元素表示刹车闸垫的牌号）刹车闸垫对车胎磨损的一个拉丁方A试验设计
|
|
A号车
|
B号车
|
C号车
|
D号车
|
|
左前轮
|
4
|
1
|
2
|
3
|
|
右前轮
|
3
|
2
|
1
|
4
|
|
左后轮
|
1
|
4
|
3
|
2
|
|
右后轮
|
2
|
3
|
4
|
1
|
这样既要顾及轮胎牌子，又要顾及刹车闸垫牌子的有关轮胎磨损综合效果组合试验设计就取为A 和B 的迭置，也就是两个互相正交的拉丁方迭置。
如表2-4
表2-4 （第i 行、第j 列的元素（aij，bij）是车胎牌号aij和刹车闸垫牌号bij组成的有序偶对）
为试验4种不同牌号的车胎和4种不同牌号的刹车闸垫对轮胎磨损组合设计
|
|
A号车
|
B号车
|
C号车
|
D号车
|
|
左前轮
|
（1，4）
|
（2，1）
|
（3，2）
|
（4，3）
|
|
右前轮
|
（2，3）
|
（1，2）
|
（4，1）
|
（3，4）
|
|
左后轮
|
（3，1）
|
（4，4）
|
（1，3）
|
（2，2）
|
|
右后轮
|
（4，2）
|
（3，3）
|
（2，4）
|
（1，1）
|
由此可见，为了设计出科学、经济的试验设计方案，正交拉丁方占有着举足轻重的的地位。下面介绍一下正交拉丁方的一条重要性质：
2.2.2 正交拉丁方的性质
定理2.1：互相正交的n 阶拉丁方的个数不超过n – 1 个，即若 A1，A2，…，Ak 是两两正交的n阶拉丁方，则k≤n – 1 。
证明：设a1，a2 ，…，an 是1，2，…，n的一个排列， = （ l = 1，2，…..，k。若对A1作如下的置换 1 2 … n
a1 a2 ... an
得一方阵 n×n 下面证与A2 ，…，Ak 正交，如若不然，不妨设不与A2 正交，则中至少有一对数偶出现的次数超过1次。设该对数偶为（）在上式中出现不只一次，说明数偶（）在中出现的次数超过一次，这跟A1和A2 互相正交的假定矛盾。这就证明了可以对拉丁方A1 做任一置换
1 2 … n
a1 a2 ... an
得另一拉丁方 以取代 ，不改变，，……的相互正交性。，，……，也有类似的性质。根据这个道理，不妨假定，，……，的第一行都是（1 2…n）。任取1≤l＜m≤k，则方阵的第一行都是（（1，1）（2，2）…（n，n））。“1”不能在第一列中重复出现，故，，……，的第二列元素没有一个取“1”这个数的，而且各不相同。如若不然，则中的书；偶（d，d）至少出现两次：一次是在第一行第d列，一次是在第二行第1列，这与Al与Am互相正交的假定相矛盾。由于，，……，的第2行第1列元素不为1而互不相同，只能分别取2，3，…，n中的1个数，故k≤n – 1。
2.3 完备拉丁方的定义与性质
在拉丁方试验设计中，有时根据试验的需求，需要所用的拉丁方具有一些特殊的性质。例如，在把一块农田分成若干纵横小块做试验且根据一个拉丁方来安排试验时，相邻的二小块的安排之间彼此是有影响的，因而希望每一对可能的安排在所用的拉丁方的相邻位置上出现一次。又如，养鸡场关于饲料对鸡的长势的试验且采用一个拉丁方来安排试验时，接连使用的二种饲料彼此是有影响的，因而也希望每两种不同饲料在所用的拉丁方中都能以不同的次序接连出现一次。这就引出了一类特殊的拉丁方。下面就给出正式的定义。
定义2.3：设A = （aij）是集 S ={ a1，a2，……，am，} 上的一个m阶拉丁方。如果S的每一个有序相异元素偶都在A的行中至少一次出现为相邻（依有序对中的顺序）的一对，则称A是一个行完备拉丁方，又称为水平完备拉丁方。如果在上面的定义中把“行”换为“列”，则称A是一个列完备拉丁方，又称为竖直完备拉丁方。如果A既是行完备拉丁方，又是列完备拉丁方，则称之为一个完备拉丁方。
一个元的相邻元根据其位置可以叫做右邻元、左邻元、上邻元、下邻元。
由此定义，有
引理2.1：在定义2.3中做下述更动，并不影响A的行完备性：
把“S的每一个有序相异元素偶都在A行中至少一次出现为相邻的一对”改为“S的每一个有序相异元素偶都在A的行中至多一次出现为相邻的一对”，或者改为“S的每一个有序相异元素偶都在A的行中恰好一次出现为相邻的一对”。
证明：S 的有序相异元素偶的个数为
m（m —1）
A 的每一行的有序相异元素偶的个数是m – 1，A的诸行的相邻元素偶的个数是m（m —1），因此，S的每一相异元素偶在A的诸行中至少一次出现为相邻元素的充要条件是，S的每一相异元素偶在A的诸行中至多出现一次为相邻元素。
对列完备拉丁方有类似的结果。在引理2.1中把“行”换成“列”，引理的结论仍成立。
引理2.2：对一个拉丁方施行行换序并不改变它是否为行完备拉丁方；对一个拉丁方施行列换序并不改变它是否为列完备拉丁方。
证明：这是定义2.3的直接推论。
2.4 相关于拉丁方的数论领域知识分析
拉丁方尤其是本文下续的最佳拉丁方的构造研究与数论是紧密相连的，可以说数论的发展直接影响到拉丁方分支，它们的元素的构造直接运用到数论里的（剩余系（环）、域、计算表等）基本知识，以下就讨论一些基本的数论知识。
2.4.1 数论的现状
数论是主要研究整数性质的一门古老的学科。由于数论立题新颖、寓意深奥、耐人思索，吸引了古今中外许多具有数学天才和有数学灵感的人们投身于数论的研究，并获得了辉煌的成就。公元前3世纪，古希腊数学家欧几里德（Euclid）证明了素数是无穷的，并给出了求两个正整数的最大公因式的辗转相除算法。我国古代的《孙子算法》中给出了求解一次同余式组的算法，即著名的孙子定理，国外誉为中国剩余定理。从17世纪到19世纪，法国数学家费马（P.de Fermat）、瑞士数学家欧拉（L.Euler）、法国数学家勒让德（A.M.Legendre）和德国数学家高斯（C.F.Gauss）等人的工作都大大发展和丰富了数论的内容。我国从20世纪30年代开始，特别在建国后，以华罗庚教授为首的一批数学家如潘承洞、王元、陈景润等，对数论进行了潜心研究，取得了优秀成果，做出了卓越的贡献。随着现代科学技术的发展，特别是计算机技术的发展，使得这门古老学科又焕发了青春，数论中的一些难题取得了新进展和新突破，并在计算机科学、组合数学、代数编码、密码学和计算方法等领域得到了卓有成效的应用。
2.4.2 重要性质定理
1. 素数和数的互素除数(因子)的概念：
设z为有全体整数而构成的集合，若 b≠0且
使得a=mb,此时称b整除a.记为b∣a,还称b为a的除数(因子).
2. 算术基本定理：任何一个不等于0的正整数a都可以写成唯一的表达式a＝P1α1P2α2…Ptαt，这里P1>P2>P3…>Pt是素数，其中αi>0
最大公约数： 若a,b,c∈z，如果c∣a，c∣b，称c是a和b的公约数。正 整数d称为a和b的最大公约数，如果它满足 d是a和b的公约数。 对a和b的任何一个公约数c有c∣d。 注：1*. 等价的定义形式是： gcd（a,b）＝max{k∣k∣a，k∣b} 若gcd（a,b）=1，称a与b是互素的。全体整数而构成的集合对整数的加法和乘法的两种运算 是封闭的且满足算术运算的所有定律，此时我们称整数 集合z为整数环。整数环z对除法运算不封闭。
3.带余除法：
"a∈z,>0，可找出两个唯一确定的整数q和r,
使a=qm+r, 0<=r< m,q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则m∣a） 整数同余式和同余方程：定义（同余）称整数a模正整数m同余于整数b，并写a≡b（mod m）是指m∣a－b, m称为模数。
注：1*.m∣a-bóa=q1m+r,b=q2m+r即a和b分别 除以m有相同的余数。“同余”二字的来源就在于此。
4.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质：自反性：对任意整数a有a≡a（modm）对称性：如果a≡b(modm)则b≡a（modm） 传递性：如果a≡b (modm）b≡c（modm）则a≡c(modm) 于是，全体整数集合z可按（m>1）分成一些两两不交的等价类。
5.整数模m同余类共有m个，他们分别为mk+0,mk+1, mk+2,…mk+(m-1); k∈z，每一个算类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称[0],[1],[2],…[m-1]为标准完全剩余系。Z模12的标准剩余系为：[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11]
对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘： (1)a(mod m)±b(mod m)=(a±b)(mod m) (2)a(mod m)*b(mod m)=a*b(mod m)
例子.通过同余式演算证明560－1是56的倍数，223－1是47的倍数。 解：注意53=125≡13(mod56) 于是有56≡169≡1(mod56) 对同余式的两边同时升到10次幂，即有56∣560-1。其次, 注意26=64≡-30(mod47), 于是 223=(26)3·25=(26·26)26·25 ≡900*(-30)*(32) mod(47) ≡(7)(-30)*(32) (mod47) ≡1(mod47) 于是有 47∣223-1 定理：(消去率)对于ab≡ac（mod m）来说，若(a,m)＝1则b≡c(mod m)
6.一次同余方程ax≡b(mod m)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b 定理：如记(a,m)=d,则同余方程ax≡b(mod m)有解的充分必要条件是d∣b。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。证明：略。（从ax+my=b入手）
7.整数环z模正整数m得到的剩余类集合可以记为zm(或z/(m)) zm={[0],[1],…,[m-1]} 在4中已说明zm对剩余类的加法，乘法是封闭的，可列出它们的加乘表。（见书214页）。我们称为zm为剩余类环（或同余类环）
8.在整数环z中是没有零因子的，即两个非零整数的乘积一定不等于0，但是剩余环则不然。例z12中：[3]*[4]=[12]=[0] 说明，zm中的元素可分为两类，一类是零因子，即若α∈zm,α≠[0]存在β∈zm且β≠[0]，有α*β=[0]，称α，β都为zm中的零因子。另一类是可逆元，即若α∈zm，存在β∈zm使α*β=[1]，此时α,β互为各自的逆元，记α-1=β；β-1=α 定理：剩余类环zm中元素α=[a]为zm的可逆元ó(a,m)=1 要证明这个定理，只需证明下列引理： 引理：任意两个整数a和b都有一个最大公约数，这样一个最大公约数d可以表示成a,b二数关于整系数的线性组合，即有s,t∈z，使d＝sa＋tb。 证明：不妨设b>0，用辗转相除法，先用b去除a，得a=q1b+r1,0<=r1<b; (1) 如果r1=0，停止，否则再用r1去除b，得 b=q2r1+r2,0<=r2<r1; (2) 如果r2=0，停止，否则再用r2去除r1，得 r1=q3r2+r3;0<=r3<r2;(3)等等，这样一直进行下去，可得一系列关系式： rk-3=qk-1rk-2+rk-1,0<=rk-1<rk-2; (k-1) rk-2=qkrk-1+rk,0<=rk<rk-1; (k)
2.4.3 域的概念
定义：F是至少含有两个元素的集合，对F的元素定义有“+”和“.”两种运算，并满足以下F1，F2，F3三个条件的代数系统<F，+，.>称为域。
F1：F的元素关于“+”运算成交换群，设其单位元素为0。
F2：F\{0}的元素关于“．”运算成交换群。
F3：分配律成立，即对于a，b，c∈F有
a．（b＋c）＝a．b＋a．c
（b＋c）．a＝b．a＋c．a
例：实数的全体、复数的全体关于通常的加法、乘法都是域，分别称为实数域和复数域。
F集合的元素除去元素0以外关于乘法成交换群，其单位元素用1表示。在不引起混乱的情况下就用0和1分别表示F关于“+”，和F\{0}关于“．”运算构成的交换群的单位元素。
集合F的元素个数是有限个时，称为有限域。若p是素数，则F={0，1，2，．．．，p-1}在mod p的意义下关于乘法“．”加法“+”成域。
所谓mod p意义下相等，指的是a = b mod p，即a-b=sp。F 关于加法运算构成交换群，容易给予证明。要证明{1，2，．．．，p-1}关于乘法成交换群，只要证明属于集合中的任一元素a存在逆元素就可以了。由于p是素数，a和p的公因子为1，故唯一地存在整数b和c使得
ab + pc = 1
所以
ab = 1 mod p
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
图2-6
b就是a的逆元素。
． 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1
图2-7
上例验证了p = 5时，F= {0，1，2，3，4 } 在mod 5 的意义下关于“．”，“+”运算成域。然而p不为素数时则不然，这只要从下面的例子就可以看出。p = 6 时就有
+ 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 0
2 2 3 4 5 0 1
3 3 4 5 0 1 2
4 4 5 0 1 2 3
5 5 0 1 2 3 4
图2-8
． 1 2 3 4 5
1 1 2 3 4 5
2 2 4 0 2 4
3 3 0 3 0 3
4 4 2 0 4 2
5 5 4 3 2 1
图2-9
2.5 最佳拉丁方的入门
2.5.1 最佳拉丁方问题的提出
透过以上的这一些一般的拉丁方（基本都是要求行列中每个元素不同），它们的实用价值是很高的。从广义上我们还可以构想出一种更加特殊的拉丁方，比如就说开始2.3中那个要根据一个拉丁方来安排试验的饲料试验，再加一个限制条件，彼此二饲料有影响且要求斜方向相邻的二饲料不能相同，出于要使斜方向与横竖方向标准一样，还要每一斜方向（包含n个元素的平行于拉丁方主对角线或斜对角线的一条连接斜线，其中n为拉丁方的阶数）涵盖所有的待测饲料，如果存在这样的广义方，就按它来安排试验。这样的拉丁方是n阶拉丁方族里的最佳者。下面给出具体的定义。
定义2.4：模ｎ的剩余环(Ｒｎ,⊙, )中
Ｒｎ={0,1,2,…,ｎ-1}
在不致产生混淆时,即以Ｒｎ表(Ｒｎ,⊙, )
以Ｒｎ的元构成的拉丁方如果在每条斜线上都全部出现,就称之为最佳拉丁方,平行于主对角线的斜线叫主斜线,平行于副对角线的斜线叫副斜线。图1是一个最佳拉丁方,(2,0,3,1,4)是一条主斜线,把拉丁方右移过来,便可将主斜线联成一条,在一个拉丁方内它是被截成两段的,同样(1,2,3,4,0)是一条副斜线。
图2-10
2.5.2 最佳拉丁方存在性公式透析
在拉丁方内任取一元ｘ,如果它右边紧邻的元都是ｘ⊙ｈ,便称这个拉丁方的右进间距为ｈ,如果ｘ的下方紧邻的元都是ｘ⊙Ｋ,便称这个拉丁方的下移间距为Ｋ。当右进间距为ｈ时,其左进间距为-ｈ,对ｎ阶拉丁方而言,就是ｎ-ｈ,沿主斜线方向,ｘ的下一元的ｘ⊙Ｋ⊙ｈ,便说主斜间距为Ｋ⊙ｈ,同样可说副斜间距为Ｋ⊙ｎ-ｈ,亦即Ｋ-ｈ。右进间距为ｈ,下移间距为Ｋ的拉丁方记为Ｌhk,图2-10的拉丁方是个Ｌ12,图2-11(ａ)表Ｌhk,(ｂ)表Ｌ12。
图2-11
引理2.3 若(ｎ,Ｋ)=1,则当ｘ遍历Ｒｎ时,Ｋｘ也遍历Ｒｎ。
引理2.4 若(ｎ,Ｋ)=ｇ≠1,则当ｘ遍历Ｒｎ时,Ｋｘ只能遍历Ｒｎ的一个子集,重复ｇ次。例如,ｎ=15,Ｋ=4,(ｎ,Ｋ)=1,
有ｘ=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14.
4ｘ=0,4,8,12,1,5,9,13,2,6,10,14,3,7,11.又
若Ｋ=6,(ｎ,Ｋ)=3,
有ｘ=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14.
6ｘ=0,6,12,3,9;0,6,12,3,9;0,6,12,3,9.
定理2.2 若(ｎ,2)≠1,则ｎ阶拉丁方中无最佳者。
证明 ｎ既为偶数,则ｈ,Ｋ只能为苛,于是Ｋ⊙ｈ为偶,由引理2,Ｒh的元不能在主斜线上
全部出现,故Ｌhk非最佳。
定理2.3 若(ｎ,3)≠1,则ｎ阶拉丁方中无最佳者。
证明 ｎ既为3的倍数,则只能有ｈ=3Ｐ+ｉ(ｉ=1或2),Ｋ=3ｑ+ｊ(ｊ=1或2),于是
Ｋ⊙ｈ=3 (Ｐ⊙ｑ)- (ｉ+ｊ),Ｋ-ｈ=3⊙(ｑ-Ｐ) ⊙ (ｊ-ｉ)
若ｉ=ｊ,则Ｋ-ｈ为3的倍数,若ｉ≠ｊ,则Ｋ⊙ｈ为3的倍数,由引理2,Ｒh的元总会在某种
斜线上不能全部出现,故Ｌhk非最佳。
定理2.4 如果(ｎ,ｈ)=(ｎ,Ｋ)=(ｎ,Ｋ⊙ｈ)=(ｎ,Ｋ-ｈ)=1,则Ｌhk是个最佳拉丁方。
证明 因这时Ｒn的元在各行、各列、各斜线上都全部出现。
理解了最佳拉丁方存在性的条件，下面将进入近一步探讨。
2.6 二维方块染色问题与对应最佳拉丁方存在构造的深入研究
2.6.1 二维方块染色问题的提出及其相关规定
问题2.1：在二维平面内，把一个由n×n个小格构成的方块染色，使得同行、同列以及同斜线的小格颜色不相同，最少需要多少种颜色。当且仅当染色后，同行、同列、同斜线的各小格颜色不同时，才称之为“染色”，因此问题可以简化为“方块染色，最少要多少种颜色？”。按逻辑说，起码是要n种颜色的，如果存在n阶最佳拉丁方，就只要n种颜色。
定义2.5：方块中若干小格，如果有两个小格同行、同列、同斜线。则称为相关；否则称为无关。
规定2.1：矩阵中方块的序号：方块中的行序号，自上而下，依次为0，1，2，．．．，n-1；列序号自左至右依次为0，1，2，．．．，n-1；平行于主对角线的斜线称为主斜线，其序号的规定为 主对角线是0，此外自上而下依次为1，2，．．．，n-1；平行于副对角线的斜线称为副斜线，其序号规定为副对角线是0，此外自上而下依次是1，2，．．．，n-1；。我用a表示某小方格的行序号，b表示列序号，h表示主斜线序号，k表示副斜线序号，则每个小方格都有一个序号数组S =（a，b，h，k ）。Jn = （{0，1，2，．．．，n-1}，+，.）表模n的剩余环，于是a∈Jn ，b∈Jn，h∈Jn，k∈Jn。并且对a，b，h，k进行的运算，全在Jn内进行。
则相关问题即是两格的S中有不少于一个元素相等，则相关，否则无关。
例如：在如下一个3×3的方阵中，
|
A B C
D E F
G H I
|
图2-12
F小格在第1行，第2列，主斜线为2，副斜线为1。即其序号数组 S = （1，2，2，1）
G小格在第2行，第0列，主斜线为2，副斜线为0。即其序号数组 S = （2，0，2，1）
F与G小格的S中有h都等于2，即同一主斜线，则F与G小格相关。
引理2.5：h = a-b, k = a+b+1.（显然）
这里的运算，可以直接用域概念里的加法表来实现。
把各行的行序号a 加上整数e，（e∈Jn），然后按行序号0，1，2，．．．，n-1顺序将行重新排列，这样的变换称为行变换。同样也可以对列这样进行列变换。
引理2.6：对方块（矩阵）进行行、列变换，不改变方块内的各小格的相关性。
证：显然同一行，同一列内的格子不变。由h = a+b, k = a+b+1，同一主斜线上的格子不变，因为都由h变成了h’，同理，同一副斜线上的格子，都由k变成了k’。即同一斜线上的格子也不变，引理2．6得证。
有了以上的概念、规定、和引理，下面就可以开始研究“染色”问题了。
图表规则（用三角形“△”表示选定的做相关参考的方块，用“×”表示与选定的做相关参考的方块有关的方块，用其它英文字母表示与选定的做相关参考的方块无关的方块。）
2.6.2 1 到 7阶方块染色的分析与对应最佳拉丁方的存在构造
I. 先来看2×2方块：
△ ×
× ×
1 2
3 4
图2-13 图2-14
很明显，4个小方格都是两两相关，所以对它染色任两格不能同色，要4种颜色，如图2-13与图2-14我们用1，2，3，4表示，所以不存在2×2阶最佳拉丁方。
II. 对于3×3方块：
由引理2.5和引理2.6在3×3方块任意一个格子都可以经过行、列变换，变换到第0行第0列，而不改变方块各个格子的相关性。所以不妨取第0行、第0列那个格子，并划去与之相关的格子，剩下的格子如图2-15，即没有剩下一格，也就意味着3×3方块任意2格相关，所以对它染色任2格不能同色，要9种颜色。如图2-16。
△ × ×
× × ×
× × ×
1 2 3
4 5 6
7 8 9
图2-15 图2-16
所以不存在3阶最佳拉丁方。
III. 对于4×4方块：
由引理2.5和引理2.6在4×4方块任意一个格子都可以经过行、列变换，变换到第0行第0列，而不改变方块各个格子的相关性。所以不妨取第0行、第0列那个格子，并划去与之相关的格子，剩下各小格如图2-17，记为A1，A2，A3，A4。显然A1，A2，A3，A4两两相关，因而至多只能取1格，即4×4方块，任意3格相关。所以对它染色时，同颜色的小格最多只能有2格，所以最少需要4×4/2 = 8种颜色（我们用1，2，3，4，5，6，7，8表示），如图2-18。
△ × × ×
× × A1 ×
× A2 × A4
× × A3 ×
1 2 3 4
3 4 1 2
5 6 7 8
7 8 5 6
图2-17 图2-18
所以不存在4阶最佳拉丁方。
IV. 对于5×5方块：
由引理2.5和引理2.6在5×5方块任意一个格子都可以经过行、列变换，变换到第0行第0列，而不改变方块各个格子的相关性。所以不妨取第0行、第0列那个格子，并划去与之相关的格子，剩下各小格如图2-19，A1，A2，A3，A4，B1，B2，B3，B4。
|
△ × × × ×
× × A1 B1 ×
× A2 × × B2
× B4 × × A4
× × B3 A3 ×
|
图2-19
随着方块阶数的加高，以后的各方块的相关性用肉眼来观察容易混淆，，所以不妨由引理2.5和引理2.6通过计算每一个方块的序数组S（a,，b，h，k），再由比较S来确定诸方格的相关性，(计算机算法程序附后)
A1（a12,s (1,2,4,4)）与之不相关的方格为（a00 , a04 , a20 , a24 , a31 , a33 , a41 , a43）
B1(a13,s (1,3,3,0)) 与之不相关的方格为（ a00 , a01 , a20 , a21 , a32 , a34 , a42 , a44）
A2(a21, s (2,1,1,4)) 与之不相关的方格为( a00 , a02 , a13 , a14 , a33 , a34 , a40 , a42)
B2(a24 , s (2,4,3,2)) 与之不相关的方格为 (a00 , a03 , a11 , a12 , a31 , a32 , a40 , a43 )
B4(a31 ,s (3,1,2,0)) 与之不相关的方格为 ( a00 , a02 , a10 , a12 , a23 , a24 , a43 , a44)
A4(a34 , s (3,4,4,3)) 与之不相关的方格为(a00 , a03 , a10 , a13 , a21 , a22 , a41 , a42)
B3(a42 , s ( 4,2,2,2)) 与之不相关的方格为(a00 , a04 , a11 , a13 , a21 , a23 , a30 , a34)
A3(a43 , s (4,3,1,3)) 与之不相关的方格为 (a00 , a01 , a12 , a14 , a22 , a24 , a30 , a31)
于是在所剩A1，A2，A3，A4，B1，B2，B3，B4中可以选出一条方案使得其各不相关为
A1 (a12)----- B2(a24)----- B4(a31)----- A3(a43),再加上a00 ，一共是5个格子，也就是说有5
个格子，各不相关，所以5×5方块中任意6格相关，则在染色时最多5格同色，所以最少
需要5×5/5 = 5 种颜色（我们用1，2，3，4，5表示），如图2-20。
|
5 1 2 3 4
3 4 5 1 2
1 2 3 4 5
4 5 1 2 3
2 3 4 5 1
|
图2-20
所以存在5阶最佳拉丁方。
V. 对于6×6方块：
由引理2.5和引理2.6在6×6方块任意一个格子都可以经过行、列变换，变换到第0行第0列，而不改变方块各个格子的相关性。所以不妨取第0行、第0列那个格子，并划去与之相关的格子，剩下各小格如图2-21，（A1，A2，A3，A4），（B1，B2，B3，B4），（C1，C2，C3，C4），（D1，D2，D3，D4）。
|
△ × × × × ×
× × C1 A1 D1 ×
× C2 × B1 × D4
× A2 B2 × B4 A4
× D2 × B3 × C4
× × D3 A3 C3 ×
|
图2-21
相关性(在所剩方格中)计算：
C1(a12,s(1,2,5,4))不相关于(a25, a31 , a35 , a41 , a43 , a53)
A1(a13,s(1,3,4,5))不相关于(a21 , a25 , a32 , a34 , a41 , a45 , a52 , a54)
D1(a14,s(1,4,3,0))不相关于(a21,a31,a35,a43,a45,a53)
C2(a21,s(2,1,1,4))不相关于(a13,a14,a34,a35,a52,a53)
B1(a23,s(2,3,5,0))不相关于(a31,a35,a52,a54)
D4(a25,s(2,5,3,2))不相关于(a12,a13,a31,a32,a53,a54)
A2(a31,s(3,1,2,5))不相关于(a12,a14,a23,a25,a43,a45,a52,a54)
B2(a32,s(3,2,1,0))不相关于(a13,a25,a45,a53)
B4(a32,s(3,4,5,2))不相关于(a13,a21,a41,a53)
A4(a35,s(3,5,4,3))不相关于(a12,a14,a21,a23,a41,a43,a52,a54)
D2(a41,s(4,1,3,0))不相关于(a12,a13,a34,a35,a53,a54)
B3(a43,s(4,3,1,2))不相关于(a12,a14,a31,a35)
C4(a45,s(4,5,5,4))不相关于(a13,a14,a31,a32,a52,a53)
D3(a52,s(5,2,3,2))不相关于(a13,a21,a23,a31,a35,a45)
A3(a53,s(5,3,2,3))不相关于(a12,a14,a21,a25,a32,a34,a41,a45)
C3(a54,s(5,4,1,4))不相关于(a13,a23,a25,a31,a35,a41)
于是在所剩方格里可以选出一条方案使得其各不相关为：C1(a12)-----D4(a25)-----A2(a31)
，再加上a00，一共是4个格子，也就是说有4个格子，各不相关，所以6×6方块中任意5
格相关，则在染色时最多4格同色，所以最少需要6×6/4 = 9 种颜色（我们用1，2，3，4，
5，6，7，8，9表示），如图2-22。
|
1 2 3 4 5 6
3 4 5 6 7 8
6 7 8 9 4 5
8 9 1 2 6 7
2 3 7 8 9 1
4 5 9 1 2 3
|
图2-22
所以不存在6阶最佳拉丁方。
VI. 对于7×7方块：
在7阶拉丁方中，由引理2.5和引理2.6来制作染色，划去与a00 不相关的方格后将剩下24格，它们分别H(a12)-----I(a13)-----M(a14)-----Q(a15)-----A(a21)-----J(a23)-----N(a24)-----
U(a26)-----B(a31)-----E(a32)-----R(a35)-----V(a36)-----C(a41)-----F(a42)-----S(a45)-----W(a46)---
--D(a51)-----K(a53)-----O(a54)-----X(a56)-----G(a62)-----L(a63)-----P(a64)-----T(a65)（如图2-23）
下面以它们的S(a,b,h,k)序数组分类列出：
|
△ × × × × × ×
× × H I M Q ×
× A × J N × U
× B E × × R V
× C F × × S W
× D × K O × X
× × G L P T ×
|
图2-23
下面以它们的S(a,b,h,k)序数组分类列出：
表2-5
|
格子
序数组a
|
|
|
|
|
|
1
|
H
|
I
|
M
|
Q
|
|
2
|
A
|
J
|
N
|
U
|
|
3
|
B
|
E
|
R
|
V
|
|
4
|
C
|
F
|
S
|
W
|
|
5
|
D
|
K
|
O
|
X
|
|
6
|
G
|
L
|
P
|
T
|
表2-6
|
格子
序数组b
|
|
|
|
|
|
1
|
A
|
B
|
C
|
D
|
|
2
|
H
|
E
|
F
|
G
|
|
3
|
I
|
J
|
K
|
L
|
|
4
|
M
|
N
|
O
|
P
|
|
5
|
Q
|
R
|
S
|
T
|
|
6
|
U
|
V
|
W
|
X
|
表2-7
|
格子
序数组h
|
|
|
|
|
|
1
|
A
|
E
|
O
|
T
|
|
2
|
B
|
F
|
K
|
P
|
|
3
|
Q
|
U
|
C
|
L
|
|
4
|
M
|
V
|
D
|
G
|
|
5
|
I
|
N
|
R
|
W
|
|
6
|
H
|
J
|
S
|
X
|
表2-8
|
格子
序数组k
|
|
|
|
|
|
0
|
Q
|
N
|
F
|
D
|
|
2
|
G
|
K
|
R
|
U
|
|
3
|
L
|
O
|
S
|
V
|
|
4
|
H
|
A
|
P
|
W
|
|
5
|
I
|
B
|
T
|
X
|
|
6
|
M
|
J
|
E
|
C
|
由以上的4个表可以选出一条方案，使得其各不相关，A (a21)-----F(a42)-----I(a13)-----V(a36)，再加上a00一共5格，也就是说在7×7方块中任意6格相关，所以染色时只能有5格同色，7×7/5！= 7，所以不存在7阶最佳拉丁方，但是实际上我可以对7×7方块这样染色（图2-24）：
|
7 1 2 3 4 5 6
5 6 7 1 2 3 4
3 4 5 6 7 1 2
1 2 3 4 5 6 7
6 7 1 2 3 4 5
4 5 6 7 1 2 3
2 3 4 5 6 7 1
|
图2-24
所以这里与由引理2.5和引理2.6推出的设计方案矛盾，所以此方案不适合7阶以上的最
佳拉丁方判定设计。
2.6.3 一种二维最佳拉丁方构造方法
鉴于前面所定义的最佳拉丁方，即要在拉丁方的每一条斜线上出现Rn中的所有元素，由于每条斜线上的元素个数与每行每列一样，都是n个，所以结合起来也就是说，如若n阶最佳拉丁方存在的话，那就是这个拉丁方的每行、每列、每条歇线上的元素均不同，那样n个元素都必须要出现。
设一个n阶拉丁方族存在最佳者，则Rn =（0,1,2,…,ｎ-1），Jn = （Rn，+，.）那么可以从方块的第一行开始，第一列元素定为n-1，然后后面的列元素依次加1（运算在Jn内进行）直到最后一列。
然后第二行的第一列元素定为第一行第一列元素减2（运算在Jn内进行），后面的列元素依次加1（运算在Jn内进行）直到最后一列。
后面的行第一列元素依次件2（运算在Jn内进行），而此行的后列元素依然是依次加1（运算在Jn内进行）。执行上面的操作直到n行n行元素全部填满，这个拉丁方即每行、每列、每条歇线上的元素均不同，则得出一个n阶最佳拉丁方。
例如对于11阶拉丁方族：
用上面的算法，第一行元素应该是：
10...0...1...2...3...4...5...6...7...8...9
第二行元素应该是：
8...9...10...0...1...2...3...4...5...6...7
依次下去，最后得出的结果是：
10...0...1...2...3...4...5...6...7...8...9
8...9...10...0...1...2...3...4...5...6...7
6...7...8...9...10...0...1...2...3...4...5
4...5...6...7...8...9...10...0...1...2...3
2...3...4...5...6...7...8...9...10...0...1
0...1...2...3...4...5...6...7...8...9...10
9...10...0...1...2...3...4...5...6...7...8
7...8...9...10...0...1...2...3...4...5...6
5...6...7...8...9...10...0...1...2...3...4
3...4...5...6...7...8...9...10...0...1...2
1...2...3...4...5...6...7...8...9...10...0
这就是一个11阶最佳拉丁方。
2.7 三维立体方块染色问题的深入研究与对应最佳立体拉丁方的思考
2.7.1 三维立体拉丁方
在拉丁方试验中，除了平面的，也会有立体的，构想一种试验，若有一块地用做某一作物的A，B，C三种不同品种的试验田。按照2.1.1中的安排，设计方案应为图2-2，现在若考虑这种作物在一年内的不同时段里因气候条件差异而带来的影响，则此方案还应加如一个因素，即时间。那么可以这样来设计，把一年分成三个时间段，使得每个时间段内都有如2.1.1中的方案，并且每种作物在不同时间段里的试验又成拉丁方排列，综上所述，较为合理的试验方案如图2-25。
俯视
俯视
俯视
C A B
B C A
A B C
A B C
C A B
B C A
B C A
A B C
C A B
第一层
第二层
第三层
图2-25
图中第一层代表一年内第一时间段，第二层代表一年内第二时间段，第三层代表一年内第三时间段。右边为左边的方案的俯视图，这样一个方案组成的一个3×3×3的立体方块就是一个广义三维立体拉丁方。
它还可以用于许多实际立体问题或者是能转化成立体问题的拉丁方试验。比如一幢高楼大厦里的若干层是用于电子通讯的，要求层与层接触的房间还有相邻房间应该尽量不产生干扰，那就要求这些两两相邻房间发射的电子波长不相同（原理：波长相等的两列波产生干扰），如果房间全部用不同波长的电子波进行通讯，那么接收器和发射器就要很多，所以我们可以只要求两两相邻的房间波长不等，那么就可以按广义立体三维拉丁方来安排房间和电子波。
还有许许多多诸如此类问题可以用广义立体三维拉丁方来生成解决方案，譬如柜厨藏药等等。
我们在这个基础上给它下一个基于平面拉丁方的定义。
定义2.6 n个不同的符号，通常就取整数1，2，….，n。在一个n×n×n的三维数组中，排列这n个整数，使得任意两维形成的所有n个平面（整个三维拉丁方中一共3n个）都是一个平面上拉丁方，则这n阶立体方块就称之为n阶广义三维立体拉丁方。
2.7.2 三维立体拉丁方的具体构造方法
定义好了三维立体拉丁方，我们具体来看看它的构造方法。
由三维立体拉丁方的定义出发，要求任意两维形成的平面都是拉丁方，定义三维空间内的三个坐标轴X，Y，Z，如图2-26。
2
1
0
0 1 2
Z
Y
X
O (0,0,0)
图2-26
首考虑任意两维平面段的第一层平面，先从X-Y（Z=0）平面开始，依照规定2.1，从过原点的副斜线开始，依次赋值为0，1，2，…，n-1直到最底端的副斜线，这样一来X-Z（Y=0）平面过原点的副斜线为1，则可以依次往下定副斜线为2，3，…，n-1，0。此时Y -Z（X=0）平面过原点的副斜线也为1，也可以依次往下定副斜线为2，3，…，n-1，0。然后，每一两维的第二层平面靠原点的副斜线自然就定为2，在这个第二层平面内的往下的副斜线就定为3，4，…，2。然后这一两维的第三层平面靠原点的副斜线自然是3，此平面内的副斜线同理往后推一个数字；按这样的规律把整个三维拉丁方排完，它所有3n个平面都会是拉丁方。我们具体来看几个例子。
I. 对于4阶的三维方块（12个面）：
按以上规律，构造好的三维方块。
X-Y（Z=0）面俯视如图2-27（a）： X-Y（Z=1）面俯视图2-27（b）：
0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2
1 2 3 0
2 3 0 1
3 0 1 2
0 1 2 3
图2-27（a） 图2-27（b）
X-Y（Z=2）面俯视如图2-27（c）： X-Y（Z=3）面俯视如图2-27（d）：
2 3 0 1
3 0 1 2
0 1 2 3
1 2 3 0
3 0 1 2
0 1 2 3
1 2 3 0
2 3 0 1
图2-27（c） 图2-27（d）
X- Z（Y=0）面俯视如图2-28（a）： X- Z（Y=1）面俯视如图2-28（b）：
0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2
1 2 3 0
2 3 0 1
3 0 1 2
0 1 2 3
图2-28（a） 图2-28（b）
X- Z（Y =2）面俯视如图2-28（c）： X- Z（Y =3）面俯视如图2-28（d）：
2 3 0 1
3 0 1 2
0 1 2 3
1 2 3 0
3 0 1 2
0 1 2 3
1 2 3 0
2 3 0 1
图2-28（c） 图2-28（d）
Y- Z（X=0）面俯视如图2-29（a）： Y- Z（X=1）面俯视如图2-29（b）：
0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2
1 2 3 0
2 3 0 1
3 0 1 2
0 1 2 3
图2-29（a） 图2-29（b）
Y- Z（X =2）面俯视如图2-29（c）： Y- Z（X =3）面俯视如图2-29（d）：
2 3 0 1
3 0 1 2
0 1 2 3
1 2 3 0
3 0 1 2
0 1 2 3
1 2 3 0
2 3 0 1
图2-29（c） 图2-29（d）
II. 对于5阶的三维方块（15个面）：
按以上规律，构造好的三维方块。
X-Y（Z=0）面俯视如图2-30（a）： X-Y（Z=1）面俯视如图2-30（b）：
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3
0 1 2 3 4
图2-30（a） 图2-30（b）
X-Y（Z=2）面俯视如图2-30（c）： X-Y（Z=3）面俯视如图2-30（d）：
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
3 4 0 1 2
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
图2-30（c） 图2-30（d）
X-Y（Z=4）面俯视如图2-30（e）：
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
图2-30（e）
X-Z（Y=0）面俯视如图2-31（a）： X-Z（Y=1）面俯视如图2-31（b）：
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3
0 1 2 3 4
图2-31（a） 图2-31（b）
X-Z（Y=2）面俯视如图2-31（c）： X-Z（Y=3）面俯视如图2-31（d）：
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
3 4 0 1 2
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
图2-31（c） 图2-31（d）
X-Z（Y=4）面俯视如图2-31（e）：
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
图2-31（e）
Y-Z（X=0）面俯视如图2-32（a）： Y-Z（X=1）面俯视如图2-32（b）：
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3
0 1 2 3 4
图2-32（a） 图2-32（b）
Y-Z（X=2）面俯视如图2-32（c）： Y-Z（X=3）面俯视如图2-32（d）：
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
3 4 0 1 2
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
图2-32（c） 图2-32（d）
Y-Z（X=4）面俯视如图2-32（e）：
4 0 1 2 3
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
图2-32（e）
经过对所有面的验证，确实都是拉丁方，所以总体上以上两个立体三维方块分别是4阶三维拉丁方与5阶三维拉丁方。对于n阶三维方块也是一样的，那么上面的对于三维立体拉丁方的构造方法是可行的。
现在再来看以上的方块的各个面，可惜发现构造的n阶三维立体拉丁方的第i行（坐标X）,j列（坐标Y）,k层（坐标Z）的元素为i+j+k，当然，运算在规定2.1中提到的剩余环Jn = （{0，1，2，．．．，n-1}，+，.）中进行。在4阶三维立体拉丁方中（必须是以上的构造方法）验证第1行，第0列，第1层的元素，它应该为i+j+k=1+0+1=2，到构造出来的4阶实例中去检验，确实第1行，第0列，第1层的元素为2。
在三维立体拉丁方的基础上，现在我们来看看三维空间的染色讨论。
2.7.3 三维染色问题的提出及其相关规定
问题2.2：如若把以上的方法推广到三围立体空间中来，染色问题即是在三个坐标轴形成的三个平面内，同行、同列、同斜线，以及同大斜线内的小块颜色各不相同，最少要多少种颜色。为了顺利的从二维平面过渡到三维立体空间中来查看立方体中的各小方块的相关性，先要把以前的定义及规定重新引申一下。
规定2.2：首先在三维空间中三坐标轴（x，y，z）会形成三个平面，设其为α（x轴与y轴交汇而成），β（x轴与z轴交汇而成），γ（y轴与z轴交汇而成），这样一来对于三个平面都有所属的行序号、列序号、主斜线序号、副斜线序号，坐标系原点O（0，0，0），立体拉丁方方块在坐标系中的位置如下图2-33：
2
1
0
0 1 2
Z
Y
X
O (0,0,0)
图2-33
矩阵中小方块的序号：小方块中的行序号（相对于所属平面α或β或γ），自原点而下次为0，1，2，．．．，n-1；列序号（相对于所属平面α或β或γ）自原点而下依次为0，1，2，．．．， n-1；各个平面的主对角线都是过原点或平行于过原点的那一条对角线，另一条对角线定为副对角线，平行于主对角线的斜线称为主斜线，大斜线（主副）即是立方体的4根大对角线（主副各2）以及平行于其的在同一大对角线的隶属平面的斜线。其序号的规定为 主对角线是0，此外自上而下依次为1，2，．．．，n-1；平行于副对角线的斜线称为副斜线，其序号规定为副对角线是0，此外自上而下依次是1，2，．．．，n-1；。我用x表示某小方块的行序号，y表示列序号，z表示层序号，h表示主斜线序号，k表示副斜线序号，这里的h与k是相对与不同坐标平面而言的，在α内，则hα，kα；在β内，则hβ，β；在γ内，则hγ，kγ。则每个小方块都有一个序号数组S =（x，y，z，hi，ki，[i=αβ，γ] ）。Jn = （{0， 1，2，．．．，n-1}，+，。）表模n的剩余环，于是a∈Jn ，b∈Jn，h∈Jn，k∈Jn。并且对a， b，h，k进行的运算，全在Jn内进行。
引理2.7：在平面α内，hα=x – y ; kα= x + y + 1 。
在平面β内，hβ= – (x – z) ; kβ= x + z + 1 。
在平面γ内，hγ= – (y – z) ; kγ= y + z + 1 。
引理2.8：把各行（x）序号加上整数e（e∈Jn），然后行（x）序号按序号0，1，2，．．．n-1
顺序将行（x）重新排列，这样的变换称为行（x）变换，同样也可以进行列（y）变换，层
（z）变换。与引理2.2一样，这样改变也不会改变各小方块的相关性。从二围平面引申到三围立体空间，我把立方体拉丁方各小方块的相关性定义为如下。
定义2.7：
1) 坐标系中两个坐标轴值相等；
2) 一个坐标轴值相等，其余二个坐标轴交汇形成的平面有h或k相等或都相等，例如x相等，hγ相等。
3) 无一坐标轴值相等，则看是否属于同一平面上的同一大斜线。这里又分六种情况：
i. 如两小方块都有x=y，则同属于（x=y，z）这个平面<大斜线所在平面>，再（x,y）与z组成h 或者k运算，这里（x=y，z）平面上的运算同β平面上的运算等效，不妨取x与z; hβ= – (x – z) ; kβ= x + z + 1 。如若有{ hβ，kβ}的非空子集相等，则表明两小方块属于同一大斜线，则两小方块相关。
ii. 如两小方块都有x=z，则同属于（x=z，y）这个平面<大斜线所在平面>，再（x,z）与y组成h 或者k运算，这里（x=z，y）平面上的运算同γ平面上的运算等效，不妨取y与z; hγ= – (y – z) ; kβ= y+ z + 1 。如若有{ hγ，kγ}的非空子集相等，则表明两小方块属于同一大斜线，则两小方块相关。
iii. 如两小方块都有y=z，则同属于（y=z，x）这个平面<大斜线所在平面>，再（y,z）与x组成h 或者k运算，这里（y=z，x）平面上的运算同β平面上的运算等效，不妨取x与z; hβ= – (x – z) ; kβ= x + z + 1 。如若有{ hβ，kβ}的非空子集相等，则表明两小方块属于同一大斜线，则两小方块相关。
iv. 如两小方块都有x+y=n-1 , 则属于x+y=n-1这个平面<大斜线所在平面>，再（x,y）与z组成h 或者k运算，这里（x+y=n-1，z）平面上的运算同γ平面上的运算等效，不妨取y与z; hγ= – (y – z) ; kβ= y+ z + 1 。如若有{ hγ，kγ}的非空子集相等，则表明两小方块属于同一大斜线，则两小方块相关。
v. 如两小方块都有x+z=n-1 , 则属于x+z=n-1这个平面<大斜线所在平面>，再（x,z）与y组成h 或者k运算，这里（x+z=n-1，y）平面上的运算同γ平面上的运算等效，不妨取y与z; hγ= – (y – z) ; kβ= y+ z + 1 。如若有{ hγ，kγ}的非空子集相等，则表明两小方块属于同一大斜线，则两小方块相关。
vi. 如两小方块都有y+z=n-1 , 则属于y+z=n-1这个平面<大斜线所在平面>，再（y,z）与x组成h 或者k运算，这里（y+z=n-1，x）平面上的运算同β平面上的运算等效，不妨取x与z; hβ= – (x – z) ; kβ= x + z + 1 。如若有{ hβ，kβ}的非空子集相等，则表明两小方块属于同一大斜线，则两小方块相关。
2.7.4 1 到 5阶立体方块染色分析与对应最佳立体拉丁方的思考
基于三未立体空间内小方块的相关性难以从图中用肉眼直接观察，下面的探讨我只列出形状图，相关性用以上的规定设计出的计算机算法来通过计算机验证（计算机算法程序附后）。
Ⅰ. 对于2×2×2立体方块：
O (0,0,0)
Z
X
Y
图2-34
由引理2.7和引理2.8和定义2.7，任意一小方块都可以经过行列层变换到坐标值为（0，0，0）的那一小块，不妨就取（0，0，0）这一小块，然后清除与其相关的小方块，无剩余小方块，所以在2×2×2立体方块中任意两小方块相关，所以至少要8种颜色。
Ⅱ. 对于3×3×3立体方块：
|
O (0,0,0)
|
|
Z
|
|
X
|
|
Y
|
图2-35
由引理2.7和引理2.8和定义2.7，任意一小方块都可以经过行列层变换到坐标值为（0，0，0）的那一小块，不妨就取（0，0，0）这一小块，然后清除与其相关的小方块，无剩余小方块，所以在3×3×3立体方块中任意两小方块相关，所以至少要27种颜色。
Ⅲ. 对于5×5×5立体方块：
O (0,0,0)
Z
X
Y
图2-36
由引理2.7和引理2.8和定义2.7，任意一小方块都可以经过行列层变换到坐标值为（0，0，0）的那一小块，不妨就取（0，0，0）这一小块，然后清除与其相关的小方块，剩余小方块： a012-----a013-----a021-----a024-----a031-----a034-----a042-----a043-----a102-----a103-----a112-----a113-----a120-----a121-----a122-----a123-----a124-----a130-----a131-----a132-----a133-----a134-----a142-----a143-----a201-----a204-----a210-----a211-----a212-----a213-----a214-----a221-----a224-----a301-----a304-----a310-----a311-----a334-----a340-----a341-----a342-----a343-----a344-----a402-----a403-----a412-----a413-----a420-----a421-----a422-----a423-----a424-----a430-----a431-----a432-----a433-----a434-----a442-----a443。
在这些剩余小方块中可选出一条方案再加上a000，使得其都不相关为：a000...a012…a024…a031…a043。所以在5×5×5立体方块中可以选出5小方块各不相关，所以任意6小块相关，所以至少要25种颜色。
同理，此方法也适用于6阶以上的三维立体拉丁方，鉴于后附算法，这里不再赘述。
广义三维最佳拉丁立方按平面上的最佳拉丁方来看，就是要任意两维形成的所有n个平面（整个三维拉丁方中一共3n个）都是最佳拉丁方，并且过4条大对角线的6个斜面也都要是最佳拉丁方，即一共3n+6个面都要是最佳拉丁方，它才是一个最佳拉丁立方。那么对于以上讨论的广义的三维立体染色问题，对于一个n×n×n广义三维立体拉丁方族，若染色只需要n种颜色，则存在n阶三维立体最佳拉丁方。
但是，在[9]参考文献中，三维最佳拉丁立方被定义成除了上面说的3n+6个面都要是最佳拉丁方之外，还有就是在大对角线两旁平行于大对角斜面的两个元素加起来是n×n的两个斜面是最佳拉丁方，按[9]的观点来说，最佳拉丁立方存在的充分条件是阶数n与2，3，5，7互素的，也就是说最低是11阶。详细论述见[9]与译文。
第三章 染色及其对应最佳拉丁方分析的计算机算法实现
3.1 二维方块染色分析计算机实现
程序名：XYLDF
程序功能：10阶以内（含10阶）二围染色问题相关性判断，方案选择，最少任意相关格数推算，最多同色格数推算，染色最少色数推算。
程序I/O（输入输出）：输入二围方块阶数，经过程序处理，顺序输出此阶数的二围方块矩阵（a[0][0] ~ a[n-1][n-1]），与a[0][0]不相关的方格矩阵（相关方格在此矩阵中用*表示），与a[0][0]不相关的方格汇总横排输出，一条基于a[0][0]的互不相关的方格方案输出，在此阶方块中最少任意相关格数输出，在此阶方块中最多同色格数输出，在此阶方块中染色最少色数输出。
程序源码：
#include<stdio.h>
#include<math.h>
int n;
int b[100],c[100];
int i,j;
int m=0;
int q=0;
int count=0;
int h,k,h1,k1;
int flag=0;
int d[100],e[100];
main()
{
set1:
printf("please input the square's order:\n");
printf("\n");
scanf("%d",&n);
if(n<=1 || n>10 )
goto set1;
printf("this is %d*%d square you required:\n",n,n);
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{ if(j!=0 && j%(n-1)==0)
printf("a%d%d\n\n",i,j);
else printf("a%d%d....",i,j);
}
}
printf("\n");
printf("\n");
printf("this is the square irrelating a00\n");
i=0;
j=0;
h=0;
k=0;
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{ h=i-j;
k=i+j+1;
if(h<0)
h=h+n;
if(k>(n-1))
k=k-n;
if(j!=0 && j%(n-1)==0)
if(i==0 || j==0 || h==0 || k==1)
printf("*\n\n");
else {printf("a%d%d\n\n",i,j);
b[m]=i;
c[m]=j;
m=m+1;
}
else
if(i==0 || j==0 || h==0 || k==1)
printf("*....");
else {printf("a%d%d..",i,j);
b[m]=i;
c[m]=j;
m=m+1;
}
}
}
b[m]=200;
c[m]=200;
printf("total is:");
for(m=0;m<100;m++)
{ if(b[m]!=200 && c[m]!=200)
{ count=count+1;
printf("a%d%d...",b[m],c[m]);
}
else
break;
}
printf("\n");
printf("\n");
printf("this is one of the irrelevant elements' choice:\n ");
printf("a00....");
d[0]=b[0];
e[0]=c[0];
d[1]=200;
e[1]=200;
i=0;
m=0;
h=0;
k=0;
h1=0;
k1=0;
while(m<count)
{ q=0;
flag=0;
while(d[q]!=200 && e[q]!=200)
{ h=b[m]-c[m];
k=b[m]+c[m]+1;
h1=d[q]-e[q];
k1=d[q]+e[q]+1;
if(h<0)
h=h+n;
if(k>(n-1))
k=k-n;
if(h1<0)
h1=h1+n;
if(k1>(n-1))
k1=k1-n;
if(b[m]!=d[q] && c[m]!=e[q] && h!=h1 && k!=k1)
{ q=q+1;
continue;}
else { flag=1;break;}
}
if(flag==0)
{
d[q]=b[m];
e[q]=c[m];
q++;
d[q]=200;
e[q]=200;
}
m++;
}
i=0;
while(d[i]!=200 && e[i]!=200)
{ printf("a%d%d....",d[i],e[i]);
i=i+1;
}
printf("\n");
printf("\n");
count=0;
q=0;
while(d[q]!=200 && e[q]!=200)
{ count=count+1;
q=q+1;
}
printf("%d elements relate at random in this %d*%d square \n\n",count+2,n,n);
printf("so the num of elements with the same color at most is %d in this %d*%d square\n\n",count+1,n,n);
printf("so at least %d different kinds of color can dye this %d*%d square\n",n*n/(count+1),n,n);
}
程序I/O示例截图：
3.2 三维方块染色分析计算机实现
程序名：3D
程序功能：10阶以内（含10阶）三围立体染色问题相关性判断，方案选择，最少任意相关小方块数推算，最多同色小方块数推算，染色最少色数推算。
程序I/O（输入输出）：输入三围立体方块阶数，经过程序处理，顺序输出此阶数的三围立体方块中与a[0][0][0]不相关的小方块汇总横排，一条基于a[0][0]的互不相关的方格方案输出，在此阶方块中最少任意相关格数输出，在此阶方块中最多同色格数输出，在此阶方块中染色最少色数输出。
程序源码：
#include <stdio.h>
int n;
int i=0;
int j=0;
int k=0;
int m=0;
int flag=0;
int count=0;
int hxy=0;
int kxy=0;
int hxz=0;
int kxz=0;
int hyz=0;
int kyz=0;
int hxy1=0;
int kxy1=0;
int hxz1=0;
int kxz1=0;
int hyz1=0;
int kyz1=0;
int a[1000]={100};b[1000]={100};c[1000]={100};
int d[1000]={100};e[1000]={100};f[1000]={100};
main()
{ set1: printf("input 3D square's order:\n");
scanf("%d",&n);
if(n<=1 || n>10) goto set1;
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{ for(k=0;k<n;k++)
{ hxy=i-j;
if(hxy<0) hxy=hxy+n;
kxy=i+j+1;
if(kxy>(n-1)) kxy=kxy-n;
hxz=-(i-k);
if(hxz<0) hxz=hxz+n;
kxz=i+k+1;
if(kxz>(n-1)) kxz=kxz-n;
hyz=-(j-k);
if(hyz<0) hyz=hyz+n;
kyz=j+k+1;
if(kyz>(n-1)) kyz=kyz-n;
if( ((i==0&&j==0)||(i==0&&k==0)||(j==0&&k==0)) || (i==0&&(hyz==0||kyz==1)) || (j==0&&(hxz==0||kxz==1)) || (k==0&&(hxy==0||kxy==1)) || (i==j&&(hxz==0||kxz==1)) || (i==k&&(hyz==0||kyz==1)) || (j==k&&(hxz==0||kxz==1)) )
continue;
a[m]=i;
b[m]=j;
c[m]=k;
m=m+1;
}
}
}
a[m]=200;
b[m]=200;
c[m]=200;
for(m=0;m<1000;m++)
{if(a[m]!=200&&b[m]!=200&&c[m]!=200)
count=count+1;
else
break;
}
printf("\n");
printf("the elements irrelating a000:\n");
m=0;
while(a[m]!=200&&b[m]!=200&&c[m]!=200)
{ printf("a%d%d%d...",a[m],b[m],c[m]);
m=m+1;
}
printf("\n");
d[0]=a[0];
e[0]=b[0];
f[0]=c[0];
d[1]=200;
e[1]=200;
f[1]=200;
i=0;
m=0;
for(m=0;m<count;m++)
{ flag=0;
j=0;
while(d[j]!=200&&e[j]!=200&&f[j]!=200)
{ hxy=a[m]-b[m];
if(hxy<0) hxy=hxy+n;
kxy=a[m]+b[m]+1;
if(kxy>(n-1)) kxy=kxy-n;
hxz=-(a[m]-c[m]);
if(hxz<0) hxz=hxz+n;
kxz=a[m]+c[m]+1;
if(kxz>(n-1)) kxz=kxz-n;
hyz=-(b[m]-c[m]);
if(hyz<0) hyz=hyz+n;
kyz=b[m]+c[m]+1;
if(kyz>(n-1)) kyz=kyz-n;
hxy1=d[j]-e[j];
if(hxy1<0) hxy1=hxy1+n;
kxy1=d[j]+e[j]+1;
if(kxy1>(n-1)) kxy1=kxy1-n;
hxz1=-(d[j]-f[j]);
if(hxz1<0) hxz1=hxz1+n;
kxz1=d[j]+f[j]+1;
if(kxz1>(n-1)) kxz1=kxz1-n;
hyz1=-(e[j]-f[j]);
if(hyz1<0) hyz1=hyz1+n;
kyz1=e[j]+f[j]+1;
if(kyz1>(n-1)) kyz1=kyz1-n;
if((a[m]==d[j]&&b[m]==e[j])||(a[m]==d[j]&&c[m]==f[j])||(b[m]==e[j]&&c[m]==f[j]))
{flag=1;
break;}
else if(a[m]==d[j]&&(hyz==hyz1||kyz==kyz1))
{flag=1;
break;}
else if(b[m]==e[j]&&(hxz==hxz1||kxz==kxz1))
{flag=1;
break;}
else if(c[m]==f[j]&&(hxy==hxy1||kxy==kxy1))
{flag=1;
break;}
else if(a[m]==b[m]&&d[j]==e[j]&&(hxz==hxz1||kxz==kxz1))
{flag=1;
break;}
else if(a[m]==c[m]&&d[j]==f[j]&&(hyz==hyz1||kyz==kyz1))
{flag=1;
break;}
else if(b[m]==c[m]&&e[j]==f[j]&&(hxz==hxz1||kxz==kxz1))
{ flag=1;
break;}
else if((a[m]+b[m])==(n-1)&&(d[m]+e[m])==(n-1)&&(hyz==hyz1||kyz==kyz1))
{ flag=1;
break;}
else if((a[m]+c[m])==(n-1)&&(d[m]+f[m])==(n-1)&&(hyz==hyz1||kyz==kyz1))
{ flag=1;
break;}
else if((b[m]+c[m])==(n-1)&&(e[m]+f[m])==(n-1)&&(hxz==hxz1||kxz==kxz1))
{ flag=1;
break;}
else{
j=j+1;
continue;}
}
if(flag==0)
{ d[j]=a[m];
e[j]=b[m];
f[j]=c[m];
d[j+1]=200;
e[j+1]=200;
f[j+1]=200;
}
}
i=0;
count=0;
printf("\n");
printf("a kind of choice without relation:\n");
printf("a000...");
while(d[i]!=200&&e[j]!=200&&f[j]!=200)
{ printf("a%d%d%d...",d[i],e[i],f[i]);
count=count+1;
i=i+1;
}
printf("\n");
printf("\n%d elements relate at random\n",count+2);
printf("\nso the elements with the same color at most are %d\n",count+1);
i=n*n*n;
printf("\n");
printf("at least %d different colors can dye this %d*%d*%d 3D square\n",i/(count+1),n,n,n);
}
程序I/O示例截图：
3.3 二维或三维方块子元素相关性分析计算机实现
程序名：CHECK
程序功能：10阶以内（含10阶）二围或三围染色问题输入的待测小方格或小方块相关性判断，结合原点小方格或小方块相关性判断。
程序I/O（输入输出）：输入方块围数，再输入方块阶数，经过程序处理，顺序输出此阶数的二围或三围立体方块中与待测小方格或小方块不相关的小方格或小方块汇总横排，与待测小方格或小方块不相关并且与a[0][0]或者a[0][0][0]不相关的小方格或小方块输出。
程序源码：
#include<stdio.h>
#include<math.h>
int dim;
int n;
int i=0;
int j=0;
int k=0;
int r=0;
int c=0;
int z=0;
int h=0;
int kk=0;
int hc=0;
int kc=0;
int hxy=0;
int kxy=0;
int hxz=0;
int kxz=0;
int hyz=0;
int kyz=0;
int hxy1=0;
int kxy1=0;
int hxz1=0;
int kxz1=0;
int hyz1=0;
int kyz1=0;
main()
{
set1:
printf("please input the aquare's dimension:\n" );
scanf("%d",&dim);
if(dim<2 || dim>3 )
goto set1;
printf("please input the square's order:\n");
printf("\n");
scanf("%d",&n);
if(n<=1 || n>10 )
goto set1;
if(dim==3)
goto set2;
printf("\n");
printf("input the elments you want to check:a??");
scanf("%d %d",&r,&c);
printf("\n");
hc=r-c;
kc=r+c+1;
if(hc<0)
hc=hc+n;
if(kc>(n-1))
kc=kc-n;
printf("the element you selected in %d*%d square's(a,b,h,k)=s(%d,%d,%d,%d)\n",n,n,r,c,hc,kc);
printf("\nsuitable elements for a%d%d is",r,c);
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{ h=i-j;
kk=i+j+1;
if(h<0)
h=h+n;
if(kk>(n-1))
kk=kk-n;
if(i!=r && j!=c && h!=hc && kk!=kc)
printf("...a%d%d",i,j);
}
}
printf("\nfollow is proper elements for a%d%d in irrelating a00's\n",r,c);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{h=i-j;
kk=i+j+1;
if(h<0)
h=h+n;
if(kk>(n-1))
kk=kk-n;
if(i!=r && j!=c && h!=hc && kk!=kc && i!=0 && j!=0 && h!=0 && kk!=1)
printf("...a%d%d",i,j);
}
goto end;
set2:
printf("input the elments you want to check:a???");
scanf("%d %d %d",&r,&c,&z);
printf("\n");
hxy=r-c;
if(hxy<0) hxy=hxy+n;
kxy=r+c+1;
if(kxy>(n-1)) kxy=kxy-n;
hxz=-(r-z);
if(hxz<0) hxz=hxz+n;
kxz=r+z+1;
if(kxz>(n-1)) kxz=kxz-n;
hyz=-(c-z);
if(hyz<0) hyz=hyz+n;
kyz=c+z+1;
if(kyz>(n-1)) kyz=kyz-n;
printf("the element you selected in %d*%d*%d square's(x,y,z,hxy,kxy,hxz,kxz,hyz,kyz)=s(%d,%d,%d,%d,%d,%d,%d,%d,%d)\n",n,n,n,r,c,z,hxy,kxy,hxz,kxz,hyz,kyz);
printf("\nsuitable elements for a%d%d%d is",r,c,z);
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{ for(k=0;k<n;k++)
{ hxy1=i-j;
if(hxy1<0) hxy1=hxy1+n;
kxy1=i+j+1;
if(kxy1>(n-1)) kxy1=kxy1-n;
hxz1=-(i-k);
if(hxz1<0) hxz1=hxz1+n;
kxz1=i+k+1;
if(kxz1>(n-1)) kxz1=kxz1-n;
hyz1=-(j-k);
if(hyz1<0) hyz1=hyz1+n;
kyz1=j+k+1;
if(kyz1>(n-1)) kyz1=kyz1-n;
if( ((i==r&&j==c)||(i==r&&k==z)||(j==c&&k==z)) || (i==r&&(hyz==hyz1||kyz==kyz1)) || (j==c&&(hxz==hxz1||kxz==kxz1)) || (k==z&&(hxy==hxy1||kxy==kxy1)) || (i==j&&r==c&&(hxz==hxz1||kxz==kxz1)) || (i==k&&r==z&&(hyz==hyz1||kyz==kyz1)) ||
(j==k&&c==z&&(hxz==hxz1||kxz==kxz1))||((r+c)==n-1&&(i+j)==n-1&&(hyz==hyz1||kyz==kyz1))||((r+z)==n-1&&(i+k)==n-1&&(hyz==hyz1||kyz==kyz1))||((c+z)==n-1&&(j+k)==n-1&&(hxz==hxz1||kxz==kxz1)) )
continue;
printf("...a%d%d%d",i,j,k);
}
}
}
printf("\nfollow is proper elements for a%d%d%d in irrelating a000's\n",r,c,z);
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{ for(k=0;k<n;k++)
{ hxy1=i-j;
if(hxy1<0) hxy1=hxy1+n;
kxy1=i+j+1;
if(kxy1>(n-1)) kxy1=kxy1-n;
hxz1=-(i-k);
if(hxz1<0) hxz1=hxz1+n;
kxz1=i+k+1;
if(kxz1>(n-1)) kxz1=kxz1-n;
hyz1=-(j-k);
if(hyz1<0) hyz1=hyz1+n;
kyz1=j+k+1;
if(kyz1>(n-1)) kyz1=kyz1-n;
if( ((i==r&&j==c)||(i==r&&k==z)||(j==c&&k==z)) || (i==r&&(hyz==hyz1||kyz==kyz1)) || (j==c&&(hxz==hxz1||kxz==kxz1)) || (k==z&&(hxy==hxy1||kxy==kxy1)) || (i==j&&r==c&&(hxz==hxz1||kxz==kxz1)) || (i==k&&r==z&&(hyz==hyz1||kyz==kyz1)) ||
(j==k&&c==z&&(hxz==hxz1||kxz==kxz1))||((r+c)==n-1&&(i+j)==n-1&&(hyz==hyz1||kyz==kyz1))||((r+z)==n-1&&(i+k)==n-1&&(hyz==hyz1||kyz==kyz1))||((c+z)==n-1&&(j+k)==n-1&&(hxz==hxz1||kxz==kxz1)) ||
((i==0&&j==0)||(i==0&&k==0)||(j==0&&k==0)) || (i==0&&(hyz1==0||kyz1==1)) || (j==0&&(hxz1==0||kxz1==1)) || (k==0&&(hxy1==0||kxy1==1)) || (i==j&&(hxz1==0||kxz1==1)) || (i==k&&(hyz1==0||kyz1==1)) || (j==k&&(hxz1==0||kxz1==1)) )
continue;
printf("...a%d%d%d",i,j,k);
}
}
}
end:
printf("\n");
}
程序I/O示例截图：
3.4 一种二维最佳拉丁方构造方法计算机实现
程序名：OPTIMAL
程序功能：如果存在，则构造一个100阶以内的平面最佳拉丁方。
程序I/O（输入输出）：输入一个100以内的拉丁方阶数，如若存在这个阶数的最佳拉丁方，则输出一个最佳拉丁方，反之，则输出出错信息，提示不存在此阶数的最佳拉丁方。
程序源码：
#include<stdio.h>
#include<math.h>
static int fix;
int i,j;
int n;
int res(int x,int y,int nn)
{ int z;
if(x==0 && j==0)
{z=nn; fix=z;
if(fix<0) fix=fix+nn+1;
if(fix>nn) fix=fix-nn-1;
}
else if(j==0)
{z=nn-2*x; fix=z;
if(fix<0) fix=fix+nn+1;
if(fix>nn) fix=fix-nn-1;
}
else
z=fix+y;
if(z<0)
z=z+nn+1;
if(z>nn)
z=z-nn-1;
return(z);
}
main()
{
set:
printf("input the optimal latin square's order(within 100):");
scanf("%d",&n);
if(n%2==0 || n%3==0 || n<5 || n>97)
{ printf("sorry! no this optimal latin square!");
goto set;}
printf("\nfollow is the %d*%d optimal latin square:\n",n,n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ if(j==n-1)
printf("%d\n\n",res(i,j,n-1));
else
printf("%d...",res(i,j,n-1));
}
}
程序I/O示例截图：
3.4 广义三维立体拉丁方的构造算法实现
程序名：3DLDF
程序功能：构造一个20阶以内的广义三维立体拉丁方。
程序I/O（输入输出）：输入一个20以内的拉丁方阶数，则输出一个构造好的此阶数的广义三维立体拉丁方的每个元素的具体排法。
程序源码：
#include<stdio.h>
int i,j,k;
int n;
int a[20][20][20];
int res(int x,int y,int z,int nn)
{int m;
m=x+y+z;
if(m<0)
m=m+nn;
if(m>nn-1)
m=m-nn;
if(m<0)
m=m+nn;
if(m>nn-1)
m=m-nn;
return(m);
}
main()
{
set:
printf("\ninput the order of the 3d latin square(1<order<=20):");
scanf("%d",&n);
if(n<2 || n>20)
goto set;
printf("\nfollow are the %d*%d*%d 3d latin square's elements:\n",n,n,n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
{ printf("a[%d][%d][%d] is %d...",i,j,k,res(i,j,k,n));
}
}
程序I/O示例截图：
第四章 结论总结
综上所述，拉丁方由一个有趣的数学游戏衍生为一支强大的自然科学的数学分支，通过社会生活与生产的广泛应用，人们强烈意识到它的科学性与实用性，自然关于它的理论研究已经到达白热化的阶段。通过本文以上的讨论研究，在对正交拉丁方、完备拉丁方以及最佳拉丁方形成了熟练而精密的学术观点之后，利用了计算机在算法设计上的帮助，从广义上以一种染色问题与最佳拉丁方的内在理论联系开展深入的讨论，去研究n阶拉丁方的存在以及该染色问题自身的属性。近而以一种拉丁方试验的推广构造了广义上的拉丁方，即三维立体拉丁方。并导出一种基于副斜线的n阶广义三维拉丁立方的构造方法并发现了新规律，即按此法构造的三维拉丁立方的第i行,j列,k层的元素为i,j,k之和（Jn内计算）。随后通过修改补充二维方块染色问题中的相关规约引理把平面上的染色问题拓展到三维立体空间，并且对一至五阶三维立体方块染色问题进行了细致研究，最后提出了广义立体空间上的最佳拉丁方存在性问题的一些初步的看法和思考。这里最主要的是“相关性”的拓展分析，把二维平面上的染色问题推广到三维立体空间，并叙述了广义立体最佳拉丁方方面的一些观点。
当然，一些方法还是有它的片面性与局限性，并且本人自己的广义立体最佳拉丁方的定义仅仅是一种猜想。
致 谢
在这次毕业设计的工作中，我学到了很多知识，并强化了自己的创新意识，这与指导老师陈小松教授的推荐文献资料、难点答疑指导是分不开的，还有中南大学图书馆的工作人员，在文献查找方面给予了热心的帮助。在此，我要对他们表示衷心的感谢。
参考文献
[1] 孙有伟. 纵横图与拉丁方[J]. 辽宁教育学院学报. 2000年9月，第17卷 第5期：63 ～ 65
[2] 魏万迪. 组合论[M]. 北京：科学出版社，1987
[3] 杨骅飞 王朝瑞. 组合数学及其应用[M]. 北京：北京理工大学出版社，1992
[4] 李盘林 李丽双 李洋 王春立. 离散数学[M]. 北京：高等教育出版社，2002
[5] 高建国. 点阵与有限群的立体定义[J ]. 开封大学学报. 1994年2月，第2、3期：56 ～ 61
[6] Carla P.Gomes Rommel G.Regis David B.Shmoys[J]. Annual ACM-SIAM Symposium on Discrete Algorithms. 2003，Vol. 14th No.1：832 ～ 833
[7] 欧阳录. 最佳拉丁方与高级原幻方[J]. 数学理论与应用. 2001年9月，第21卷第3期：22 ～ 29
[8] 王建中. 方块染色问题的探讨[J]. 湖南教育学院学报. 1991年，第9卷 第2期：39 ～ 41
[9] 陈小松. n (( n, 235)=1)阶高级幻立方的构造方法[J]. 湖南教育学院学报. 1990年5月，卷期页码不详
[10] Chen Xiaosong. [J]. Ways of Constructing Optimal Magic Cube of Order n When ( n, 2357)=1. Journal of Central south university of Technology. (English Edition) 2002.1，Vol.9 No.1：70 ～ 72
[11] 程品. 利用完全拉丁方快速构造素数阶完全幻方[J]. 四川师范学院学报(自然科学版). 1996年9月，第17卷 第3期：106 ～ 108
附 录
外文资料原文：
Ways of constructing optimal magic cube of order n
when(ｎ,2·3·5·7)=1
CHEN Xiao-song(陈小松)
Department of applied mathematics and applied software, central south university, shangsha 410083, China
Abstract: an optimal magic cube of order n is a magic cube whose row sums, column sums and oblique sums of 9 n layers are . The author proved that optimal magic cubes of order n may be constructed as long as n and 2,3,5,7 are relatively prime, and a formula for making optimal magic cubes by using optimal Latin squares and optimal magic squares was given.
Key words: optimal Latin square; optimal magic square; complete residue system
Document code: A
The concept of optimal magic cube and the way of constructing optimal magic cube of order 16n was given in . How to construct optimal magic cubes of order n when n is odd ? In this paper, the author proves the optimal magic cubes of order n may be constructed when (ｎ,2·3·5·7)=1, and a formula for making optimal magic cubes by using optimal Latin squares and optimal magic squares is given.
Write a square matrix A of order n for
and call it square A. We write square A for [a1, a2, …, an] if aj is the jth column of A, (the least positive complete residue system of module n). Totality of two parallel segments is called an oblique line if the two segments are on the two sides of the diagonal and the number of elements in it is n. Diagonal is also an oblique line .The sum of all elements on an oblique line is called oblique sum. Totality of two parallel sections is called an inclined plane if the two sections are on the two sides of diagonal plane and the number of elements on it is . Diagonal plane is also an inclined. Square A is called an optimal magic square if the total elements are 1，2，3,…, and all its row sums, column sums and oblique sums are .
Foundation item: Supported by the Arts and science Foundation of Central South University (No.2000007)
Biography of author: CHEN Xiao-song, associate professor, born in 1956, majoring in algebra and number theory.
Received date: Jane 27, 2001
Square A is called a Latin square if its n elements appear on every row and column; if its n
elements appear also on every oblique line, then A is called an optimal Latin square.
Definition A magic cube A is a cube which consists of 1，2，3,…, and all its row sums , column rows, vertical sums and four large diagonal sums are . An optimal magic cube of order n is the magic cube whose row sums, column sums and oblique sums of 9 n layers are . (including 3n layers which run parallel to the surface and 6n inclined plane).
Let A=[a1,a2,a3,…,ai,ai+1,…,an], ，define =[ai，ai+1， …,a1，…ai-1]； if （n，a）=1, define =[，，…，，…， ]，1+(j-1)a .
Let
Then both E and are Latin squares. We shall construct optimal magic squares and optimal magic cubes by using E and.
Lemma 1 (1) , here A and B are both square of order n, m is an integer;
(2) (or ) is an optimal Latin square if and only if n，k-1）=（n，k）=（n，k+1）=1;
(3) If both and are Latin squares, and （n，k-h）=1, then and are orthogonal (the pair of elements on corresponding position of and are pair wise different).
(4) If A is a optimal Latin square which consists of 0, 1, 2, … , n-1, B is an optima Latin square which consists of elements of , which Z and B are orthogonal, then Ｍ=ｎＡ+Ｂ is an optimal magic square.
Lemma 2 If is an optimal magic square (optimal Latin square) then () is also an optimal magic square (optimal Latin square).
Proof By definition of , (n, a)=1, this shows that 1+(j-1) a passes though a complete residue system of module n when j-1 passes through a complete residue system of module n, And as 1+(j-1) , there exists j0 that makes i=1+(j0-1)a. Hence the fact that is an optimal magic square implies is an optimal magic square, thus =[，，，…]= is also an optimal magic square.
Lemma 3 Let M be Latin square of order n ( M consists of 1, 2, 3, …, ), L is a Latin square of order n ( L consists of 0，2，…，（n-1） ), （n，h）=（n，r）=（n，h-r）=1, and , then all elements of ，，…，are {1，2，3，…， }.
Theorem 1 Optimal magic cubes of order n can be constructed of the following conditions are satisfied:
(1) （n，6）=1;
(2) There exists optimal magic square M of order n, Which makes both and optimal magic square;
(3) There exists an optimal Latin square L whose elements are {0，2，…，（n-1） }, which makes all of the ，, and optimal Latin square.
Proof Let （k=1，2，3，…，n）, we pile up ，，…， from up to down make a cube , by lemma 3, all elements of are 1，2，3，…，. We shall now prove is an optimal magic cube.
Pile up ，，，…， to make a cube , and pile up ，，，…， to make a cube corresponding with . Since every row, column and oblique line of 3n layers (which run parallel to the surface) is row or column on some inclined plane in a cube, so we only prove that every row sum, column sum and oblique sum on 6n inclined plane of is , and every row sum, column sum and oblique sum on 6n inclined plane of is . Therefore every row sum, column sum and oblique sum on 9n layer of is .
Consider the first (seeing Fig.1)
Fig 1. cube
Diagonal plane A1 A2 B3 B4 and kth inclined plane counting from up to down (which runs parallel to A1 A2 B3 B4) is =[，，，，…]=, by lemma 2, each of the m is optimal square. (k=1, 2, 3, …,n)
Diagonal plane B1 B2 A3 A4 and kth inclined Plane counting up to down(which runs parallel to B1 B2 A3 A4) is =[，，，，…]= is optimal magic square. （k=1，2，3,…，n）
As the kth layer of (from up to down) is =[，，…，，…],
jth column jth column
the ith row of it is identical with the ith row of ;the 1st,2nd,3rd,… column of it is respectively identical with the 1st,3rd,5th,… main oblique line counting from the right (which runs parallel to main diagonal) of ;the 1st,4th,7th,… main oblique line (counting from the right) of it is respectively the 1st,3rd,5th,… main oblique line (counting from the right) of ;the 1st,2nd,3rd,… auxiliary oblique line counting from the right (which runs parallel to the auxiliary diagonal) of it is respectively identical with the 1st,3rd,5th,… auxiliary oblique line counting from the right of ,by lemma 2,all are optimal magic square. （k=1，2，3,…，n）.
Consider the other inclined planes, similarly. Therefore, all row sums, column sums and oblique sums on every inclined plane of are .
Fig2. cube
Similarly, all row sums, column sums and the （i，j） -entry of satisfies .
Diagonal plane A1 B2 B3 A4 and kth inclined plane counting from up to down (which runs parallel to diagonal plane) is
oblique sums of every inclined plane of (seeing Fig.2) are .
Theorem 2 if (ｎ,2·3·5·7)=1 ,then we can construct the optimal magic cubes of order n. The kth layer (from up to down) of is . （k=1，2，3,…，n） .
Proof Since (ｎ,2·3·5·7)=1 , by lemma 1, are optimal Latin square, and are orthogonal, and are orthogonal, and are orthogonal. Therefore are all optimal Latin square, are optimal magic squares, the optimal magic cube of order n is constructed.
References
[1] Li li. Fast way of constructing 1st class optimal magic cube of order 16n[J]. Mathematics Progress (in Chinese), 1988. 17(4): 385-390.
[2] Andrews W S. Magic squares and cubes[M]. Dover Publications INC, 1960. 64-206.
[3] Hua Luo-geng. Introduction to theory of numbers (in Chinese)[M].Beijing: Science Press, 1979.
[4] Min Si-he, Yian Shi-jian. Primary theory of numbers (in Chinese)[M].Beijing: People Education Press, 1983.
[5] Chen Xiao-song. Way of constructing advanced Magic Cube of order n when (n, 2.3.5)=1 (in Chinese)[J]. Journal of Hunan Education Institute, 1990, 5: 104-106.
[6] Chen Xiao-song. The researching of ways of constructing prime number and it’s primitive root (in Chinese)[J]. Mathematics Theory and Applications, 2000, 20: 66-68.
外文资料主体正文译文：
n阶最佳幻方的构造方法
(ｎ,2·3·5·7)=1
陈小松
应用数学与应用软件系，中南大学，长沙410083，中国
摘要：一个n阶的最佳幻立方是一个9n层行和、列和、的斜和都为。作者证明了当n与2，3，5，7都互素时，n阶的幻立方是可以被构造出来的，并且推导了一个利用最佳拉丁方和最佳幻方来构造最佳幻立方的公式。
关键词：最佳拉丁方；最佳幻方；完全剩余系
最佳幻立方的概念以及16n阶的最佳幻立方的构造方法已经在1988年被给出。怎样构造一个n为奇数的最佳幻立方呢？在这篇文章里，作者证明了当n与2，3，5，7都互素的奇数阶的最佳幻立方的构造方法以及采用最佳拉丁方和最佳幻方来构造的构造公式。
写一个n阶的拉丁矩阵A如下：
称之为方块A。我们写A=[a1, a2, …, an] 如果aj在A的j列, (模n的最小正完全剩余系)。两个平行段的总体被称为一条斜线，如果两个段在对角线的两边并且这条斜线上有n个元素。当然，对角线也是一条斜线，一条斜线上所有元素的和称为斜和。两个平行段的总和成为斜面，如果两个段位于一条对角线面的两边并且其上的元素个数是。对角面也是一个斜面。方块A就是一个最佳幻方，如果所有元素是1，2，3,…, 并且它的行和、列和、斜和都是。
方块A被称之为拉丁方，如果它的n个元素都出现在每一行、每一列；如果它的n个元素也都出现在每一条斜线，那么就称之为最佳拉丁方。
定义：幻立方A 由1，2，3,…, 组成，它的所有行和、列和、垂直纵向和、4个大对角线和都为，一个n阶最佳幻立方，它9n层的行和，列和，斜和也都是（包括平行于相应表面的3n层和6n斜面）。
设A=[a1,a2,a3,…,ai,ai+1,…,an], ，定义 =[ai，ai+1， …,a1，…ai-1]；如果（n，a）=1，定义 =[，，…，，…， ]，1+(j-1)a 。
设：
那么Ｅ和都是拉丁方，我们将使用Ｅ和来构造一个最佳幻方和一个最佳幻立方。
引理1：（1），，这里的A和B都是n阶方块，m是一个整数；
（2）（或者）是一个最佳拉丁方，当且仅当（n，k-1）=（n，k）=（n，k+1）=1；
（3）如果和是拉丁方，并且（n，k-h）=1，那么和是正交的（对应位置的和的元素对之间是两两不相同的）。
（4）如果A是一个由0，1，2，…，n-1组成的最佳拉丁方，B是一个由里的元素组成的最佳拉丁方，当Z与B正交的时候，Ｍ=ｎＡ+Ｂ是一个最佳幻方。
引理2：如果是一个最佳幻方（最佳拉丁方），那么也是一个最佳幻方（最佳拉丁方）。
证明：由的定义可知，（n，a）=1，这就说明了1+（j-1）a通过了模n的一个完备剩余系当（j-1）通过了模n的一个完备剩余系。并且当1+(j-1)a ，存在j0，使得i=1+(j0-1)a，因此是一个最佳幻方表明了是一个最佳幻方，所以 =[，，，…]= 也是一个最佳幻方。
引理3：设M是一个n阶的拉丁方（M由1，2，…，构成），L是一个n阶的拉丁方（L由0，2，…，（n-1）构成），（n，h）=（n，r）=（n，h-r）=1，而且 ,那么，所有，，…，的元素是{1，2，3，…， }。
定理1：n阶最佳幻立方可以被构造出来，如果满足以下条件：
（1）（n，6）=1；
（2）存在n阶最佳幻方，使得与都是最佳幻方；
（3）存在最佳拉丁方L，其元素是{0，2，…，（n-1） }，使得所有的，和都是最佳拉丁方。
证明：设（k=1，2，3，…，n），我们从上至下堆叠，，…，来构造一个立方体，由引理3，所有的元素是1，2，3，…，。我们现在来证明是一个最佳幻立方。
堆叠，，，…，来构造一个立方体，再堆叠，，，…，来构造一个对应于的，因为3n层的每一行、每一列、每一斜线（平行于表面）是立方体中某一个斜面的行或者列。所以我们只证明的6n斜面上的每一行和、列和、斜和都是，并且的6n斜面上的每一行和、列和、斜和都是。因此的9n层面上的每一行和、列和、斜和都是。
考虑第一个（如图1）
图1 立方体
对角面A1 A2 B3 B4和从上至下数的第k斜面（平行于A1 A2 B3 B4）是 =[，，，，…]=，由引理2，每一个m都是一个最佳幻方（k=1，2，3,…，n）。
对角面B1 B2 A3 A4和从上至下数的第k斜面（平行于B1 B2 A3 A4）是 =[，，，，…]=是最佳幻方（k=1，2，3,…，n）。
当的第k层（从上至下）是 =[，，…，，…]，
第j列 第j列
图2
它的第i行的元素是与的第i行是恒等的；它的第1列，第2列，第3列，…，分别与的从右开始数的主斜线（平行于主对角线）的第1条，第3条，第5条，…，恒等；它的主斜线（从右开始数的）的第1条，第4条，第7条，…，分别与的从右边开始数的主斜线的第1条，第3条，第5条，…，恒等；它的从右开始数的副斜线（平行于副对角线）的第1条，第2条，第3条，…，分别与的从右开始数的副斜线的第1条，第3条，第5条，…，恒等，由引理2，所有的都是最佳幻方（k=1，2，3,…，n）。设置如上面的图2。
再考虑其他的斜面，同理是一样的。因此，的每一个斜面上的行和、列和、斜和都是。
图3 立方体
同理，所有的行和，列和和（i，j）-通道满足。
对角面A1 B2 B3 A4 和从上至下（对行于对角面）的第k斜面的斜和是每一个斜面的斜和，为。如图3。
定理2：如果(ｎ,2·3·5·7)=1，那么我们可以构造一个n阶的幻立方，它的第k层（从上至下）是 （k=1，2，3,…，n）。
证明：因为(ｎ,2·3·5·7)=1，由引理1，是最佳拉丁方，和是正交的，和是正交的，和是正交的，因此都是最佳拉丁方，都是最佳幻方，所以n阶最佳幻立方能被构造出来。
