深圳大学实验报告
课程名称：算法分析与复杂性理论
实验项目名称：八皇后问题
学院：计算机与软件学院
专业：软件工程
指导教师：杨烜
报告人：学号：班级：15级软工学术型
实验时间：2015-12-08
实验报告提交时间：2015-12-09
教务部制
一．实验目的
1.掌握选回溯法设计思想。

2.掌握八皇后问题的回溯法解法。

二．实验步骤与结果
实验总体思路：
根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。

测试数据模块主要调用判断模块进行判断，完成测试。

用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。

相应结果和过程如下所示（代码和结果如下图所示）。

回溯法的实现及实验结果：
1、判断函数
代码1：
procedure BTrack_Queen(n)
皇后问题 2.测试数据0.退出**"<<endl;
cout<<"******************************************"<<endl;
cin>>n;
switch(n){
case 0: cout<<"退出程序成功..."<<endl;
return 0; //一个程序两个出口
case 1: cout<<"八皇后问题的解为："<<endl;
BackTrack_Queen(0);
cout<<"共有"<<sum<<"个解"<<endl;
break;
case 2: cout<<"运行测试数据："<<endl;
while(1) {
cout<<"请输入要测试的数据："<<endl;
for(int j=0;j<max;j++)
cin>>queen[j];
if(Judge(max)==1) cout<<"该数据是八皇后问题的解"<<endl;
else cout<<"该数据不是八皇后问题的解"<<endl;
}
break;
default: cout<<"输入非法，请重新输入！"<<endl;
}
}
return 0;
}
注：MFC实现代码下载：若链接无效可加我百度云好友：123望月台456。