中原工学院信息商务学院
实验报告
实验项目名称回溯划算法的应用
课程名称算法设计与分析
学院(系、部)中原工学院信息商务学院学科专业计算机科学与技术系班级学号计科132班17号姓名程一涵
任课教师邬迎
日期2014年12月9日
实验五回溯算法的应用
一、实验目的
1．掌握回溯算法的基本概念
2．熟练掌握回溯算法解决问题的基本步骤。

3．学会利用回溯算法解决实际问题。

二．问题描述
题目一：N皇后问题
要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。

规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。

求所有的解要求：键盘输入皇后的个数n (n ≤ 13)
输出有多少种放置方法
输入输出实例：
三．算法设计
首先，确定第一行皇后的位置，再确定第二行的位置，并且要注意不能同行同列同对角线，若是发现有错则返回上一层，继续判断。

满足约束条件时，则开始搜索下一个皇后的位置，直到找出问题的解。

四.程序调试及运行结果分析
五.实验总结
通过这次试验，使得我们面对问题时的解题思路变得更加灵活和多变，并且使我们的编写能力稍稍的提高一些。

初步了解了回溯算法，回溯算法实际是一个类似枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。

他特别适用于求解那些涉及到寻求一组解的问题或者求满足某些约束条件的最优解的问题。

此算法具有结构清晰，容易理解且可读性强等优点，并且通过稍加变通也可以适用于其他类似问题
附录：程序清单（程序过长，可附主要部分）
#include <iostream>
#include <math.h>
using namespace std;
int a[20],n;
backdate(int n);
int check(int k);
void output(int n);
int main()
{
int n;
cout<<"请输入皇后的个数：";
cin>>n;
cout<<"位置排列是："<<endl;
backdate(n);
return 0;
}
backdate(int n)
{
int k;
int num=0;
a[1]=0;
k=1;
while(k>0)
{
a[k]=a[k]+1;
while((a[k]<=n) && (check(k)==0))
a[k]=a[k]+1;
if(a[k]<=n)
if(k==n)
{
num++;
output(n);
}
else
{
k=k+1;
a[k]=0;
}
else
k=k-1;
}
cout<<"一共有"<<num<<"种情况。

"<<endl;
}
int check(int k)
{
int i;
for(i=1;i<=k-1;i++)
if(abs(a[i]-a[k])==abs(i-k) || a[i]==a[k])
return(0);
return(1);
}
void output(int n)
{
int i;
cout<<"[";
for(i=1;i<=n;i++)
cout<<a[i]<<",";
cout<<"]"<<endl;
}。