damon.txt

(排列宝石问题)算法思想 形如着色问题依次填充,如不能填写任何宝石则回溯.

(排列宝石问题)设有n种不同的颜色，同一种形状的n颗宝石分别具有这种不同的颜色。现有n种不同形状的宝石共有 颗，欲将这 颗宝石排列成n行n列的一个方阵，使方阵中每一行每一列的宝石都有n种不同颜色和n种不同形状。试设计一个算法计算出对于给定的n有多少种不同的宝石排列方案。
算法思想
形如着色问题依次填充,如不能填写任何宝石则回溯.
程序流程图:

源程序:
#include<iostream>
using namespace std;
#define N 100

struct node
{
   int shape;
   int color;
};
node a[N][N];
int n;
long num;
bool b[N][N];
void compute(int k)
{
   int i,j,i1,j1,i2,j2;
   if(k>=n*n)
   {
   /*列举出所有的情况,输出的(i,j),其中:i表示形状的类型,j表示颜色的类型
   printf("\n");
   for(i=0;i<n;i++,printf("\n"))
   for(j=0;j<n;j++)
         printf("(%d,%d) ",a[i][j].shape,a[i][j].color);
     printf("-----------------------------");*/
     num++;
     return ;
   }
   bool f1,f2;
   i=k/n;j=k%n;
   for(i1=0;i1<n;i1++)
     for(j1=0;j1<n;j1++)
     {
       if(!b[i1][j1])
       {
         f1=true;f2=true;
         for(i2=0;i2<i;i2++)
           if(a[i2][j].color==j1||a[i2][j].shape==i1){f1=false;break;}
         for(j2=0;j2<j;j2++)
           if(a[i][j2].shape==i1||a[i][j2].color==j1){f2=false;break;}
         if(f1&&f2)
         {
           b[i1][j1]=1;
           a[i][j].color=j1;
           a[i][j].shape=i1;
           compute(k+1);
           b[i1][j1]=0;
           a[i][j].color=-1;
           a[i][j].shape=-1;
         }
       }
     }
}
int main()
{
   int i,j,t=1;
   while(t)
   {
     printf("input n:");
     scanf("%d",&n);
     for(i=0;i<n;i++)
       for(j=0;j<n;j++)
       {
         b[i][j]=0;
         a[i][j].color=-1;
         a[i][j].shape=-1;
       }
       num=0;
       compute(0);
       printf("the number of method:%d\n:",num);
   }
   return 0;
}
运行结果:
input n:3
the number of method:72
:input n: