回溯法实验(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后问题-回溯法问题描述： 在n*n的棋盘上放置彼此不受攻击的n个皇后。

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

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

算法设计： |i-k|=|j-l|成⽴，就说明2个皇后在同⼀条斜线上。

可以设计⼀个place函数，测试是否满⾜这个条件。

1 当i>n时，算法搜索⾄叶节点，得到⼀个新的n皇后互不攻击放置⽅案，当前已找到的可⾏⽅案sum加1. 2 当i<=n时，当前扩展结点Z是解空间中的内部结点。

该结点有x[i]=1,2,3....n共n个⼉⼦节点。

对当前扩展结点Z的每个⼉⼦节点，由place检察其可⾏性。

并以深度优先的⽅式递归地对可⾏⼦树，或剪去不可⾏⼦树。

算法描述：　#include <iostream>#include <cstdlib>using namespace std;class Queen{friend int nQueen(int);private:bool Place(int k);void Backtrack(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::Backtrack(int t){if(t>n)sum++;elsefor(int i=1;i<=n;i++){x[t] = i;if(Place(t))Backtrack(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.Backtrack(1);delete [] p;cout<<X.sum<<endl;return X.sum;}int main(){nQueen(4);nQueen(2);nQueen(3);return0;}执⾏结果：迭代回溯：数组x记录了解空间树中从根到当前扩展结点的路径，这些信息已包含了回溯法在回溯时所需要的信息。

回溯算法与八皇后问题(N皇后问题)1 问题描述八皇后问题是数据结构与算法这一门课中经典的一个问题。

下面再来看一下这个问题的描述。

八皇后问题说的是在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。

更通用的描述就是有没有可能在一张N*N的棋盘上安全地放N个皇后？2 回溯算法回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。

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

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

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

N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。

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

下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘：1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步3) 在当前位置上满足条件的情形：在当前位置放一个皇后，若当前行是最后一行，记录一个解；若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；若当前行是最后一行，当前列不是最后一列，当前列设为下一列；若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；以上返回到第2步4) 在当前位置上不满足条件的情形：若当前列不是最后一列，当前列设为下一列，返回到第2步;若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。

湖州师范学院实验报告课程名称：算法实验四：回溯算法一、实验目的1、理解回溯算法的概念，掌握回溯算法的基本要素。

2、掌握设计回溯算法的一般步骤，针对具体问题，能应用回溯算法求解。

二、实验内容1、问题描述1 ）n后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后。

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

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

2）0-1 背包问题需对容量为 c 的背包进行装载。

从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。

对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。

每种物品要么放进背包，要么丢弃。

2、数据输入：文件输入或键盘输入。

3、要求：1）完成上述两个问题，时间为2 次课。

2）独立完成实验及实验报告。

三、实验步骤1、理解方法思想和问题要求。

2、采用编程语言实现题目要求。

3、上机输入和调试自己所写的程序。

4、附程序主要代码：1.n后问题：#include<iostream>using namespace std;class Queen {friend int nQueen(int);private:bool Place(int k);void Backtrack(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::Backtrack(int t) {if (t > n) {for (int i = 1; i <= n; i++)cout << x[i] << " ";cout << endl;sum++;}else {for (int i = 1; i <= n; i++) {x[t] = i;if (Place(t)) Backtrack(t + 1);}}}int nQueen(int n) {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;}void main() {int n, set;cout << "请输入皇后个数："; cin >> n;cout << "可行方案所有解：" << endl;set = nQueen(n);cout << "可行方案数：" << set << endl;}2.0-1背包：#include <stdio.h>#include <conio.h>int n;//物品数量double c;//背包容量double v[100];//各个物品的价值double w[100];//各个物品的重量double cw = 0.0;//当前背包重量double cp = 0.0;//当前背包中物品价值double bestp = 0.0;//当前最优价值double perp[100];//单位物品价值排序后int order[100];//物品编号int put[100];//设置是否装入//按单位价值排序void knapsack(){int i,j;int temporder = 0;double temp = 0.0;for(i=1;i<=n;i++)perp[i]=v[i]/w[i];for(i=1;i<=n-1;i++){for(j=i+1;j<=n;j++)if(perp[i]<perp[j]) perp[],order[],sortv[],sortw[] {temp = perp[i];perp[i]=perp[i];perp[j]=temp;temporder=order[i]; order[i]=order[j]; order[j]=temporder; temp = v[i];v[i]=v[j];v[j]=temp;temp=w[i];w[i]=w[j];w[j]=temp;}}}//回溯函数void backtrack(int i){double bound(int i);if(i>n){bestp = cp;return;}if(cw+w[i]<=c){cw+=w[i];cp+=v[i];put[i]=1;backtrack(i+1);cw-=w[i];cp-=v[i];}if(bound(i+1)>bestp)//符合条件搜索右子数 backtrack(i+1);}//计算上界函数double bound(int i){double leftw= c-cw;double b = cp;while(i<=n&&w[i]<=leftw){leftw-=w[i];b+=v[i];i++;}if(i<=n)b+=v[i]/w[i]*leftw;return b;}int main(){int i;printf("请输入物品的数量和容量：");scanf("%d %lf",&n,&c);printf("请输入物品的重量和价值：");for(i=1;i<=n;i++){printf("第%d个物品的重量：",i);scanf("%lf",&w[i]);printf("价值是：");scanf("%lf",&v[i]);order[i]=i;}knapsack();backtrack(1);printf("最有价值为：%lf\n",bestp);printf("需要装入的物品编号是：");for(i=1;i<=n;i++){if(put[i]==1)printf("%d ",order[i]);}return 0;}5、实验结果：四、实验分析1、：n后问题分析只要不要在同一直线和斜线上就行。

实验报告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皇后问题实验时间：2013.12.3姓名：***班级：计科1101学号：**********一、实验内容及要求在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皇后有10个可行解五、源代码#include<stdio.h>static int n, sum=0;//可行解个数static int locate[20];int place(int k){//判断是否在一条线上并返回0,1for(int i=1;i<k;i++){if(locate[i] == locate[k] || (i+locate[i])==(locate[k]+k)||(locate[i]-i)==(locate[k]-k))return 0;}return 1;}void Back(int m){if(m>n){sum++;for(int i=1;i<=n;i++){for(int a=1;a<=n;a++){if(a<locate[i]||a>locate[i])printf(" * ");elseprintf(" \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 main(){printf("请输入皇后数量:");scanf("%d",&n);printf("\n(\2表示皇后，*表示棋盘)\n\n\n");Back(1);printf("%d个皇后共有以上%d种解法\n\n\n",n,sum);}六、实验心得回溯法有“通用解题法”之称，用它可以搜索问题的所有解。