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皇后问题递归算法想象一下，有一个棋盘，上面要放下几个皇后。

这个皇后可不是普通的角色，她可厉害了，能横着、竖着、斜着攻击其他棋子。

没错，皇后就是这么霸道，咱们要确保她们互不干扰。

这个事情听起来有点棘手，但其实只要动动脑筋，找到一些聪明的方式，问题就迎刃而解了。

说到这里，很多小伙伴可能会想：“这不是简单的下棋吗？有什么难的？”可是，等你真正上手的时候，嘿嘿，才发现事情并没有想象中那么简单。

我们从一个小小的例子开始吧。

假如棋盘是个4×4的小方块，咱们的目标就是在这个方块上放四个皇后。

听起来简单吧？但试想一下，放下第一个皇后没问题，她随便摆哪儿都行，棋盘上空荡荡的。

但是当你放下第二个皇后时，哎哟，她可就要考虑第一位皇后的地盘了，不能让她们互相看对方的脸呀。

接下来再放第三个、第四个，感觉压力山大，像是要参加一场马拉松比赛，刚开始风驰电掣，后来就感觉体力不支，越往后越是踌躇满志又心慌慌。

于是，咱们决定采用递归的方式来解决这个问题。

你说，递归是什么鬼？其实就是一种方法，简单点说就是“自己叫自己”。

我们可以从放第一个皇后开始，然后把剩下的事情交给下一个步骤，就像是把作业一层一层递交给老师，直到所有问题都解决为止。

我们可以把当前棋盘的每一行都视为一个新的阶段，逐行逐列地放置皇后。

如果这一步走不通，那就“咱们重来”。

这就像是人生中的很多事情，不顺利的时候就换个思路，继续前进。

当你把第一行的皇后放好，接下来就要检查第二行的每一个位置，看看哪里可以放。

每检查一个位置，就像是在打探敌情，谨慎又小心。

噢，不行，这个位置被第一行的皇后盯上了，得换个地方。

这样一来，你可能会发现，有的地方放不下，有的地方则一片大好，任你选择。

一直检查到棋盘的最后一行，如果成功放下皇后，哇，心里那种成就感，简直像中了大奖一样！可是如果发现放不下，那就要退回去，换个方案，哪怕是从头再来。

这就是递归的魅力，既简单又复杂，似乎在和我们的人生进行一场心灵的对话。

算法分析与设计实验报告第三次附加实验附录：完整代码（回溯法）//回溯算法递归回溯n皇后问题#include<iostream>#include<time.h>#include<iomanip>#include"math.h"using namespace std;class Queen{friend int nQueen(int); //定义友元函数，可以访问私有数据private:bool Place(int k); //判断该位置是否可用的函数void Backtrack(int t); //定义回溯函数int n; //皇后个数int *x; //当前解long sum; //当前已找到的可行方案数};int main(){int m,n;for(int i=1;i<=1;i++){cout<<"请输入皇后的个数："; //输入皇后个数cin>>n;cout<<"皇后问题的解为："<<endl;clock_t start,end,over; //计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();m=nQueen(n); //调用求解的函数cout<<n<<"皇后问题共有";cout<<m<<"个不同的解！"<<endl; //输出结果end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间cout<<endl;}system("pause");return 0;}bool Queen::Place(int k)//传入行号{for(int j=1;j<k;j++){if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))//如果两个在同一斜线或者在同一列上，说明冲突，该位置不可用{return false;}}return true;}void Queen::Backtrack(int t){if(t>n){sum++;/*for(int i=1;i<=n;i++) //输出皇后排列的解{cout<<x[i]<<" ";}cout<<endl;*/}else{//回溯探索第i行的每一列是否有元素满足要求for(int i=1;i<=n;i++){x[t]=i;if(Place(t)){Backtrack(t+1);}}}}int nQueen(int n){Queen X; //定义Queen类的对象X//初始化XX.n=n;X.sum=0;int *p=new int[n+1]; //动态分配for(int i=0;i<=n;i++) //初始化数组{p[i]=0;}X.x=p;X.Backtrack(1);delete[] p;return X.sum;//输出解的个数}完整代码（回溯法）//回溯算法迭代回溯n皇后问题#include<iostream>#include<time.h>#include<iomanip>#include"math.h"using namespace std;class Queen{friend int nQueen(int); //定义友元函数private:bool Place(int k); //定义位置是否可用的判断函数void Backtrack(void); //定义回溯函数int n; // 皇后个数int *x; // 当前解long sum; // 当前已找到的可行方案数};int main(){int n,m;for(int i=1;i<=1;i++){cout<<"请输入皇后的个数：";cin>>n;cout<<n<<"皇后问题的解为："<<endl;clock_t start,end,over; //计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();m=nQueen(n); //调用求解皇后问题的函数cout<<n<<"皇后问题共有";cout<<m<<"个不同的解!"<<endl;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间cout<<endl;}system("pause");return 0;}bool Queen::Place(int k){for (int j=1;j<k;j++){if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) //如果两个皇后在同一斜线或者在同一列上，说明冲突，该位置不可用{return false;}}return true;}void Queen::Backtrack() //迭代法实现回溯函数{x[1] = 0;int k = 1;while(k>0){x[k] += 1; //先将皇后放在第一列的位置上while((x[k]<=n)&&!(Place(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++;x[k]=0;}}else//没有找到合适的位置则回溯{ k--; }}}int nQueen(int n){Queen X; //定义Queen类的对象X//初始化XX.n=n;X.sum=0;int *p=new int[n+1];for(int i=0;i<=n;i++){p[i]=0;}X.x=p;X.Backtrack();delete []p;return X.sum; //返回不同解的个数}。

