算法实验 递归回溯解八皇后问题.doc

深 圳 大 学 实 验 报 告 课程名称： 算法分析与复杂性理论 实验项目名称： 八皇后问题 学院： 计算机与软件学院 专业： 软件工程 指导教师： 杨烜 报告人： 学号： 班级： 15级软工学术型 实验时间： 2015-12-08 实验报告提交时间： 2015-12-09 教务部制一实验目的1. 掌握选回溯法设计思想。2. 掌握八皇后问题的回溯法解法。二实验步骤与结果实验总体思路：根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。回溯法的实现及实验结果：1、 判断函数代码1：procedure BTrack_Queen(n)/如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。globalX(1:k);integeri,ki1whilei0 doX(k)X(k)+1 /移到下一个位置while X(k)=n and not Judge(k) do /判断能否放置皇后X(k)X(k)+1repeatif X(k)=n /找到一个位置then if k=n /是一个完整的解吗then print(X) /是，打印数组else kk+1;X(k)0 /转向下一行endifelse kk-1 /否则，回溯上一行endifrepeatend BTrack_Queen实验结果：(图1 回溯法解八皇后问题)(图2 回溯法解八皇后问题)(图3 测试数据结果)注：根据实验数组中保存的列坐标，对应行坐标顺序输入即可。实验中多加入了一组不满足八皇后问题的解。MFC可视化下八皇后的实现与结果：代码3：/判断是否符合八皇后问题的解int CBfhouDlg:check(int row, int col) /看同行是否合法; for(int i=0;i=col-1;i+) if(arowi=1)return 0; for(i=col+1;i8;i+) if(arowi=1)return 0; /看同列是否合法; for(i=0;i=row-1;i+) if(aicol=1)return 0; for(i=row+1;i=0&j= N-1) if(aij=1)return 0; -i;+j; i=row+1; j=col-1; while(i=0) if(aij=1)return 0; +i;-j; i=row-1;j=col-1; while(i=0&j=0) if(aij=1)return 0; -i;-j; i=row+1;j=col+1; while(i=N-1)&j=N-1) if(aij=1)return 0; +i;+j; return 1; 实验结果：（图4 八皇后的第1种解）(图5 八皇后的第92种解)注：由于时间有限，这个月考试较多，程序还要很多地方需要完善。三实验分析与结论根据八皇后问题的规则皇后不能放置在同行、同列及同一对角线上，进而将问题转化为将第i个皇后放在第i行第xi列上(1i,xin)，皇后间彼此不能同列及不同对角线表示为xi != xj，|ixi| != |jxj|。八皇后问题的解法主要有枚举法、非递归回溯法、递归回溯法这三种，枚举法是将所以的可能组合都进行判断，时间复杂度为O(nn),适用于个数n比较少的情况。而非递归回溯法采用深度优先搜索策略判断当前位置是否符合该问题的解，时间复杂度为O(n2)，在实现大规模的N皇后问题上性能更好。递归回溯法同样采用深度优先搜索策略，但在搜索到不满足约束条件时能及时回溯，整体上提高了解题的效率。时间复杂度较非回溯法更低。四实验心得八皇后问题以前也看过，只是以前没有将测试数据模块和解八皇后问题模块整合到主函数中，后面也想到用MFC实现可视化求解，但是之前都没学过MFC编程，根据网上的资料还是完成了较为基本的程序。这次实验确实学到很多东西，不光是提高了编程能力、代码阅读能力，更掌握了回溯法的递归求解思路。 附录：代码#include#include#include#define max 8using namespace std; int queenmax, sum=0; / max为棋盘最大坐标 /*输出所有皇后的坐标 */void Show_Queen() cout( ; for(int i = 0; i max; i+) coutqueeni+1 ; cout)endl; sum+; /*判断是否满足八皇后问题函数*/int Judge(int n) for(int i = 0; i n; i+) / 检查横排和对角线上是否可以放置皇后 if(queeni = queenn | abs(queeni - queenn) = (n - i) return 1; return 0;/*回溯尝试皇后位置,n为横坐标*/void BackTrack_Queen(int n) for(int i = 0; i max; i+) queenn = i; /* 将皇后摆到当前循环到的位置 */ if(!Judge(n) if(n = max-1 ) Show_Queen(); /* 如果全部摆好，则输出所有皇后的坐标 */ else BackTrack_Queen(n + 1); /* 否则继续摆放下一个皇后 */ int main()while(1) int n;cout*endl;cout* 选择相应序号进行操作： *endl;cout* 1.八皇后问题 2.测试数据 0.退出 *endl;cout*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;jqueenj; if(Judge(max)=1) cout该数据是八皇后问题的解en