算法分析与设计实验报告
实验内容：N皇后问题
实验时间：2013.12.3
姓名：***
班级：计科1101
学号：**********
一、实验内容及要求
在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

二、实验目的
1.巩固和加深对回溯法的理解
2.了解递归和迭代法在回溯法中的应用
三、算法分析
1.理解皇后不被攻击的条件：n后问题等价于在n*n格的棋盘上放置n个皇后，任何两个皇后不能放在同一行或同一列或同一斜线上。

2.算法模块简要分析
用数组存储皇后的位置，将i设置为0.
Int place(*x,n) :数组x[] 用来表示列数，n为皇后个数，用来判断皇后是否被攻击，判断的条件是（x[i]-x[n]==i-n||x[i]-x[n]==n-i||x[i]==x[n]）即用来判断“同一行或同一列或同一斜线上”。

Int print(*x,n):打印皇后解的空间。

Int iniprint(*x,n):初始化打印函数，相当于对棋盘初始化。

将可以放皇后的位置记为“1”，不放皇后的位置记为“0”。

Int Nqueen(int n):n皇后问题求解，如果满足一组可行解，sum++。

Int i=0,如果x[i]>=n的时候即进行下一行，i++；当i=n时，
sum++；输出该组可行解的个数和位置的矩阵。

并且i--，回溯到上一层继续搜索可行解。

四、运行结果及分析
1、三皇后没有可行解
2、
2.4个皇后有2个可行解
3.5皇后有10个可行解
五、源代码
#include<stdio.h>
static int n, sum=0;//可行解个数
static int locate[20];
int place(int k)
{//判断是否在一条线上并返回0,1
for(int i=1;i<k;i++){
if(locate[i] == locate[k] || (i+locate[i])==(locate[k]+k)||(locate[i]-i)==(locate[k]-k))
return 0;
}
return 1;
}
void Back(int m)
{
if(m>n){
sum++;
for(int i=1;i<=n;i++)
{
for(int a=1;a<=n;a++)
{
if(a<locate[i]||a>locate[i])
printf(" * ");
else
printf(" \2 "); //如果已经安排完毕则输出棋盘和记录
}
printf("\n");
}
printf("第%d种解法如上图所示: ",sum);
for(int i=1;i<=n;i++)
printf("%d ",locate[i]);
printf("\n\n\n");
}
else
{//如果没有安排完则递归继续下一个安排，无解则返回上一个
for(int i=1;i<=n;i++)
{
locate[m]=i;
if(place(m))
Back(m+1);
}
}
}
int main()
{
printf("请输入皇后数量:");
scanf("%d",&n);
printf("\n(\2表示皇后，*表示棋盘)\n\n\n");
Back(1);
printf("%d个皇后共有以上%d种解法\n\n\n",n,sum);
}
六、实验心得
回溯法有“通用解题法”之称，用它可以搜索问题的所有解。

它是一个既带有系统性又带有跳跃性的搜索算法，是按照深度优先策略，从根节点出发搜索解
空间树。

算法搜索至某一节点时，利用判断函数先判断该节点内是否包含问题的解，如果不包含则直接跳过，节省时间，相关的判断函数根据实际问题来编写。

比较适合求解组合数较大的问题。

通过本次试验，对回溯法有了深刻的理解，并且对递归得到了巩固。

在编写N皇后算法的过程中，遇到了一些问题，当以普通的方式回溯时，当n>=11时，程序运行时间变得很长，说明该算法的时间复杂度比较大。

由于时间原因没有来得及使用递归，接下来可以比较一下两者的算法的时间复杂度。

程序不是一时之事，需要长时间的积累，逐步付诸实践才能真正的掌握。