本文主要是介绍排列宝石问题 回溯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
现有n种不同形状的宝石，每种n 颗，共n*n颗。同一种形状的n颗宝石分别具有n种不同的颜色c1,c2,…,cn中的一种 颜色。欲将这n*n颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜 色。
试设计一个算法，计算出对于给定的n，有多少种不同的宝石排列方案。
算法设计：
对于给定的n，计算出不同的宝石排列方案数。
输入文件示例 输出文件示例
1 1
#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;
}这篇关于排列宝石问题 回溯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
