n皇后实验报告.doc

实 验 报 告

实验名称 n皇后问题
课程名称 计算机算法设计与分析

专业班级： 学生姓名：
学 号： 成 绩：
指导老师： 实验日期：

一、 实验内容
要求在一个n*n的棋盘上放置n个皇后，使得它们彼此不受攻击。一个皇后可以攻击与之处在同一行或同一列或同一斜线上的任何其他棋子。

二、 实验基本思想
典型深度优先遍历，假设某一行为当前状态，不断检查该行所有的位置是否能放一个皇后，检索的状态有两种：
（1）先从首位开始检查，如果不能放置，接着检查该行第二个位置，依次检查下去，直到在该行找到一个可以放置一个皇后的地方，然后保存当前状态，转到下一行重复上述方法的检索。
（2）如果检查了该行所有的位置均不能放置一个皇后，说明上一行皇后放置的位置无法让所有的皇后找到自己合适的位置，因此就要回溯到上一行，重新检查该皇后位置后面的位置。

三、 算法设计
问题的解可表示为x[1:n]， 表示皇后i放在棋盘的第i行的第x[i]列。
a)x[i]≠x[j] ,i≠j ：不允许将任何两个皇后放在同一列上；
b)|j-i|≠|x[j]-x[i]| :不允许两个皇后位于同一条斜线上。
问题的解空间的形式为：

要找出”四皇后”问题的解，最可靠的方法就是把各种情况全部检核一遍，将符合条件A的解找出来。但这样做，你要有相当耐心才行，这是很费时的。采用回溯算法进行求解，在搜索的过程中，将不满足条件要求的分支树减去，可以有效的降低算法的时间复杂性。
n后问题的算法描述如下：
剪枝函数：
bool Ok(int t)
{
int i;
for(int i=0;i<t;i++){
if(x[t]==x[i] || abs(t-i)==abs(x[t]-x[i]))
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==x[i])
cout<<"1";
else
cout<<"0";
}
cout<<endl;
}
sum++;
}
else{
for(int i=0;i<n;i++){
x[t]=i;
if(Ok(t))
Backtrack(t+1);
}
}
}

四、 实验结果

五、实验代码
#include<iostream>
using namespace std;
int *x;//当前解
int n;//皇后的个数N
int sum=1;
bool Ok(int t)//检查参数所指示的这一行皇后放置方案是否满足要求
{
int i;
for(int i=0;i<t;i++){
if(x[t]==x[i] || abs(t-i)==abs(x[t]-x[i]))
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==x[i])
cout<<"1";
else
cout<<"0";
}
cout<<endl;
}
sum++;
}
else{
for(int i=0;i<n;i++){
x[t]=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");
}

六、实验心得
通过本次实验的学习，让我了解到了用回溯法可以搜索问题的所有解。它是一个既带有系统性又带有跳跃性的搜索算法，是按照深度优先策略，从根节点出发搜索解空间树。算法搜索至某一节点时，利用判断函数先判断该节点内是否包含问题的解，如果不包含则直接跳过，节省时间。相关的判断函数要根据实际问题来编写，此比较适合求解组合数较大的问题。 
总的来说，这次实验不仅让我基本掌握递归的思想，而且进一步提高了自己的自学能力和编程能力，使我对算法的分析与设计有更深刻的认识。程序不是一时之事，需要长时间的积累，逐步付诸实践才能真正的掌握，我会继续努力学习，争取做得更好。