2024年6月14日发(作者：)

算法设计与分析

课程设计报告

设计题目：排列宝石问题

一、问题描述：

排列宝石问题。设有n种不同的颜色，同一种形状的n颗宝石分别具有这种不同的颜

色。现有n种不同形状的宝石共n*n颗，欲将这n可宝石排列成n行n列的一个方阵，使

方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个算法计算出

对于给定的n有多少种不同的宝石排列方案。

二、问题分析:

实验要求方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色，所以问题

可以看成n*n的矩阵中每一个元素与其同一行和同一列的元素都不相同。此时我们想到n

后问题要求n*n格的棋盘上放置n个彼此不收攻击的皇后。所以我们的宝石排列问题就可

以看做是n后问题的扩展，即有n种不同的皇后且每种皇后有n个不同大小。下面我们就

可以通过n后问题的算法来解决我们的问题。

三、程序代码：

方法一代码：递归法

#include"iostream.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;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;i

if(a[s[i][y]].color==a[s[x][y]].color||a[s[i][y]].shape==a[s[x][y]].shape)return 0;