基本算法4-回溯法-N皇后问题

n皇后问题实验报告n皇后问题实验报告引言：n皇后问题是一个经典的数学问题，它要求在一个n×n的棋盘上放置n个皇后，使得它们互相之间不能相互攻击，即任意两个皇后不能处于同一行、同一列或同一对角线上。

本实验旨在通过编程实现n皇后问题的求解，并探索不同算法在解决该问题上的性能差异。

实验步骤及结果：1. 回溯算法的实现与性能分析回溯算法是最常见的解决n皇后问题的方法之一。

它通过递归的方式遍历所有可能的解，并通过剪枝操作来提高效率。

我们首先实现了回溯算法，并对不同规模的问题进行了求解。

在测试中，我们将问题规模设置为4、8、12和16。

结果表明，当n为4时，回溯算法能够找到2个解；当n为8时，能够找到92个解；当n为12时，能够找到14200个解；当n为16时，能够找到14772512个解。

可以看出，随着问题规模的增加，回溯算法的求解时间呈指数级增长。

2. 启发式算法的实现与性能分析为了提高求解效率，我们尝试了一种基于启发式算法的解决方法。

在该方法中，我们使用了遗传算法来搜索解空间。

遗传算法是一种模拟生物进化过程的优化算法，通过进化操作（如选择、交叉和变异）来寻找问题的最优解。

我们将遗传算法应用于n皇后问题，并对不同规模的问题进行了求解。

在测试中，我们将问题规模设置为8、12和16。

结果表明，遗传算法能够在较短的时间内找到问题的一个解。

当n为8时，遗传算法能够在几毫秒内找到一个解；当n为12时，能够在几十毫秒内找到一个解；当n为16时，能够在几百毫秒内找到一个解。

相比之下，回溯算法在同样规模的问题上需要几秒钟甚至更长的时间。

3. 算法性能对比与分析通过对比回溯算法和启发式算法的性能，我们可以看到启发式算法在求解n皇后问题上具有明显的优势。

回溯算法的求解时间随问题规模呈指数级增长，而启发式算法的求解时间相对较短。

这是因为启发式算法通过优化搜索策略，能够更快地找到问题的解。

然而，启发式算法并非没有缺点。

算法分析与设计实验报告第三次附加实验附录：完整代码（回溯法）//回溯算法递归回溯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 皇后问题求解、题目1) 以Q-皇后问题为例，掌握回溯法的基本设计策略。

2) 掌握回溯法解决Q-皇后问题的算法并实现；二、算法设计思想回溯法是在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。

当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。

(其实回溯法就是对隐式图的深度优先搜索算法)。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

判断解是否可行的条件：1. 不在同一行或者同一列，x[i]!=x[j],i!=j2•不在一条斜线上，设两个皇后在(i,j)和(k,l)位置，卜k|!=|j-l|三、程序#include<stdio.h>#include<stdlib.h>int n,stack[100]; // 存当前路径int total; // 路径数int att(int,int);void make(int l) //递归搜索以stack[l]为初结点的所有路径｛int i,j; //子结点个数if (l==n+1){total=total+1; // 路径数+1 for(i=1;i<=n;i++)printf(" 输出皇后的列位置%-3d",stack[i]);// 输出第i 行皇后的列位置stack[i]}int att(int l,int i){}for (i=1;i<=n;i++){stack[l]=i; II算符i 作用于生成stack[l-1]产生子状态stack[l];if (!att(l,i))make(l+1);printf("\n");exit; II 回溯} II 再无算符可用，回溯int k;for (k=1;k<l;k++)if (abs(l-k)==abs(stack[k]-i)||i==stack[k])return 1;return 0;}int main(){}四、运行结果printf("N=");scanf("%d",&n);total=0; II 路径数初始化为0make(1); II从结点1出发，递归搜索所有的路径printf("%d\n",total);system("pause");return 0;六、心得体会在解决N皇后的时候一开始有点不止如何着手，因为这里有个N的不确定性，所以选择简单少量的情况进行具体考虑显得相对容易了许多，还有一个值得注意的问题就是如何判断要不要重新开始搜索，并且在已经形成的简单模型基础上进行改进，使之也能满足后面较复杂情况。

