问题描述：

(王晓东 算法设计与分析 第五章习题)

现有n种不同形状的宝石，每种n 颗，共n*n颗。同一种形状的n颗宝石分别具有n种不同的颜色c1,c2,…,cn中的一种颜色。欲将这n*n颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个算法，计算出对于给定的n，有多少种不同的宝石排列方案。

问题地址：

http://acm.bjtu.edu.cn/OnlineJudge/problem?problem_id=1083

/**
采用回溯法，因为找不到好的剪枝方法，所以速度奇慢orz
所以在本机计算完毕后打表吧
以下是在本机计算的结果数据

int a[9] = {0,1,0,72,6912,6220800,0,0,0}

*/

#include <stdio.h>
#define N 9

int shape[N][N];//棋盘记录石子的形状
int color[N][N];//记录棋盘石子的颜色
bool stone[N][N];//stone[i][j]表示i形状的j颜色的石子是否已经用过

int cnt = 0;
int n = 0;

//row行，col列
bool isOK(int row,int col)
{
if(stone[shape[row][col]][color[row][col]])
{
   //如果石子没有被用过

   //检查这一行
   for(int i=1;i<col;i++)
   {
    if(shape[row][i]==shape[row][col] || color[row][i]==color[row][col])
    {
     return false;
    }
   }

   //检查这一列
   for(int j=1;j<row;j++)
   {
    if(shape[j][col]==shape[row][col] || color[j][col]==color[row][col])
    {
     return false;
    }
   }

   return true;
}
else
{
   //如果石子已经被用过
   return false;
}
}

void Swap(int &x,int &y)
{
int tmp = x;
x = y;
y = tmp;

}

//从上到下，从左到右回溯，row代表行，col代表列
void BackTrace(int row,int col)
{

if(row>n)
{
   //排完了最后一行
   cnt++;
   return ;
}
else if(col>n)
{
   //一行排序完毕，排序下一行
   BackTrace(row+1,1);
}
else
{
   for(int i=col;i<=n;i++)
   {
    //排列形状
    Swap(shape[row][col],shape[row][i]);
    for(int j=col;j<=n;j++)
    {
     //排列颜色
     Swap(color[row][col],color[row][j]);
     if(isOK(row,col))
     {
      stone[shape[row][col]][color[row][col]] = false;
      BackTrace(row,col+1);
      stone[shape[row][col]][color[row][col]] = true;
     }
     Swap(color[row][col],color[row][j]);
    }
    Swap(shape[row][col],shape[row][i]);
   }
}

}

int main()
{
while(scanf("%d",&n)!=EOF)
{
   //初始化工作
   cnt = 0;
   for(int i=1;i<=n;i++)
   {
    for(int j=1;j<=n;j++)
    {
     color[i][j] = j;
     shape[i][j] = j;
     stone[i][j] = true;
    }
   }
   BackTrace(1,1);
   printf("%d\n",cnt);
}

return 0;
}