C语言编程构造拉丁方阵和正交拉丁方阵组

代码源于网络

将1,2,--,n这n个数填入n*n矩阵，使得每行每列的数两两不同(都是1,2,--,n的全排列)，这样的n阶方阵是拉丁方阵。如果一对n阶拉丁方阵对应的元素构成的有序对两两不同,则称这一对n阶拉丁方阵是正交的。现要编程用计算机构造出所有的n阶拉丁方阵和n阶正交拉丁方阵组，该怎么做？

一个显然的事实是,n阶拉丁方阵中各行i元素（i=1,2---n）是两两不同列的。所以按a1,---,an(为1,2--n的置换)顺序向各行填入ai(i=1,2,--,n)，使其两两不同列,就能得到一个正交拉丁方阵。我们可以按1,2,---,n的顺序填入各数得到一系列正交拉丁方阵,然后从中剔除可以由其中的其他拉丁方阵置换得到的拉丁方阵，经剔除后剩下拉丁方阵姑且叫基拉丁方阵。各基拉丁方阵通过置换{1,2,--,n}->{a1,a2,--,an}就能得到所有n阶拉丁方阵。且每个基拉丁方阵通过置换得到的所有拉丁方阵（包括基拉丁方阵在内）两两不成交,若两个不同的基拉丁方阵相互正交,则对于由这两个基拉丁方阵通过置换{1,2,--,n}->{a1,a2,--,an}衍生出的所有拉丁方阵（包括这两个基拉丁方阵）来说，衍生自其中一个拉丁方正的拉丁方阵和衍生自另一基拉丁方阵的拉丁方阵相互正交，反之亦然。因此只要找出所有的正交基拉丁方阵对就可找出所有的正交拉丁方阵组。

具体实现时，我们需要一个存放找到的拉丁方阵的二维数组Lad(回溯试探操作就对它进行),二维数组position-其第i行第j列的元素表示试探过程中数字j在Lad第i行的位置的列标，我称它为占位矩阵，以及二维数组hold，其第i行第j列的元素为1时表示Lad的第i行第j列已被填充,为0时表示Lad的第i行第j列未被填充。我们用回溯法反复试探，将n个数字全部填入Lad中，使其为拉丁方阵。通过回溯法找到的拉丁方阵及对应的占位矩阵被存放在B1类型的链表中。随后，根据以上分析，我们从找到的的拉丁方阵中剔除可由其中其他拉丁方阵置换得到的拉丁方阵,从而得到存放在B1类型链表中的所有基拉丁方阵,剔除过程中用到了一条性质:若两拉丁方阵对应的占位矩阵的所有列构成的集合相等,则两拉丁方阵中的每一个可以通过置换得到另一个。

得到基拉丁方阵后，就可以轻而易举地通过置换输出所有的n阶拉丁方阵，然后通过判断任意两个基拉丁方阵是否正交来求得并输出（对两个基拉丁方阵作置换）正交拉丁方阵组，问题就解决了。

以下是构造拉丁方阵和正交拉丁方阵组的C语言代码。程序还是有一些问题的,n超过4后等了一段时间后仍然没有结果输出。经过调试发现n=5时回溯操作能顺利完成,但当我越过剔除操作运行至输出操作时发现等了一段时间后程序还是无法运行至输出操作。按步进方式执行剔除操作时没有遇到程序崩溃出错等问题，但无论我按住按键多长时间剔除操作都无法执行完，所以推测是n=5时找出的拉丁方阵过多,程序运行的时间开销太大，短时间内无法执行完毕，没办法。笔者智商捉急，想不到好的方法能解决这个问题，希望有大神能提出改进方案，优化程序，缩短运行时间,目前这个程序至多对n=4能输出正确结果,n>=5时等了一段时间就是不出结果,仔细检查觉得应该不是死循环导致这个问题，暂时也只能这样了，郁闷。