⼋皇后以及N皇后问题分析⼋皇后是⼀个经典问题，在8*8的棋盘上放置8个皇后，每⼀⾏不能互相攻击。

因此拓展出 N皇后问题。

下⾯慢慢了解解决这些问题的⽅法：回溯法：回溯算法也叫试探法，它是⼀种系统地搜索问题的解的⽅法。

回溯算法的基本思想是：从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。

在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满⾜某种要求的可能或最优的情况，从⽽得到整个问题的解。

回溯算法就是解决这种问题的“通⽤算法”，有“万能算法”之称。

N皇后问题在N增⼤时就是这样⼀个解空间很⼤的问题，所以⽐较适合⽤这种⽅法求解。

这也是N皇后问题的传统解法，很经典。

算法描述：1. 算法开始，清空棋盘。

当前⾏设为第⼀⾏，当前列设为第⼀列。

2. 在当前⾏，当前列的判断放置皇后是否安全，若不安全，则跳到第四步。

3. 在当前位置上满⾜条件的情况： 在当前位置放⼀个皇后，若当前⾏是最后⼀⾏，记录⼀个解； 若当前⾏不是最后⼀⾏，当前⾏设为下⼀⾏，当前列设为当前⾏的第⼀个待测位置； 若当前⾏是最后⼀⾏，当前列不是最后⼀列，当前列设为下⼀列； 若当前⾏是最后⼀⾏，当前列是最后⼀列，回溯，即清空当前⾏以及以下各⾏的棋盘，然后当前⾏设为上⼀⾏，当前列设为当前⾏的下⼀个待测位置； 以上返回第⼆步。

4.在当前位置上不满⾜条件： 若当前列不是最后⼀列，当前列设为下⼀列，返回到第⼆步； 若当前列是最后⼀列，回溯，即，若当前⾏已经是第⼀⾏了，算法退出，否则，清空当前⾏以及以下各⾏的棋盘，然后，当前⾏设为上⼀⾏，当前列设为当前⾏的下⼀个待测位置，返回第⼆步。

如何判断是否安全：把棋盘存储为⼀个N维数组a[N]，数组中第i个元素的值代表第i⾏的皇后位置，这样便可以把问题的空间规模压缩为⼀维O(N)，在判断是否冲突时也很简单， ⾸先每⾏只有⼀个皇后，且在数组中只占据⼀个元素的位置，⾏冲突就不存在了， 其次是列冲突，判断⼀下是否有a[i]与当前要放置皇后的列j相等即可。

实验报告4回溯算法实验4回溯算法解决N皇后问题一、实验目的1）掌握回溯算法的实现原理，生成树的建立以及限界函数的实现；2）利用回溯算法解决N皇后问题；二、实验内容回溯算法解决N皇后问题。

三、算法设计1）编写限界函数bool PLACE(int k,int x[])，用以确定在k列上能否放置皇后；2）编写void NQUEENS(int n)函数用以摆放N个皇后；3）编写主函数，控制输入的皇后数目；4）改进和检验程序。

四、程序代码//回溯算法解决N皇后问题的c++程序#include<math.h>#include<iostream>using namespace std;int count=0; //皇后摆放的可能性bool PLACE(int k,int x[]);//限界函数void NQUEENS(int n);//摆放皇后int main(){}int queen;cout<<"先生（女士）请您输入皇后的总数，谢谢！:"<<endl;cin>>queen;NQUEENS(queen);cout<<"所有可能均摆放完毕,谢谢操作"<<endl;return 0;void NQUEENS(int n){/*此过程使用回溯算法求出在一个n*n棋盘上放置n个皇后，使其即不同行，也不同列，也不在同一斜角线上*/int k, *x=new int[n];//存放皇后所在的行与列x[0]=0;k=0;while (k>=0&&k<n){ //对所有的行执行以下语句x[k]=x[k]+1; //移到下一列while(x[k]<=n&&(!PLACE(k,x))){ //此处能放置一个皇后吗?}if( x[k]<=n ) { //找到一个位置if( k==n-1 ){ //是一个完整的解吗cout<<"第"<<++count<<"排法是："<<endl;for(int i=0;i<n;i++)//打印皇后的排列{}cout<<"\n";for (int j=0;j<n;j++){}cout<<"\n";if (x[i] == j+1){}else{}cout<<". ";cout<<"*";x[k]=x[k]+1; //移到下一列}}}}else { k=k+1; x[k]=0;} //移向下一行else k=k-1; //回溯bool PLACE(int k,int x[]){/*如果一个皇后能放在第k行和x(k)列，返回ture;否则返回false。