n皇后问题【问题描述】在n×n的国际象棋盘上，放置n个皇后，使任何一个皇后都不能吃掉另一个,需满足的条件是：同一行、同一列、同一对角线上只能有一个皇后。

求所有满足要求的放置方案。

【输入】一个正整数n，表示皇后的个数。

【输出】每行代表一种放置方案：第i行的第一个数是i，表示第i种方案，后面一个冒号，然后是用空格隔开的n个数，其中第i个数x[i]表示第i行上的皇后放在第x[i]列；最后一行：一个整数，表示方案总数。

〖问题描述〗在一个8×8的棋盘里放置8个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。

〖问题分析〗(聿怀中学吕思博)这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。

主要解决以下几个问题：1、冲突。

包括行、列、两条对角线：（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I 为下标的标记置为被占领状态；（3）对角线：对角线有两个方向。

在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。

因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。

2、数据结构。

（1）解数组A。

A[I]表示第I个皇后放置的列；范围：1..8（2）行冲突标记数组B。

B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8 （3）对角线冲突标记数组C、D。

C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7 D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16〖算法流程〗1、数据初始化。

2、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于0（未被占领）:如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。

算法设计与分析实验报告姓名：杨勇涛班级：计科102一、实验名称：n皇后问题时间：2012年4月25日，星期三，第四节地点：12#311二、实验目的及要求在n*n格的棋盘上放置彼此不受攻击的n皇后。

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

N皇后问题等价于在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行同一列或同一列统统一些线上。

三、实验环境VC++四、实验内容从键盘上输入n皇后的数目，输出所有的结果五、算法描述及实验步骤Ｎ×Ｎ皇后问题的求解过程就是一个试探回逆的过程。

如图－１（图１－１）１、首先查找第一行的可放位置，第一行全部可以放，那么我们就先将第一个皇后放在（０，０）点。

（图１－２）２、再查找第二行，由于第一行的（０，０）已经放了皇后，故第二行的（１，０）和（１，１）都能放皇后了，可放的就是（１，２）和（１，３）点，在（１，２）放上皇后。

（图１－３）３、再查找第三行，查找所以发现第三行没有可放的位置了，回逆到第二行讲皇后放到（１，３）再查找第３行。

如果还不行，就回到第一行将第一行的皇后放人下一个可放的点，依次类推，查找Ｎ×Ｎ上的所以可放的位置，直到第一行所以位置被放完，输出结果。

４、根据上面的规律可以发现，对于一个皇后放在坐标（ｘ，ｙ），它的下一行位置为（ｘ－１，ｙ）（ｘ，ｙ）（ｘ＋１，ｙ）的坐标都不能再放皇后。

我们用一个数组来存放本行能放皇后的点。

用循环来查找上面行对本行的影响六、调试过程及实验结果七、总结回溯法有“通用的解题法”之称。

用它可以系统的搜索一个问题的所有解或任一解。

回溯法是一个既带有系统性又带有跳跃性的搜索算法。

八、附录（源程序清单）#include "math.h"#include <iostream>using namespace std;bool valid(int i,int j);//判断安置元素的合法性void trial(int i); //递归安置元素void print(); //显示布局int q; //皇后数int *a; //存储布局元素int count = 0; //合法布局的序号int main(int argc, char* argv[]){cout<<"请输入皇后数:"<<endl;cin>>q;a = new int[q*q];for(int j=0;j<q*q;j++)a[j] = 0;trial(0);cout<<"布局完毕"<<endl;return 0;}void trial(int i) //递归安置元素{if(i>=q)print();elsefor(int j=0;j<q;j++){a[i*q+j] = 1;if(valid(i,j))trial(i+1);a[i*q+j] = 0;}}bool valid(int i,int j) //判断安置元素的合法性{bool b=true;for(int i1=0;i1<i;i1++)for(int j1=0;j1<q;j1++)if(a[i1*q+j1]==1){if(j1==j)//判断是否在同一列b = false;else if(abs(i-i1)==abs(j-j1))//判断是否在对角线b = false;}return b;}void print() //显示布局{count++;cout<<"第"<<count<<" 种布局:"<<endl;for(int m=0;m<q;m++){for(int n=0;n<q;n++){cout<<a[m*q+n]<<" ";}cout<<endl;}cout<<"----------------------------------------"<<endl; }。

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皇后问题算法一、实验目的及要求所要涉及或掌握的知识：1.了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。

