回溯拉丁矩阵

---

---

现有n种不同形状的宝石，每种宝石有足够多颗。欲将这些宝石排列成m行n列的一个矩阵，m<=n，使矩阵中每一行和每一列的宝石都没有相同的形状。试设计一个算法，计算出对于给定的m和n，有多少种不同的宝石排列方案。

分析：

宝石n种，又是n列，所以可以认为保证每一行的宝石都不同（关键），判断的时候只判断列是否相同就行

#include<stdio.h>
#define n 3
#define m 3
int a[m][n];
int count=0;

bool OK(int x,int y){//因为之前已经保证每一行都是不同的，所以OK方法只判断列相不相同就行
    for(int i=0;i<x;i++){
        if(a[x][y]==a[i][y])
            return false;
    } 
    return true;
}

void traceback(int x,int y){
    int temp;
    for(int i=y;i<n;i++){
        temp=a[x][y];
        a[x][y]=a[x][i];
        a[x][i]=temp;
        if(OK(x,y)){
            if(x==m-1){//到达最后一行 
                if(y==n-1){//到达最后一列 
                    count++;
                    return; 
                }else{
                    traceback(x,y+1);   
                }
            }else{//还没有到达最后一行
                if(y==n-1){//到达某一行的最后一列 
                    traceback(x+1,0);
                }else{
                    traceback(x,y+1);
                }
            }
        }
        temp=a[x][y];
        a[x][y]=a[x][i];
        a[x][i]=temp;
    } 
}

int main(){
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            a[i][j]=j+1;//每一行都是1 2 3 ... n ,保证每行内宝石种类都不会重复 
        }
    }
    traceback(0,0); 
    printf("%d",count);
    return 0;
} 

运行截图