算法分析与设计实验报告 实验内容：N皇后问题 实验时间：2013
3 姓名：杜茂鹏 班级：计科 1101 学号：0909101605 一、实验内容及要求 在n×n 格的棋盘上放置彼此不受攻击的 n 个皇后， 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子
二、实验目的 1
巩固和加深对回溯法的理解 2
了解递归和迭代法在回溯法中的应用 三、算法分析 1
理解皇后不被攻击的条件：n 后问题等价于在n*n 格的棋盘上放置 n 个皇后，任何两个皇后不能放在同一行或同一列或同一斜线上
算法模块简要分析 用数组存储皇后的位置，将 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 皇后有1 0 个可行解 五、源代码 #include static int n, sum=0;//可行解个数 static int locate[20]; int place(int k) {//判断是否在
