n皇后试验报告

1、实验报告实验名称n阜后问题课程名称计算机算法设计与分析专业班级：学生姓名：学 号：成 绩:指导老师：实验日期：实验内容要求在一个n*n的棋盘上放置n个皇后，使得它们彼此不受攻击一个皇后可以攻击与之处在同一行或同一列或同一斜线上的任何其他棋子。二、实验基本思想典型深度优先遍历，假设某一行为当前状态，不断检查该行所有 的位置是否能放一个皇后，检索的状态有两种：(1)先从首位开始检查，如果不能放置，接着检查该行第二个位 置，依次检查下去，直到在该行找到一个可以放置一个皇后的地方， 然后保存当前状态，转到下一行重复上述方法的检索。(2)如果检查了该行所有的位置均不能放置一个皇后，说明上一 行皇后放置的

2、位置无法让所有的皇后找到自己适宜的位置，因此就要回溯到上一行，重新检查该皇后位置后面的位置。三、算法设计问题的解可表示为x1:n,表示皇后i放在棋盘的第i行的第xi列a)xi #xj ,i ?j :不允许将任何两个皇后放在同一列上;b)|j-i|*|xj-xi| :不允许两个皇后位于同一条斜线上,问题的解空间的形式为：要找出"四皇后”问题的解，最可靠的方法就是把各种情况全部检核 一遍，将符合条件A的解找出来。但这样做，你要有相当耐心才行， 这是很费时的。采用回溯算法进行求解，在搜索的过程中，将不满足 条件要求的分支树减去，可以有效的降低算法的时间复杂性。n后问题的算法描述如下: 剪枝

3、函数：bool Ok(int t)(if(xt=xi | abs(t-i)=abs(xt-xi)return 0;)return 1;)void Backtrack(int t)if(t>=n)cout<<"第"<<sum<<"个方案：n"for(int i=1;i<=n;i+)for(int j=1;j<=n;j+)if(j=xi)cout<<"1"elsecout<<"0")cout<<endl;)sum+;)elsext

4、=i;if(Ok(t)Backtrack(t+1);)四、实验结果五、实验代码#include<iostream>using namespace std;int *x;/ 当前解int n;/ 皇后的个数Nint sum=1;bool Ok(int t)/检查参数所指示的这一行皇后放置方案是否满足要求int i;for(int i=0;i<t;i+)if(xt=xi | abs(t-i)=abs(xt-xi)return 0;return 1;void Backtrack(int t)if(t>=n)cout<<"第"<<su

5、m<<"个方案：n"for(int i=1;i<=n;i+)for(int j=1;j<=n;j+)if(j=xi)elsecout<<"0")cout<<endl;)sum+;)elsefor(int i=0;i<n;i+)xt=i;if(Ok(t)Backtrack(t+1);)void main()cout<<"输入皇后个数:"cin>>n;x=(int *)malloc(sizeof(int)*n);Backtrack(0);cout<<"一共的方案数为："<<sum-1<<"n"system("pause");六、实验心得通过本次实验的学习，让我了解到了用回溯法可以搜索问题的所 有解。它是一个既带有系统性又带有跳跃性的搜索算法，是按照深度优先策略，从根节点出发搜索解空间树。算法搜索至某一节点时，利 用判断函数先判断该节点内是否包含问题的解， 如果不包含则直接跳 过，节省时间。相关的判断函数要根据实际问题来编写，此比较适合 求解组合数较大的问题。总的来说，这次实验不仅让我基本掌握递归的思想