2.运用迭代的方法实现6皇后问题，求解得到皇后不相互攻击的一个解。

3.在运用迭代的方法实现编程时，要注意回溯点。

二、N皇后问题：在一个 N * N 的国际象棋棋盘中，怎样放置 N 个皇后才能使 N 个皇后之间不会互相有威胁而共同存在于棋局中，即在 N * N 个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。

三、问题分析最容易想到的方法就是有序地从第 1 列的第 1 行开始，尝试放上一个皇后，然后再尝试第 2 列的第几行能够放上一个皇后，如果第 2 列也放置成功，那么就继续放置第 3 列，如果此时第 3 列没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第 2 步），将上一步（第 2 步）所放置的皇后的位置再重新取走放在另一个符合要求的地方…如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。

四、具体实现package queen;import java.util.Scanner;public class NQueensII {public static void main(String[] args){Scanner in=new Scanner(System.in);System.out.println("Please enter the number of queen you want(请输入你要求解的皇后的个数)");int n=in.nextInt();Queen(n);}/***用回溯法设计函数Queen(n)求解*/public static boolean Place(int x[],int k)//考察皇后k放置在x[k]列是否发生冲突{for(int i=1; i<k; i++)if (x[k]==x[i]||Math.abs(k-i)==Math.abs(x[k]-x[i])) return false;return true;}public static void Queen(int n){int x[]=new int[n+1];for (int i=1; i<=n; i++)//初始化x[i]=0;int k=1;while (k>=1){x[k]=x[k]+1;//在下一列放置第k个皇后while (x[k]<=n&&!Place(x,k))x[k]=x[k]+1;//搜索下一列if (x[k]<=n && k==n){ //得到一个解，输出System.out.println("The answer is(得到的解是):");for (int i=1; i<=n; i++)System.out.print("("+i+","+x[i]+")"+" ");System.out.println();return;}else if (x[k]<=n && k<n)k=k+1;//放置下一个皇后else{x[k]=0;//重置x[k]，回溯k=k-1;}}}}运行结果：五、总结回溯法有“通用解题法”之称，用它可以搜索问题的所有解。

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);}}采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。

一、问题11、问题描述一、N皇后问题在N*N的棋盘上放置彼此不受攻击的N个皇后。

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

N皇后的问题等价于在N*N大小的棋盘中放置N个皇后，任何2个皇后都不放在同一行或同一列或同一斜线上。

使用队列式分支限界法，求出N个皇后的一种放置方案。

2、算法设计思想分支限界法解向量：因为皇后不能同行或同列，所以我们可以用这样一个解向量来表示问题的解X[x1,x2…xn] x=[1,2,3…n];表示1~n行皇后位于的列数解空间：因为皇后不能同行同列，因此解空间为排列树，使用广度优先搜索的方式搜索整棵树剪枝函数：判断新摆放的皇后是否在已经摆放的皇后的斜线上3、算法过程描述第一行第一列放置皇后，这个节点成为拓展节点，产生n-1个活结点，加入队列，第一行第二列到第n列分别产生n-1个活结点，加入队列，从队列取出第一个活结点，即第二行第二列，不满足剪枝函数的要求，除去这个节点，队列中的节点依次取出，满足剪枝函数的节点成为拓展节点产生活结点并加入队列，当成功进行到叶子节点时，就能得到问题的一个解，队列为空时，就得到了所有解4、算法实现及运行结果#include<iostream>#include<ctime>using namespace std;bool isOK(int n, int pieces[]){//剪枝函数//判断当前状态是否合理，即皇后会不会互相攻击for (int i = 1; i <= n-1; i++){for (int j = i + 1; j <= n; j++){int left = -(j - i);//向左的斜线int right = (j - i);//向右的斜线if (pieces[j] == pieces[i] + left||pieces[j] == pieces[i] + right){//第i行皇后和第j行皇后会互相攻击return false;}}}//所有皇后都不会互相攻击return true;}void swap(int &a, int &b){int t = a;a = b;b = t;}void nQueen(int n, int t, int pieces[]){if (t > n){for (int i = 1; i <= n; i++){for (int j = 1; j < pieces[i]; j++)cout << "- ";cout << pieces[i]<<" ";for (int j = pieces[i] + 1; j <= n; j++)cout << "- ";cout << endl;}cout << endl;}else{for (int i = t; i <= n; i++){swap(pieces[t], pieces[i]);if (isOK(t, pieces)){nQueen(n, t + 1, pieces);}swap(pieces[t], pieces[i]);}}}int main (){int n;cin >> n;int *pieces = new int[n + 1];for (int i = 1; i <= n; i++){pieces[i] = i;}nQueen(n, 1, pieces);cout << "OK" << endl;system("pause");}5、算法复杂度分析及算法改进子集树O(n^n)*剪枝函数(包括判断行列和斜线)O(n)=O(n^n+1)。