实训一
N皇后排列方法问题的回溯算法与实现
一、设计目的
1）掌握N皇后排列方法问题的回溯算法；
2）进一步掌握回溯算法的基本思想和算法设计方法；
二、设计内容
1．任务描述
1）算法简介
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再
走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
2）N皇后排列方法问题简介
在N*N格的棋盘上放置彼此不受攻击的N个皇后.按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子.N后问题等价于在N*N格的棋盘上放置N个皇后,任何2个皇后不放在同一行或同一列或同一斜线上.
3）设计任务简介
对于回溯类似的问题。
首先，要能理解该问题运用到的回溯的概念；其次，根据回溯相关的基本思想，找出相应的数学公式；最后，进行程序的设计和编写。
利用回溯的基本思想和计算步骤，有助于我们解决生活中遇到的各种数学问题。
4）问题分析
由于这是一个平面上棋子布局处理问题，因此，我们可以将问题看成是一个二维数组问题。
给八个皇后分别编号为1,2，…,8，其中第i个皇后放置在第i行上，并这就解决了不同皇后分别摆放在
不同列的问题，这样又可以把问题简化为一个一维数组的问题，假设用一维数组x[i]来存放皇后所放
置的列，对于第i个皇后，假设它存放在x[i]列上，则对应的x数组应满足如下的条件：[2]
1)因为一共只有8列，故x[i]的取值只能取1到8之间的数。
2)因为不同的皇后只能粗放在不同的列上，则对于任意的i和j，应满足如果i！=j，则x[i]!=x[j]
3)因为不同的皇后不能存放在同一对角线上，故连接两个皇后的直线的斜率应不能等于正负1，而
连接任意第i个皇后和第j个皇后(i与j不同)的直线的斜率的计算公式为：(x[i]-x[j])/(i-j),
即(x[i]-x[j])/(i-j)！=±1，即:|x[i]-x[j]|！=| i-j |
N皇后排列方法问题的表示方案
2．递推过程的抽象描述
本设计采用前向或后向递推公式。
用自然语言、伪程序设计语言或流程图等形式针对N皇后排列方法问题的求解（抽象地）描述递推过程……
3．解题思路
4．主要数据类型与变量
Backtrack (int t)//递归调用,回溯法
int nQueen(int n)//皇后排列的方法
int n;//皇后个数
5．算法或程序模块
class Queen
{
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(int t);
int n,
*x;
long sum;
};
bool Queen::Place(int k)
{
for (int j=1; j<k ;j++)
if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;
return true;
}
void Queen::Backtrack (int t)
{
if (t>n)
sum++;
else
for (int i=1;i<=n;i++)
{
x[t]=i;
if (Place(t)) Backtrack(t+1);
}
}
int nQueen(int n)
{
Queen X;
X.n=n;
X.sum=0;
int*p=new int[n+1];
for(int i=0;i<=n;i++)
p[i]=0;
X.x=p;
X.Backtrack(1);
delete[]p;
return X.sum;
}
三、测试
1．方案
描述测试方案、测试模块、测试数据实例（文字数据、图或表等形式）……
2．结果
四、总结与讨论
通过构造函数，利用回溯思想编写代码，利用回溯的基本思想和计算步骤，有助于我们解决生活中遇到的各种数学问题。
附：程序模块的源代码
#include<stdio.h>
#include<math.h>
class Queen
{
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(int t);
int n,
*x;
long sum;
};
bool Queen::Place(int k)
{
for (int j=1; j<k ;j++)
if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;
return true;
}
void Queen::Backtrack (int t)
{
if (t>n)
sum++;
else
for (int i=1;i<=n;i++)
{
x[t]=i;
if (Place(t)) Backtrack(t+1);
}
}
int nQueen(int n)
{
Queen X;
X.n=n;
X.sum=0;
int*p=new int[n+1];
for(int i=0;i<=n;i++)
p[i]=0;
X.x=p;
X.Backtrack(1);
delete[]p;
return X.sum;
}
void main()
{
int n;
printf("请输入皇后个数:\n"); scanf("%d",&n);
n=nQueen(n);
printf("有%d种方法\n",n);
}。