算法分析与设计实验报告 实验内容：N皇后问题 实验时间：2013.12.3 姓名：杜茂鹏 班级：计科 1101 学号：0909101605 一、实验内容及要求 在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 皇后有1 0 个可行解 五、源代码 #include static int n, sum=0;//可行解个数 static int locate[20]; int place(int k) {//判断是否在一条线上并返回 0,1 for(int i=1;in){ sum++; for(int i=1;i<=n;i++) { for(int a=1;a<=n;a++) { if(alocate[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 m...
