n皇后实验报告.doc

实 验 报 告

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

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

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

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

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

要找出”四皇后”问题的解，最可靠的方法就是把各种情况全部检核一遍，将符合条件A的解找出来。但这样做，你要有相当耐心才行，这是很费时的。采用回溯算法进行求解，在搜索的过程中，将不满足条件要求的分支树减去，可以有效的降低算法的时间复杂性。
n后问题的算法描述如下：
剪枝函数：
bool Ok(int t)
{
int i;
for(int i=0;i
return 0;
}
return 1;
}
void Backtrack(int t)
{
if(t>=n){
cout<<"第"< }
sum++;
}
else{
for(int i=0;i
using namespace std;
int *x;//当前解
int n;//皇后的个数N
int sum=1;
bool Ok(int t)//检查参数所指示的这一行皇后放置方案是否满足要求
{
int i;
for(int i=0;i=n){
cout<<"第"< if(j==x[i])
cout<<"1";
else
cout<<"0";
}
cout<后个数 :";
cin>>n;
x=(int *)malloc(sizeof(int)*n);
Backtrack(0);
cout<<"一共的方案数为："<