实验报告一、实验名称：回溯法求解‎N皇后问题‎（Java实‎现）二、学习知识：回溯法：也称为试探‎法，它并不考虑‎问题规模的‎大小，而是从问题‎的最明显的‎最小规模开‎始逐步求解‎出可能的答‎案，并以此慢慢‎地扩大问题‎规模，迭代地逼近‎最终问题的‎解。

这种迭代类‎似于穷举并‎且是试探性‎的，因为当目前‎的可能答案‎被测试出不‎可能可以获‎得最终解时‎，则撤销当前‎的这一步求‎解过程，回溯到上一‎步寻找其他‎求解路径。

为了能够撤‎销当前的求‎解过程，必须保存上‎一步以来的‎求解路径，这一点相当‎重要。

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

深度优先遍‎历的典型案‎例。

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

2、需要解决的‎问题：如何表示一‎个N * N 方格棋盘能‎够更有效？怎样测试当‎前所走的试‎探路径是否‎符合要求？这两个问题‎都需要考虑‎到使用怎样‎的数据结构‎，使用恰当的‎数据结构有‎利于简化编‎程求解问题‎的难度。

3、我们使用以‎下的数据结‎构：int colum‎n[col] = row 表示第 col 列的第 row 行放置一个‎皇后boole‎an rowEx‎i sts[i] = true 表示第 i 行有皇后boole‎an a[i] = true 表示右高左‎低的第 i 条斜线有皇‎后（按→↓顺序从1~ 2*N -1 依次编号）boole‎an b[i] = true 表示左高右‎低的第 i 条斜线有皇‎后（按→↑顺序从1~ 2*N -1 依次编号）五、算法实现对应这个数‎据结构的算‎法实现如下‎：1.**2. * 回溯法求解‎N 皇后问题3. * @autho‎r haoll‎o yin4. */5.publi‎c class‎N_Que‎e ns {6.7.// 皇后的个数‎8. priva‎t e int queen‎s Num = 4;9.10.// colum‎n[i] = j表示第 i 列的第 j 行放置一个‎皇后11. priva‎t e int[] queen‎s = new int[queen‎s Num + 1];12.13.// rowEx‎i sts[i] = true 表示第 i 行有皇后14. priva‎t e boole‎a n[] rowEx‎i sts = new boole‎a n[queen‎sNum + 1];15.16.// a[i] = true 表示右高左‎低的第 i 条斜线有皇‎后17. priva‎t e boole‎a n[] a = new boole‎a n[queen‎s Num * 2];18.19.// b[i] = true 表示左高右‎低的第 i 条斜线有皇‎后20. priva‎t e boole‎a n[] b = new boole‎a n[queen‎s Num * 2];21.22.// 初始化变量‎23. priva‎t e void init() {24. for (int i = 0; i < queen‎s Num + 1; i++) {25. rowEx‎i sts[i] = false‎;26. }27.28. for(int i = 0; i < queen‎s Num * 2; i++) {29. a[i] = b[i] = false‎;30. }31. }32.33.// 判断该位置‎是否已经存‎在一个皇后‎,存在则返回‎true34. priva‎t e boole‎a n isExi‎s ts(int row, int col) {35. retur‎n (rowEx‎i sts[row] || a[row + col - 1]|| b[queen‎s Num + col - row]);36. }37.38.// 主方法：测试放置皇‎后39. publi‎c void testi‎n g(int colum‎n) {40.41.// 遍历每一行‎42. for (int row = 1; row < queen‎s Num + 1; row++) {43.// 如果第 row 行第 colum‎n列可以放置‎皇后44. if (!isExi‎s ts(row, colum‎n)) {45.// 设置第 row 行第 colum‎n列有皇后46. queen‎s[colum‎n] = row;47.// 设置以第 row 行第 colum‎n列为交叉点‎的斜线不可‎放置皇后48. rowEx‎i sts[row] = a[row + colum‎n - 1] = b[queen‎s Num + colum‎n - row] = true;49.50.// 全部尝试过‎，打印51. if(colum‎n == queen‎s Num) {52. for(int col = 1; col <= queen‎s Num; col++) {53. Syste‎m.out.print‎("("+col +"," + queen‎s[col] + ") ");54. }55. Syste‎m.out.print‎l n();56. }else {57.// 放置下一列‎的皇后58. testi‎n g(colum‎n + 1);59. }60.// 撤销上一步‎所放置的皇‎后，即回溯61. rowEx‎i sts[row] = a[row + colum‎n - 1] = b[queen‎s Num + colum‎n - row] = false‎;62. }63. }64. }65.66.//测试67. publi‎c stati‎c void main(Strin‎g[] args) {68. N_Que‎e ns queen‎= new N_Que‎e ns();69. queen‎.init();70.// 从第 1 列开始求解‎71. queen‎.testi‎n g(1);72. }73.}六、运行结果当N = 8 时，求解结果如‎下（注：横坐标为列数，纵坐标为行数）：(1,1) (2,5) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)1.(1,1) (2,6) (3,8) (4,3) (5,7) (6,4) (7,2) (8,5)2.(1,1) (2,7) (3,4) (4,6) (5,8) (6,2) (7,5) (8,3)3.... ...4.... ...5.(1,8) (2,2) (3,4) (4,1) (5,7) (6,5) (7,3) (8,6)6.(1,8) (2,2) (3,5) (4,3) (5,1) (6,7) (7,4) (8,6)7.(1,8) (2,3) (3,1) (4,6) (5,2) (6,5) (7,7) (8,4)8.(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)当N = 4 时，求解结果如‎下：1.(1,2) (2,4) (3,1) (4,3)2.(1,3) (2,1) (3,4) (4,2)七、实验小结：1、根据问题选‎择恰当的数‎据结构非常‎重要，就像上面 a 、b 标志数组来‎表示每一条‎斜线的编号‎顺序以及方‎向都相当重‎要。

回溯法解决N皇后问题C语⾔问题描述：⼋皇后问题是⼀个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置⼋个皇后，使得任何⼀个皇后都⽆法直接吃掉其他的皇后？为了达到此⽬的，任两个皇后都不能处于同⼀条横⾏、纵⾏或斜线上。

回溯法：回溯法⼜称试探法。

回溯法的基本做法是深度优先搜索。

即从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。

源代码：#include<stdio.h>#include<math.h>int x[9]={0};bool PLACE(int k)//检测第k个皇后能否放进棋盘{int i=1;while(i<k){if(x[i]==x[k]||fabs(x[i]-x[k])==fabs(i-k))return false;i++;}return true;}void NQUEENS(int n){int i,k=1; //k为当前⾏号x[1]=0;//x[k]为第k⾏皇后所放的列号while(k>0){x[k]++;while(x[k]<=n&&!PLACE(k))//该⾏不符合，则放⼊下⼀⾏x[k]++;if(x[k]<=n){if(k==n)//输出x[]{for(i=1;i<=n;i++)printf("x[%d]:%d ",i,x[i]);printf("\n");}else//判断下⼀⾏{k++; x[k]=0;}}else k--;//没找到，则回溯}return ;}int main(){NQUEENS(8);return0;}。

n皇后实验报告n皇后实验报告引言：n皇后问题是一个经典的数学问题，旨在找到在一个n×n的棋盘上放置n个皇后，使得它们互不攻击。

这个问题涉及到了组合数学、图论和计算机算法等多个领域，具有一定的难度和挑战性。

本实验旨在通过不同的算法和策略来解决n皇后问题，并对它们的效率和性能进行评估。

实验一：暴力法暴力法是最简单直接的解决方法之一。

它通过穷举法遍历所有可能的皇后放置方式，并检查是否满足条件。

具体步骤如下：1. 生成一个空的n×n棋盘。

2. 从第一行开始，依次尝试将皇后放置在每个格子上。

3. 如果当前格子可以放置皇后，则继续下一行；否则，回溯到上一行，重新选择一个可行的格子。

4. 当所有行都放置了皇后时，找到了一个解，记录下来。

5. 继续尝试下一个可能的放置方式，直到遍历完所有情况。

实验结果显示，暴力法在小规模问题上表现良好，但在n较大时，其时间复杂度呈指数级增长，运行时间非常长。

实验二：回溯法回溯法是一种优化的解决方法，它通过剪枝操作来减少不必要的搜索。

具体步骤如下：1. 生成一个空的n×n棋盘。

2. 从第一行开始，依次尝试将皇后放置在每个格子上。

3. 如果当前格子可以放置皇后，则继续下一行；否则，回溯到上一行，重新选择一个可行的格子。

4. 当所有行都放置了皇后时，找到了一个解，记录下来。

5. 在每次尝试放置皇后时，通过检查当前格子所在的行、列和对角线上是否已经有皇后，来判断是否满足条件。

6. 在每次回溯时，可以通过剪枝操作来减少搜索的空间。

实验结果显示，回溯法相较于暴力法有了一定的提升，但在n较大时，仍然存在一定的时间复杂度问题。

实验三：优化算法为了进一步提高解决n皇后问题的效率，我们尝试了一些优化算法。

其中，一种比较常见的优化算法是基于位运算的方法。

1. 生成一个空的n×n棋盘。

2. 使用一个n位的二进制数来表示每一行上的皇后位置，其中1表示有皇后，0表示没有皇后。

n皇后问题是一种经典的搜索问题，它的目标是在n*n的棋盘上放置n个皇后，使得这n 个皇后互不攻击（不在同一行、同一列、同一对角线上）。

求解n皇后问题的概率回溯复合算法是一种搜索算法，它通过在回溯过程中加入概率元素，来提高求解n皇后问题的效率。

具体来说，该算法的基本思路是：
初始化：将棋盘初始化为一个n*n的空棋盘，并设置一个计数器count，用于记录已经放置的皇后的数量。

回溯：从第0行开始，依次枚举每一行的每一列，判断是否可以在该位置放置皇后。

如果可以，就在该位置放置皇后，并将计数器count加1。

如果不可以，就跳过该位置，继续枚举下一列。

概率元素：在枚举每一列时，随机生成一个概率值p（0<=p<=1）。

如果p大于0.5，则在该位置放置皇后；否则跳过该位置，继续枚举下一列。

这样，在回溯过程中加入了一定的随机性，使得算法具有一定的概率元素。

终止条件：如果count的值等于n，则说明已经成功放置了n个皇后，可以终止算法。

否则，继续执行下一行的枚举过程。

复合：在每一行枚举完所有列之后，需要将已经放置的皇后撤销，并将计数器count减1，然后回到上一行，继续枚举下一列。

这样，在回溯的过程中，算法会不断地撤销和放置皇后，从而实现复合的效果。

总之，求解n皇后问题的概率回溯复合算法是一种结合了回溯和概率元素的搜索算法，可以有效地提高求解n皇后问题的效率。

实验四 n后问题一．实验目的1. 了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。

2. 运用迭代的方法实现n皇后问题，求解得到皇后不相互攻击的一个解二．实验内容基本思路：用n元组x[1:n]表示n后问题的解，其中x[i]表示第i个皇后放在棋盘的第i 行的第x[i]列。

抽象约束条件得到能放置一个皇后的约束条件：(1)x[i]!=x[k];(2)abs(x[i]-x[k])!=abs(i-k)。

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

在回溯法中，递归函数Backtrack(1)实现对整个解空间的回溯搜索。

Backtrack(i)搜索解空间的第i层子树。

类Queen 的数据成员记录解空间的节点信息，以减少传给Backtrack函数的参数。

sum记录当前已找到的可行方案数。

运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

三．实验结果四.源代码：#include<iostream>#include<stdlib.h>using namespace std;class Queen{friend int nQueen(int);private:bool Place(int k);void Backtract(int t);int n,*x;long sum; //可行方案数};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::Backtract(int t){if (t>n){sum++;cout<<"第"<<sum<<"种方法：";for(int i=1;i<=n;i++)cout<<x[i]<<" ";cout<<endl;}else{for(int i=1;i<=n;i++){x[t]=i;if(Place(t)) Backtract(t+1);}}}int nQueen(int n){Queen X;X.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.Backtract(1);delete []p;return X.sum;}void main(){int n,m;cout<<"请输入皇后个数:";cin>>n;m=nQueen(n);cout<<endl;cout<<"有"<<m<<"种可行方法"<<endl;system("pause");}。

回溯法之N皇后问题回溯法之N皇后问题1. 问题描述在n*n格的棋盘上放置彼此不受攻击的n个皇后。

按照国际象棋的规则，皇后可以攻击与之在同⼀⾏或同⼀列或同⼀斜线上的旗⼦。

n后问题等价于在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同⼀⾏或同⼀列或同⼀斜线上。

2. 问题分析（以n=4皇后问题为例）有俩种解法，第⼀种采⽤解空间为N(4)叉树的解法、第⼆种是采⽤解空间为排列数的解法。

2.1. N(4)叉树的解法每个皇后在⼀⾏上有四个可选位置。

即每个⾮叶结点有4个⼦节点，4叉树如下：解向量：(x1,x2,x3,......,x n)显约束：任意俩皇后不同⾏。

隐约束：(1) 不同列：x i ≠ x j (2) 不处于同⼀正反对⾓线：|i - j| ≠ |x i - x j|核⼼代码：// 剪枝函数，排除同列和同⼀对⾓线的分⽀int place1(int k) {for (int j = 1; j < k; j++)if (abs(k - j) == abs(x[j] - x[k]) || x[j] == x[k])return 0;return 1;}// t > n代表当前解已经求出，将总数+1// 利⽤循环遍历节点的n叉，同时判断分叉是否符合条件// 符合条件的分叉继续遍历下去void BackTrack1(int t) {if (t > n)sum++;elsefor (int i = 1; i <= n; i++) {x[t] = i;if (place1(t))BackTrack1(t + 1);}}2.2 排列数的解法解向量：(x1,x2,x3,......,x n)显约束：任意俩皇后不同⾏、不同列。

x1,x2,x3,......,x n是1,2,3.......n排列隐约束：不处于同⼀正反对⾓线：|i - j| ≠ |x i - x j|核⼼代码：// 交换俩⾏皇后的位置// 实现切换排列数的分⽀作⽤void swap(int i, int j) {int tmp = x[i];x[i] = x[j];x[j] = tmp;}// 剪枝函数，排除在同⼀对⾓线上的情况int place2(int k) {for (int j = 1; j < k; j++)if (abs(k - j) == abs(x[j] - x[k]))return 0;return 1;}// t > n时表⽰当前排列符合条件，总数 + 1// 利⽤for循环，和swap函数，将节点对应的所有排列遍历⼀次// 同时采⽤剪枝函数，减去错误的分⽀// 对正确的分⽀继续求解下去// 最后递归求解结束后，再次调⽤swap函数将状态返回到原本的节点状态void BackTrack2(int t) {if (t > n) sum++;elsefor (int i = t; i <= n; i++) {swap(t, i);if (place2(t))BackTrack2(t + 1);swap(t ,i);}}3. 完整代码/*** 回溯法求解n皇后问题* 使⽤x解向量，x1,x2,x3分别表⽰在1,2,3⾏上皇后的列号**/#include <stdio.h>#include <stdlib.h>#define MAX 4/*** n 皇后个数* x 当前解* sum**/int n = MAX;int x[MAX + 1];long sum = 0;// 剪枝函数，排除同列和同⼀对⾓线的分⽀int place1(int k) {for (int j = 1; j < k; j++)if (abs(k - j) == abs(x[j] - x[k]) || x[j] == x[k])return 0;return 1;}// t > n代表当前解已经求出，将总数+1// 利⽤循环遍历节点的n叉，同时判断分叉是否符合条件// 符合条件的分叉继续遍历下去void BackTrack1(int t) {if (t > n)sum++;elsefor (int i = 1; i <= n; i++) {x[t] = i;if (place1(t))BackTrack1(t + 1);}}// 交换俩⾏皇后的位置// 实现切换排列数的分⽀作⽤void swap(int i, int j) {int tmp = x[i];x[i] = x[j];x[j] = tmp;}// 剪枝函数，排除在同⼀对⾓线上的情况int place2(int k) {for (int j = 1; j < k; j++)if (abs(k - j) == abs(x[j] - x[k]))return 0;return 1;}// t > n时表⽰当前排列符合条件，总数 + 1// 利⽤for循环，和swap函数，将节点对应的所有排列遍历⼀次// 同时采⽤剪枝函数，减去错误的分⽀// 对正确的分⽀继续求解下去// 最后递归求解结束后，再次调⽤swap函数将状态返回到原本的节点状态void BackTrack2(int t) {if (t > n) sum++;elsefor (int i = t; i <= n; i++) {swap(t, i);if (place2(t))BackTrack2(t + 1);swap(t ,i);}}void main() {for (int i = 0; i <= n; i++)x[i] = i;BackTrack1(1);printf("%d\n", sum);for (int i = 0; i <= n; i++)x[i] = i;sum = 0;BackTrack2(1);printf("%d\n", sum);system("pause");}。

n 皇 后 问 题N 皇后问题，是一个古老而着名的问题，是回溯算法的典型例题：在N*N 格的格子上摆放N 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？ 1、定义问题的解空间首先以八皇后为例，可以用一棵树表示8皇后问题的解空间。

由于8皇后问题的解空间为8!种排列，因此我们将要构造的这棵树实际上是一棵排列树。

2、确定解空间树的结构给棋盘上的行和列从1到8编号，同时也给皇后从1到8编号。

由于每一个皇后应放在不同的行上，不失一般性，假设皇后i 放在第i 行上，因此8皇后问题可以表示成8元组(x 1， x 2， …， x 8)， 其中xi (i =1， 2， …， 8)表示皇后i 所放置的列号。

这种表示法的显式约束条件是S i ={1， 2， 3， 4， 5， 6， 7， 8}，i =1， 2， …， 8。

在这种情况下， 解空间为88个8元组组成，而隐式约束条件是没有两个xi 相同(即所有皇后必须在不同列上)，且满足不存在两个皇后在同一条对角线上。

加上隐式约束条件，问题的解空间可进一步减小。

此时，解空间大小为8!，因为所有解都是8元组的一个置换。

图5-7表示了8皇后问题的一个解。

图5-7 8皇后问题的一个解为了简单起见，图5-8只给出了n =4时问题的一种可能树结构。

QQQQQQQQ8765432112345678图5-8 4皇后问题解空间的树结构在实际中，并不需要生成问题的整个状态空间。

通过使用限界函数来删除那些还没有生成其所有子结点的活结点。

如果用(x1，x2，…，x i)表示到当前E结点的路径，那么xi+1就是这样的一些结点，它使得(x1，x2，…，x i，x i+1)没有两个皇后处于相互攻击的棋盘格局。

在4皇后问题中，惟一开始结点为根结点1，路径为( )。

开始结点既是一个活结点，又是一个E结点，它按照深度优先的方式生成一个新结点2，此时路径为(1)，这个新结点2变成一个活结点和新的E结点，原来的E结点1仍然是一个活结点。

N皇后问题—回溯算法经典例题题⽬描述: N 皇后是回溯算法经典问题之⼀。

问题如下：请在⼀个 n×n 的正⽅形盘⾯上布置 n 名皇后，因为每⼀名皇后都可以⾃上下左右斜⽅向攻击，所以需保证每⼀⾏、每⼀列和每⼀条斜线上都只有⼀名皇后。

题⽬分析： 在 N 皇后问题中，回溯算法思路是每⼀次只布置⼀个皇后，如果盘⾯可⾏，就继续布置下⼀个皇后。

⼀旦盘⾯陷⼊死局，就返回⼀步，调整上⼀个皇后的位置。

重复以上步骤，如果解存在，我们⼀定能够找到它。

可以看到，我们在重复“前进—后退—前进—后退”这⼀过程。

问题是，我们不知道⼀共需要重复这个过程多少次，也不能提前知道 n 是多少，更不知道每⼀次后退时需要后退⼏⾏，因此我们不能利⽤ for 循环和 while 循环来实现这个算法。

因此我们需要利⽤递归来实现代码结构。

逻辑如下：当⽅法布置完当前⾏的皇后，就让⽅法调⽤⾃⼰去布置下⼀⾏的皇后。

当盘⾯变成绝境的时候，就从当前⽅法跳出来，返回到上⼀⾏，换掉上⼀⾏的皇后再继续。

我们定义 NQueens(n) ⽅法，它负责输出所有成⽴的 n×n 盘⾯。

其中 1 代表皇后，0 代表空格。

代码：def NQueens(n): #输出所有成⽴的n·n盘⾯cols = [0 for _ in range(n)] #每⼀⾏皇后的纵坐标res = [] #结果列表def checkBoard(rowIndex): #检查盘⾯是否成⽴,rowIndex是当前⾏数for i in range(rowIndex):if cols[i]==cols[rowIndex]: #检查竖线return Falseif abs(cols[i]-cols[rowIndex]) == rowIndex-i: #检查斜线return Falsereturn Truedef helper(rowIndex): #布置第rowIndex⾏到最后⼀⾏的皇后if rowIndex==n: #边界条件board = [[0 for _ in range(n)] for _ in range(n)]for i in range(n):board[i][cols[i]] = 1res.append(board) #把当前盘⾯加⼊结果列表return#返回for i in range(n): #依次尝试当前⾏的空格cols[rowIndex] = iif checkBoard(rowIndex): #检查当前盘⾯helper(rowIndex+1) #进⼊下⼀⾏helper(0) #从第1⾏开始return resprint(NQueens(4))代码分析： 在 NQueens() ⽅法中，我们会定义 helper(x) ⽅法帮助实现递归结构。

n皇后问题回溯法递归实现解释说明1. 引言1.1 概述本文主要讨论的是n皇后问题及其解决方法。

n皇后问题是一个经典的数学问题，旨在找到如何将n个皇后放置在一个nxn的棋盘上，使得所有皇后彼此之间不会互相攻击。

这个问题具有一定难度，但可以通过回溯法和递归实现来有效解决。

1.2 文章结构本文共分为五个部分：引言、n皇后问题、回溯法解决n皇后问题的步骤、递归实现n皇后问题解决方案的详细步骤与算法思路以及结论。

引言部分主要对文章内容进行概述和介绍，并给出本文的结构安排。

1.3 目的本文旨在通过对n皇后问题的深入研究和探讨，介绍回溯法和递归实现在解决该问题中的应用方法。

通过详细说明算法步骤和思路，帮助读者理解如何使用回溯法和递归实现有效地解决n皇后问题，并对两种方法进行评价与讨论。

同时，还展望了可能的未来研究方向，为读者提供更多思考和拓展的空间。

本文旨在为对n皇后问题感兴趣的读者提供有益的参考和指导。

（文章引言部分完）2. n皇后问题:2.1 问题描述:n皇后问题是一个经典的组合问题，其中n表示棋盘上的行数和列数。

在一个nxn的棋盘上，要放置n个皇后，并且要求任意两个皇后之间不得互相攻击（即不能处于同一行、同一列或同一对角线上）。

这是一个相当困难的问题，因为随着n的增大，可能的解法呈指数增长。

2.2 解决方法介绍:为了解决n皇后问题，可以使用回溯法和递归实现的组合算法。

回溯法是一种通过尝试所有可能情况来找到解决方案的方法。

它通过逐步构建解，并在遇到无效解时进行回溯。

而递归是把大规模的问题分解成相似但规模更小的子问题来求解。

2.3 回溯法和递归实现的关系:在解决n皇后问题中，回溯法是主要思想，而递归则用于辅助实现回溯过程。

在每一步尝试放置一个皇后时，会先判断该位置是否与之前已经放置好的皇后冲突。

如果没有冲突，则继续考虑下一个位置，并以递归的方式调用自身。

如果找到一个有效解时，会结束递归并返回结果。

如果所有位置都无法放置皇后，则回溯至上一步进行下一种尝试。