宝石排列.doc

算法设计与分析 课程设计报告 设计题目：排列宝石问题 一、问题描述： 排列宝石问题。设有n种不同的颜色，同一种形状的n颗宝石分别具有这种不同的颜色。现有n种不同形状的宝石共n*n颗，欲将这n可宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个算法计算出对于给定的n有多少种不同的宝石排列方案。 二、问题分析程序：#includeiostream.h #define N 4 struct diamond { int color; //颜色编号 int shape; //形状编号 int use; //是否已经排列，未排列为1 }; int place(struct diamond a[],int s[][N+1],int x,int y)//查看宝石是否可放 { for(int j=1;jy;j++) //判断行中是否有颜色形状重复 if(a[s[x][j]].color==a[s[x][y]].color||a[s[x][j]].shape==a[s[x][y]].shape)return 0; for(int i=1;ix;i++) //判断列中是否有颜色形状重复 if(a[s[i][y]].color==a[s[x][y]].color||a[s[i][y]].shape==a[s[x][y]].shape)return 0; return 1; } void backtrack(struct diamond a[],int s[][N+1],int t,int sum)//用回溯法递归搜索 { int x,y; x=(t-1)/N+1; //矩阵的行号 y=(t-1)%N+1; //矩阵的列号 if(xN) { sum++; for(int i=1;i=N;i++) { for(int j=1;j=N;j++)cout(a[s[i][j]].color,a[s[i][j]].shape) ; coutendl; } coutendl; } else { for(int i=1;i=N*N;i++) if(a[i].use) //宝石i未排列 { s[x][y]=i; if(place(a,s,x,y)) { a[i].use=0; backtrack(a,s,t+1,sum); a[i].use=1; } } } } void main() { struct diamond a[N*N+1]; int sum=0,s[N+1][N+1]; for(int i=1;i=N*N;i++) //初始化n*n个宝石 { a[i].color=(i-1)/N+1; a[i].shape=(i-1)%N+1; a[i].use=1; } cout(x,y)表示第x种颜色第y种形状的宝石endl; coutN宝石可排列如下:endl; backtrack(a,s,1,sum); cout总共有sum方案endl; } #includeiostream.h #define N 4 struct diamond { int color; //颜色编号 int shape; //形状编号 int use; //是否已经排列，未排列为1 }; int place(struct diamond a[],int s[][N+1],int x,int y)//查看宝石是否可放 { for(int j=1;jy;j++) //判断行中是否有颜色形状重复 if(a[s[x][j]].color==a[s[x][y]].color||a[s[x][j]].shape==a[s[x][y]].shape)return 0; for(int i=1;ix;i++) //判断列中是否有颜色形状重复 if(a[s[i][y]].color==a[s[x][y]].color||a[s[i][y]].shape==a[s[x][y]].shape)return 0; return 1; } void backtrack(struct diamond a[],int s[][N+1],int sum)//用回溯法非递归搜索 { int x,y; x=1,y=1; s[x][y]=0; whi