将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时等了一段时间就是不出结果,仔细检查觉得应该不是死循环导致这个问题，暂时也只能这样了，郁闷

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define N 4
struct B
{
    int **Pa;    //结构体B中Pa指针用于指向找到的拉丁方阵
    int **Pb;    //结构体B中Pb指针用于指向该拉丁方阵对应的占位矩阵
    struct B *next;
};
typedef struct B B1;
void L(int **p1, int *p2, int n);  //求所有全排列的递归函数
void output(B1 *psnew, int fac, int **factor);  //输出基拉丁方阵对应的所有拉丁方阵的函数
int fill(int Lad[][N], int position[][N], int hold[][N], int i, bool TF);  //将i填充入方阵的函数,填充成功返回1，否则返回0
int find(int i, int position[][N], int hold[][N], int k);  //寻找方阵的k+1行可以放置i的位置,找到返回列标，否则返回0
int place(int i, int j, int position[][N], int hold[][N], int k);  //函数，判断方阵的k+1行,j列是否可以放置i，可以返回1，否则返回0
int B(int n);  //求阶乘的递归函数

void main()
{
    int Lad[N][N]={0}, position[N][N]={0}, hold[N][N]={0};  //回溯试探针对Lad方阵进行，试探成功后Lad中保存有找到的拉丁方阵.position为占位矩阵,hold为标志方阵中各位置是否已被填充的矩阵
    int que[N];
    int **factor;  //指向存放所有全排列的方阵
    int fac;
    bool TF;  //为true代表上一个数填充成功，应该开始填充下一个，为false表示当前数填充失败,应该返回上一个数进行回溯
    int i, j, k, flag;  //i在第一个while循环中表示填充的数字,flag表示两占位矩阵列集合是否相等
    B1 *head, *tail, *psnew, *pm;

    head=(B1 *) malloc(sizeof(B1));
    tail=head;
    head->next=NULL;

    for (i=0; i<N; i++)
        que[i]=i+1;

    factor=(int **) malloc((fac=B(N))*sizeof(int *)); 
    for (i=0; i<fac; i++)
        factor[i]=(int *) malloc(N*sizeof(int));  //建立用来保存所有全排列的矩阵

    L(factor, que, N);  //将所有全排列填入上述矩阵

    TF=true;
    i=1;      //TF,i初始化