n皇后问题算法实验报告

嘗竄 Ntolall醫料曝科画“ 2014丄一丄9專“題沏1 韋 12R2一、实验内容及要求在nXn格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。二、实验目的1. 巩固和加深对回溯法的理解2. 了解递归和迭代法在回溯法中的应用三、算法分析1. 理解皇后不被攻击的条件：n后问题等价于在n*n格的棋盘上放置n个 皇后，任何两个皇后不能放在同一行或同一列或同一斜线上。2. 算法模块简要分析用数组存储皇后的位置，将i设置为0.Int place(*x,n):数组x用来表示列数，n为皇后个数，用来判断 皇后是否被攻击， 判断的条件是 (xi-xn=i-n|xi-xn=n-i|xi=xn)即用来判断“同一行或同一 列或同一斜线上”Int prin t(* x,n):打印皇后解的空间。Int iniprin t(* x,n):初始化打印函数，相当于对棋盘初始化。将可以 放皇后的位置记为“1”不放皇后的位置记为“0”Int Nqueen(int n):n皇后问题求解，如果满足一组可行解，sum+。Int i=0,如果xi=n的时候即进行下一行，i+ ；当i=n时，sum+；输出该组 可行解的个数和位置的矩阵。并且i-，回溯到上一层继续搜索可行解。四、运行结果及分析1、三皇后没有可行解2、2.4个皇后有2个可行解3.5皇后有10个可行解五、源代码#includestatic int n, sum=O;/可行解个数 static int locate20;int place(int k)/判断是否在一条线上并返回0,1 for(i nt i=l;in)sum+;for(int i=l;i二n;i+)for(int a=1;a=n;a+)if(alocatei) pri ntf(“ * );elseprin tf( 2 ); /如果已经安排完毕则输出棋盘和记录 printf (n);printf(第小种解法如上图所示：,sum); for(int i=l;i二n;i+) pri ntf (%d ,loca tei);printf (nnn);else/如果没有安排完则递归继续下一个安排，无解则返回上一个 for(int i=l;i二n;i+)locatem二i; if(place(m) Back(m+1);int main()prin tf（请输入皇后数量:）;scanf（%d，&n）;printf（n（2 表示皇后，*表示棋盘）nnn）；Back（l）;printf（d个皇后共有以上%小种解法nnn,n,sum）;六、实验心得回溯法有“通用解题法”之称，用它可以搜索问题的所有解。它是一个既带 有系统性又带有跳跃性的搜索算法，是按照深度优先策略，从根节点出发搜索解 空间树。算法搜索至某一节点时，利用判断函数先判断该节点内是否包含问题的 解，如果不包含则直接跳过，节省时间，相关的判断函数根据实际问题来编写。 比较适合求解组合数较大的问题。通过本次试验，对回溯法有了深刻的理解，并且对递归得到了巩固。在编写N皇后算法的过程中，遇到了一些问题，当以普通的方式回溯时，当 n=ll时，程序运行时间变得很长，说明该算法的时间复杂度比较大。由于时间 原因没有来得及使用递归，接下来可以比较一下两者的算法的时间复杂度。程序不是一时之事，需要长时间的积累，逐步付诸实践才能真正的掌握。