n皇后问题--

算法设计及分析n皇后问题---回溯求解国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同“象”那样沿着斜线移动。

双方的皇后是不能在同一行或同一列或同一斜线上对持的。

那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。

高斯在棋盘上放下了N个互不攻击的皇后，他还认为可能有N种不同的放法，这就是有名的“N皇后”问题。

如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。

由于我们的记忆有限，很可能在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。

因此，必须找到一个简易有效、有条不紊的法则才行。

回溯法的基本思想：对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。

这棵树的每条完整路径都代表了一种解的可能。

通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。

在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。

不妨以8皇后为例，设8皇后为x i，她们分别在第i行（i=1,2,3,4,5,6,7,8）,这样问题的解空间就是一个8个皇后所在列的序号，为n元一维向量（x1,x2,,x3,x4,x5,x6,x7,x8），搜索空间是1≤x i≤8（i=1,2,3,4,5,6,7,8）,共88个状态。

约束条件是8个点（1,x1）,(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一列和同一对角线上。

虽然问题共有88个状态，但算法不会真正地搜索这么多的状态，因为回溯法采用的是“走不通就掉头”的策略，而形如（1,1,x3,x4,x5,x6,x7,x8）的状态共有86个，由于1,2号皇后在同一列不满足约束条件，回溯后这些状态是不会搜索的。

用遗传算法解决n皇后问题（李怀远）一、问題提出N皇后问题描述如下：在nxn格棋盘上敖置彼此不受攻击的n个皇后。

按国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

N皇后问题等价于在以下三个约束条件下：约束①任何2个皇后不放在同一行；约束②任何2个皇后不放在同一列；约束③任何2个皇后不放在同斜线；找出一种合法的放置方案。

我们把nxn的棋盘看作二维方阵，其行号从上到下列号从左到右依次编号为0, 1,…， n-l.。

设任意两个皇后，皇后1和皇后2的坐标分别是（i.j）和（k,l）,则如果这两个皇后在从棋盘左上角到右下角的主对角线及其平行线（斜率为-1的线）上，有i-j=k-l=0 ；如果这两个皇后在斜率为+ 1的每一斜线上，有i+j=k+l；以上两个方程分别等价于i-k=j-l 和i-k=l-j因此任两皇后的在同一斜线上的充要条件是l/-^l=l J-/I 式①因此满足两个皇后不在同一斜线上的条件表示为：\i-kM j-l\式②两皇后不在同一行用式表示为:iHk式③两皇后不在同一列用式表示为：j^l式④此属NP问题不易求解，现在我们把任意n个皇后的任意一种放置办法当作一个个体（染色体），把其中的任意一个皇后当作一个基因，用遗传算法来解决该问題。

二、编码方案对于此问题我提出两种编码方案。

A.编码方案1：排列编码用一维n元数组x[0：n-l]来表示一个个体，其中x[i]e{0,l,…,n-1}, x[i]表示皇后i放在棋盘的第i行第x[i]列，即第i行第x[i]列放置一个皇后。

例如，x[0]=0 表示棋盘的第0行第0列敖一个皇后。

数组第i个元素表示第i行的放置情况，可以看作一个基因。

这种编码可以自然的解决了某一行只能放一个皇后的约束，如果数组的每一个元素x[i]都不重复，可以看成0——n-l的一种排列，就自然保证每一列只能放一个皇后。

因此在交叉变异和产生个体时必须注意x[i]的唯一性。

N皇后问题及答案解题⽬在⼀张N∗N的国际象棋棋盘上，放置N个皇后，使得所有皇后都⽆法互相直接攻击得到，（皇后可以直接攻击到她所在的横⾏，竖列，斜⽅向上的棋⼦），现在输⼊⼀个整数N，表⽰在N∗N的棋盘上放N个皇后，请输出共有多少种使得所有皇后都⽆法互相直接攻击得到的⽅案数。

例如下⾯这样的摆法，是4皇后的⼀个解 （1代表有皇后，0代表没有）0 1 0 00 0 0 11 0 0 00 0 1 0输⼊⼀个整数N，代表皇后的个数输出输出⽅案数样例输⼊样例输⼊14样例输⼊28样例输出样例输出12样例输出292⼀、DFS+回溯(1)设已经放好的皇后坐标为(i,j),待放⼊的皇后坐标为(r,c)，则它们满⾜以下关系：（1）不同⾏，即 i ≠ r；（2）不同列，即 j ≠ c；（3）不在斜对⾓线上，即 |i-r| ≠ |j-c|.可以在⼀⾏逐列尝试，这样就不⽤考虑（1）了。

#include <iostream>#include <algorithm>#include <cstring>using namespace std;int n, tot = 0;int col[15] = {0}, ans[15] = {0}; //col[i]的值为第i⾏的皇后的列数的值，即j,ans[]数组⽤来存放结果bool check(int c, int r) //检查是否和已经放好的皇后冲突{for (int i = 0; i < r; i++)if (col[i] == c || (abs(col[i] - c) == abs(i - r))) //因为是逐⾏放置，所以只考虑纵向和斜向return false;return true;}void dfs(int r,int m) //在第r⾏放皇后,m表⽰⾏数{if(r==m){ //r==m,即皇后放到最后⼀⾏，满⾜条件，tot++,返回;tot++;return;}for(int c=0;c<m;c++) //在此⾏逐列尝试if(check(c,r)){ //检查是否冲突col[r]=c; //不冲突就在此列放皇后dfs(r+1,m); //转到下⼀⾏继续尝试}}int main(){cin>>n;for (int i = 0; i <= 13; i++) //算出所有N皇后的答案，先打表，不然会超时{memset(col, 0, sizeof(col)); //清空col，准备计算下⼀个N皇后问题tot = 0;dfs(0,i);ans[i] = tot;}cout << ans[n] << endl;return 0;}在上述程序中，dfs()⼀⾏⾏放置皇后，时间复杂度为O(N!)；check()判断冲突，时间复杂度为O(N)，总的为O(N*N!)！⾮常的⾼。

n皇后问题课程设计一、教学目标本节课的教学目标是让学生掌握“N皇后问题”的解决方法，理解其背后的数学原理和计算机科学应用。

知识目标要求学生了解“N皇后问题”的定义、解法和优化策略；技能目标要求学生能够运用所学的知识解决实际问题，编写出相应的算法程序；情感态度价值观目标则是培养学生对计算机科学的兴趣，提高其创新意识和解决问题的能力。

二、教学内容本节课的教学内容主要包括三个部分：第一部分是“N皇后问题”的定义和基本解法，让学生了解问题背景和基本概念；第二部分是“N皇后问题”的优化策略，让学生掌握如何提高算法效率；第三部分是“N皇后问题”的计算机编程实践，让学生亲自动手编写程序，巩固所学知识。

三、教学方法为了达到本节课的教学目标，我们将采用以下教学方法：首先，通过讲授法向学生介绍“N皇后问题”的基本概念和解法；其次，运用讨论法让学生分组讨论优化策略，促进学生思考；然后，采用案例分析法分析实际问题，引导学生将所学知识应用于实践；最后，通过实验法让学生动手编程，培养其实际操作能力。

四、教学资源为了支持本节课的教学内容和教学方法，我们将准备以下教学资源：首先，教材和参考书，为学生提供理论支持；其次，多媒体资料，如课件、视频等，帮助学生形象理解问题；再次，实验设备，如计算机等，让学生进行编程实践；最后，网络资源，如在线编程平台等，为学生提供更多学习资源和交流渠道。

五、教学评估为了全面、客观地评估学生在“N皇后问题”课程中的学习成果，我们将采取以下评估方式：1.平时表现：通过课堂参与、提问、回答问题等方式评估学生的学习态度和理解程度，占总评的30%。

2.作业：布置与课程相关的中等难度练习题，要求学生在规定时间内完成，占总评的20%。

3.实验报告：学生在实验过程中独立编写程序，并撰写实验报告，占总评的20%。

4.期末考试：期末考试中将包含“N皇后问题”的相关题目，测试学生对该课程知识的掌握程度，占总评的30%。

六、教学安排本课程的教学安排如下：1.授课时间：共8课时，每课时45分钟。

n 后问题1 问题描述：N 皇后问题是一个古老而著名的问题。

该问题是十九世纪著名的数学家高斯1850年提出的。

八皇后问题要求在一个N ＊N 的棋盘上放上N 个皇后，使得每一个皇后既攻击不到另外N-1个皇后，也不被另外N-1个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法？并找出所有的摆法。

因此，N 皇后问题等于要求N 个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

2 回朔法回溯法有“通用的题解法”之称。

从问题的某种可能情况出发，搜索所有能到达的可能情况，然后以其中一种可能的情况为新的出发点，继续向下探索，当所有可能情况1 2 3 4 5 6 7 8 1 2 3 4 5 6 78都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。

适用于解组合是较大的问题。

回朔法思想：1针对所给问题，定义问题的解空间。

2.确定易于搜索的解空间结构。

3.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

在搜索过程中，通常采用两种策略避免无效搜索：一是用约束函数剪去得不到可行解的子树；二是用限界函数剪去得不到最优解的子树。

这两类函数统称为剪枝函数。

回溯算法的一个显著的特性是在搜索过程中动态产生问题的解空间。

在任何时刻，只保存从根结点到当前扩展结点的路径。

因此，回溯算法的空间需求为o（n），（n为从根结点起最长路径的长度）。

而显式地存储整个解空间则需要o（2n）或o（n!）内存空间。

回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。

void backtrack (int t){if (t>n) output(x);elsefor (int i=f(n,t);i<=g(n,t);i++){x[t]=h(i);if (constraint(t)&&bound(t)) backtrack(t+1);}}采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。

对n皇后问题进行求解算法的算法描述。

文章标题：探索N皇后问题的求解算法N皇后问题是一个经典的组合优化问题，它要求在一个N×N的棋盘上放置N个皇后，使得它们互相不攻击。

这个问题在计算机科学和算法设计领域有着重要的地位，它不仅挑战了算法设计者的智慧，而且在实际中有着广泛的应用。

在本文中，我们将深入探讨N皇后问题的求解算法，并尝试用代码实现一个高效的解法。

一、N皇后问题的定义N皇后问题最初来源于围棋界的柯尼斯堡爵士（Carl Friedrich Gauss）在1850年提出。

在N×N的棋盘上放置N个皇后，使得它们不同行、不同列、不同对角线上。

这意味着任意两个皇后之间不能出现攻击的情况，即它们不能位于同一行、同一列或同一对角线上。

二、暴力求解算法最直观的一种解法是暴力穷举法。

我们可以通过递归的方式，对每一行的每一个位置进行搜索，直到找到所有满足条件的解。

这种方法的复杂度是O(N!)，随着N的增大，计算量急剧增加，性能是不可接受的。

三、回溯算法回溯算法是一种更加高效的解法。

它利用了剪枝策略，在搜索的过程中及时去掉不可能的解，从而减少了计算量。

我们可以通过递归的方式，依次尝试每一行的每一个位置，如果当前位置符合条件，则继续深入搜索，如果不符合条件，则进行回溯。

回溯算法的复杂度是O(N^N)，相比暴力穷举法，性能有了明显的提升。

四、位运算优化除了回溯算法，我们还可以通过位运算的优化来提高算法的效率。

我们可以用一个整数来表示每一行皇后的位置，然后利用位运算的与、或、异或等操作来判断是否有冲突。

这种方法的复杂度是O(1)，性能是非常高效的。

五、个人观点和总结总的来看，N皇后问题是一个挑战性很高的问题，它需要我们充分发挥创造力和智慧，不断探索各种求解算法。

在实际应用中，我们可以根据具体的场景和要求来选择合适的算法。

对于小规模的N，暴力穷举法可能是一个不错的选择；对于大规模的N，我们可以考虑采用回溯算法或位运算优化的方法。

常规N皇后解决问题过程一．问题描述运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；通过上述的基本思路，我们可以将问题描述为：X(j)表示一个解的空间，j表示行数，里面的值表示可以放置在的列数，抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。

应用回溯法，当可以放置皇后时就继续到下一行，不行的话就返回到第一行，重新检验要放的列数，如此反复，直到将所有解解出。

也就是对于N×N的棋盘，选择出N个符合i!=r∧j!=s∧|i-r|!=|j-s|∨(i+r)!=(j+s)的点的排列总数。

二．伪代码：判断点是否符合要求：place(k, X)I=1While i<k doIf x[i]==x[k] orabs(x[i]-x[k])==abs(i-k) thenReturn falseI=i+1Return true求问题的所有解：Nqueens(n, X)Sum=0 , X[1]=0 , k=1While k>0 doX[k]=X[k]+1While X[k]<=n and !(place(k,x))X[k]=X[k]+1If X[k]<=n thenSum=Sum+1ElseK=K+1 ,X[k]=0ElseK=K-1Print sum三．代码实现#include <iostream>using namespace std;#include <math.h>/*检查可不可以放置一个新的皇后*/ bool place(int k, int *X){int i;i=1;while(i<k){if((X[i]==X[k])||(abs(X[i]-X[k] )==abs(i-k)))return false;i++;}return true;}/*求解问题的所有解的总数，X存放列数*/ void Nqueens(int n,int *X){int k,sum=0;X[1]=0;k=1;while(k>0){X[k]=X[k]+1;while((X[k]<=n)&&(!place(k, X)))X[k]=X[k]+1;if(X[k]<=n)if(k==n){for(int i=1;i<=n;i++)cout<<X[i]<<" ";cout<<endl;sum++;}else{k=k+1;X[k]=0;}elsek=k-1;}cout<<"解的总数为："<<sum<<endl;}int main(){int n;int *X;cout<<"请输入皇后的个数:";cin>>n;X=new int[n];cout<<"问题的解如下:"<<endl;Nqueens(n,X);return 0;}五．存在的问题当皇后个数N大于等于16以上，程序对棋盘的扫描次数大到惊人：从维基百科列出的结果不难看出，在25皇后时，符合条件的解集已经如此庞大了。

⼋皇后问题（N皇后问题）⼋皇后问题，是⼀个古⽼⽽著名的问题，是回溯算法的典型案例。

该问题是国际西洋棋棋⼿马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放⼋个皇后，使其不能互相攻击，即任意两个皇后都不能处于同⼀⾏、同⼀列或同⼀斜线上，问有多少种摆法。

⾸先来看看这张模拟⼋皇后的图。

这张图说明皇后具有横轴、竖轴以及两个斜轴⽅向的杀伤⼒，也就是像⽶字形⼀样；为了减少判断，我们按照⼀个⽅向往另⼀个⽅向排列，中间不能跳⾏，这样我们就可以只判断已经有皇后的位置，还没有皇后的就可以偷懒不⽤判断了。

我的⽅案是：1.从最下⾯开始排列，然后往上添加，从左往右排列，这样就只需要判断⽐⾃⼰Y坐标低的具有杀伤能⼒的位置有没有皇后就OK ⽅法是把⾃⼰假定要放置皇后的位置的X和Y轴都依据判断特性进⾏处理；例如，左斜线X和Y轴都减1；中间的只需要把Y 轴减1；右边的和左边的相反，X轴加1，Y轴减1；注意处理边界问题。

2.为了找到合适的位置我们需要在查找失败的时候具备回溯的能⼒，就需要退回到前⼀⾏（Y=Y-1，注意XY是否到边界），直⾄能回溯或者全部判断完毕，每次回溯的时候记得X轴要从头开始 3.通过⼀个数据结构记录正在查找的⽅案，通过另⼀个数据结构记录已经找到的⽅案，当然也可以⽤⼀个变量记录⽅案个数下⾯这张⿊⾊背景是其中⼀个⽅案的截图，第⼀⾏代表皇后的坐标xy；后⾯的是棋盘，这⾥输出竖轴是x，横轴是y，从上到下，从左到右，其中*是边界，空格是空区，#是皇后。

#include <iostream>#include <cstring>#include "DTString.h"#include "LinkList.h" // 这⾥使⽤链表存储皇后的位置using namespace std;using namespace DTLib;template <int SIZE> // N皇后问题，SIZE表⽰皇后个数或者棋盘⼤⼩class QueenSolution : public Object{protected:enum { N = SIZE + 2 }; // N表⽰棋盘⼤⼩，为了边界识别，棋盘四周都要加⼀格struct Pos : public Object // ⽅位结构体{Pos(int px = 0, int py = 0) : x(px), y(py) { }int x;int y;};int m_chessboard[N][N]; // 棋盘，0表⽰空位，1表⽰皇后，2表⽰边界Pos m_direction[3]; // 共3个⽅向；⽅向-1、-1表⽰左斜线；0、-1表⽰下⽅；1、-1表⽰右斜线；⾸先从最下⽅开始，所以只需考虑下⾯的⾏。