n皇后 实验报告

实验[4][实验题目]:n皇后专业：信息与计算数学学号：姓名：日期：1.实验目的学习递归算法的算法思想，并将其运用在计算机程序中。

2 实验内容首先学习递归算法的思想然后运用递归算法的思想进行程序编译3.算法设计要解决N皇后问题，其实就是要解决好怎么放置这n个皇后，每一个皇后与前面的所有皇后不能在同一行、同一列、同一对角线，在这里我们可以以行优先，就是说皇后的行号按顺序递增，只考虑第i个皇后放置在第i行的哪一列，所以在放置第i个皇后的时候，可以从第1列判断起，如果可以放置在第1个位置，则跳到下一行放置下一个皇后。

如果不能，则跳到下一列...直到最后一列，如果最后一列也不能放置，则说明此时放置方法出错，则回到上一个皇后向之前放置的下一列重新放置。

此即是回溯法的精髓所在。

当第n个皇后放置成功后，即得到一个可行解，此时再回到上一个皇后重新放置寻找下一个可行解...如此后，即可找出一个n皇后问题的所有可行解。

4.程序代码#include <iostream>using namespace std;int p[12][12];//初始化矩阵(矩阵太大回溯法的效率很低,所以该题的数据很小)int result;int n;//矩阵大小void init(int n)//初始化矩阵{for(int i=0;i<n;i++){for(int j=0;j<n;j++)p[i][j]=0;}result=0;}bool issafe(int row,int col)//判断该位置能否放皇后{for(int i=0;i<row;i++){for(int j=0;j<n;j++){if(p[i][j]==1){//判断同行,同列,对角线上是否有皇后if(i==row||j==col||(j-i)==(col-row)||(j+i)==(col+row))return false;}}}return true;}void putqueen(int x)//入皇后{for(int y=0;y<n;y++)//遍历该行每个位置{if(issafe(x,y))//如果可以{p[x][y]=1;//则放皇后if(x<n-1)putqueen(x+1);//如果未到最后一行,在下一行放皇后elseresult++;//否则返回,结果加1}{for(int k=0;k<n;k++)//该步骤很重要,拿走该行上的皇后p[x][k]=0;}}}int main(){cout<<"请输入皇后数："<<endl;while(cin>>n){init(n);putqueen(0);cout<<n<<"皇后有"<<result<<"解"<<endl;}return 0;}5 运行结果6 结果分析由于100皇后的解太庞大计算机无法快速的计算出答案，故选择了8皇后进行计算，其结果与其他同学程序的结果进行对后数值大小上一致。

一、实验设计方案1、实验内容与目的（简单介绍实验内容，说明实验目的）实验目的：要求在一个n*n的棋盘上放置n个皇后，要求放置的n个皇后不会互相吃掉；皇后棋子可以吃掉它所在的那一行、那一列，以及那两条对角线上的任何棋子。

实验内容：你的具体选择（要详细）通过input.txt文件输入一个数字n，求出n皇后问题，并将结果输出到output.txt文件——————————————————————————————————————2、实验准备工作（阐述解决问题所涉及的算法思想，至少要画一个算法流程图来说明）本实验采用递归算法：递归算法中，首先定义三个bool型变量，分别表示行，对角线，反对角线是否有皇后，若有，则用true表示出来。

用循环，依次求出满足要求的点，如果满足，则放置皇后，然后循环查找能放置下一个皇后的点。

当放置的皇后数目等于行列数时，就调用函数将结果输出。

——————————————————————————————————————二、实验步骤、测试与结果分析1、源程序的设计（在此附上源程序（cpp文件）清单）queen.h 文件：#ifndef __QUEEN_H__#define __QUEEN_H__#include<iostream>#include<fstream>//文件流using namespace std;class queen//定义一个queen类{private:int n;//需要解决的n皇后问题bool *row;//行是否有皇后bool *diag;//对角线是否有皇后bool *backdiag;//反对角线是否有皇后int *x;//皇后问题的解void backtracking(int c);//用于递归求解的函数void output();//文件输出函数public:queen();//构造函数virtual~queen();//析构函数void run()//用于执行递归求解，并计算出所有皇后问题的解{backtracking(1);}};queen::queen(){ifstream in("input.txt",ios::in);if(!in)//当打开失败时{cout<<"打开文件input.txt失败！"<<endl;exit(1);}int num;in>>num;//再文本文件中读取一个数字numn=num;//令n=numrow=new bool[n+1];//分配行所占空间diag=new bool[2*n];//分配对角线所占空间backdiag=new bool[2*n];//分配反对角线所占空间x=new int[n+1];//解所占空间int i;for(i=1;i<=n;i++) row[i]=false;//表示所有行都没有放皇后for(i=1;i<2*n;i++) diag[i]=false;//所有对角线没有放皇后for(i=1;i<2*n;i++) backdiag[i]=false;//所有反对角线没有放皇后in.close();//关闭文件}void queen::backtracking(int c){if(c>n) output();//当放置的皇后数等于行数时，输出结果else{for(int r=1;r<=n;r++)//行循环{if(!row[r] && !diag[n-c+r] && !backdiag[r+c-1])//当（r，c）所在行，对角线，反对角线都没有放置皇后时{row[r]=diag[n-c+r]=backdiag[r+c-1]=true;//这点合符要求，在此处放置皇后x[c]=r;//解为（r，c）backtracking(c+1);//c加一，继续放置下一个皇后row[r]=diag[n-c+r]=backdiag[r+c-1]=false;//清空操作}}}}void queen::output(){static int num=0;//表示当前已经求得的解个数ofstream outfile("output.txt",ios::app);//不写ios::app默认是以ios::out打开，只能得到最后一个解。

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皇后问题院校：云南大学信息学院姓名：学号：1. 课题综述1. 1课题的来源及意义八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。

所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。

到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上,运用所学计算机知识来试着解决这个问题.1. 2 面对的问题N皇后问题等于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

即规定每一列放一个皇后，不会造成列上的冲突；当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i 为下标的标记置为被占领状态。

1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；2）用递归法解决问题。

2. 概要设计用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的变化表现出来。

主要思路以及思想是这样的：1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；对角线：对角线有两个方向。

在这我把这两条对角线称为：主对角线和从对角线。

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

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

算法设计与分析实验报告姓名：杨勇涛班级：计科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 皇后问题求解、题目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皇后实验报告n皇后实验报告引言：n皇后问题是一个经典的数学问题，其目标是在一个n×n的棋盘上放置n个皇后，使得它们互不攻击。

本实验旨在通过编程实现n皇后问题的解法，并对不同的算法进行性能分析。

实验方法：本实验采用Python语言编写程序，实现了两种常见的解法：回溯法和遗传算法。

回溯法是一种穷举搜索的方法，通过不断尝试每一种可能的放置方式，直到找到满足条件的解；而遗传算法则是通过模拟生物进化的过程，利用选择、交叉和变异等操作逐步优化解的质量。

实验结果：在实验中，我们分别测试了回溯法和遗传算法在不同规模的n皇后问题上的性能表现。

以下是实验结果的总结：1. 回溯法：- 对于规模较小的问题（n<10），回溯法可以在短时间内找到所有解，并输出结果。

- 随着问题规模的增大，回溯法的搜索时间呈指数级增长。

当n=15时，搜索时间已经超过10秒。

- 回溯法在解决大规模问题时，遇到了组合爆炸的问题，无法在合理的时间内得出结果。

2. 遗传算法：- 遗传算法对于规模较小的问题表现不如回溯法，因为其需要较长的时间来找到一个较优解。

- 随着问题规模的增大，遗传算法的性能逐渐超过回溯法。

当n=20时，遗传算法能够在合理的时间内找到一个较优解。

- 遗传算法在解决大规模问题时，相比回溯法有明显的优势，因为其搜索时间增长较慢。

实验讨论：通过对实验结果的分析，我们可以得出以下结论：- 回溯法适用于规模较小的n皇后问题，但在大规模问题上的性能不佳。

- 遗传算法在大规模问题上表现较好，但对于规模较小的问题需要更长的时间来找到较优解。

- 遗传算法的性能受到参数设置的影响，不同的选择、交叉和变异策略可能导致不同的结果。

结论：综上所述，回溯法和遗传算法都是解决n皇后问题的有效方法，但在不同规模的问题上有不同的性能表现。

在实际应用中，我们可以根据问题规模选择合适的算法来求解。

对于规模较小的问题，回溯法可以提供精确的解；而对于大规模问题，遗传算法能够在合理的时间内找到较优解。

N皇后——最⼩冲突算法⼀个相对⾼效的实现N皇后问题就不再叙述了，Google⼀下就知道了（这⾥我们讨论找出⼀个或⼏个解，不讨论找出全部解的⽅法）N皇后有⼀个解法是回溯法，这个可以解决，但是效率不是很⾼。

（不过这个⽅法可以找出所有解）结合随机⽅法会更快：随机初始化⼀部分皇后，使得她们互不冲突，然后再⽤回溯法，这通常快得多。

不过这个⽅法不能找到所有解，也不能保证⼀次找到解——如果第⼀次随机化找不到解，就要再次随机化+回溯。

本⽂讲⼀个从⼈⼯智能的⾓度解决该问题的算法——最⼩冲突算法，这个算法在《⼈⼯智能——⼀种现代⽅法》（第⼆版）第五章中出现简单地说，就是：（1）初始化N个皇后的⼀个放置，允许有冲突（2）考虑某⼀⾏的某个皇后，她可能与x个皇后冲突，然后看看将这个皇后移动到这⼀⾏的哪个空位能使得与其冲突的皇后个数最少，就移动到那⾥。

（也可以考虑列，是等价的）（3）不断执⾏（2），直到没有冲突为⽌这个算法也不能找到所有解，有可能也要多次初始化，因为有可能从某个初始状态开始，按照最⼩冲突准则⽆论怎么调整都达不到终⽌条件（即没有冲突）。

这⾥的最⼩冲突准则有点“贪⼼”的味道，⽽贪⼼算法常常达不到最优解。

（不过实际实现时发现1次初始化总是能得到解——当然这个没法证明，只是实验验证）上⾯的算法没有说明如何初始化，最简单的就是随便放，这⾥我们采⽤每⾏放⼀个，同时保证列号不重复的⼀种随机放法。

上⾯算法也没说明每次执⾏（2）应该处理哪⼀⾏，我们的做法是：从第⼀⾏开始直到最后⼀⾏，逐个处理，如果这样⼀轮下来没有终⽌，就再来⼀轮……直到终⽌。

计算每⾏最⼩冲突的位置是这个算法⽐较核⼼的⼀步，简单的想法就是对某个位置，遍历所有的皇后，看看与其中⼏个有冲突；对N个可能的位置都执⾏这⼀操作，这就是O(N^2)的复杂度，这样每⼀轮的调整就是O(N^3)，N超过1000就会⾮常慢了 ⼀个改进的想法是：既然每次只调整了⼀个皇后的位置，产⽣的影响并不⼤，可以记录每个皇后的冲突数，然后当某个皇后移动时，更新这个值。

n皇后问题递归算法c语言概述n皇后问题是一个经典的回溯算法问题，它要求在一个n×n的棋盘上放置n个皇后，使得它们互不攻击。

本文将使用递归算法来解决n皇后问题，并使用C语言进行实现。

问题描述在n×n的棋盘上放置n个皇后，使得它们不在同一行、同一列或同一斜线上。

其中，皇后的移动规则是可以横向、纵向、对角线方向上自由移动任意步数。

算法思路为了解决n皇后问题，我们可以采用递归的方式逐行放置皇后。

具体地，可以按照行优先的顺序，从第一行开始放置皇后，并逐行向下递归，直到放置了n个皇后，或者无法再放置皇后为止。

算法的关键在于如何判断当前位置是否可以放置皇后，即判断是否与已经放置的皇后位置冲突。

为了判断冲突，我们需要考虑以下几个方面：1.所有皇后不能在同一列：我们可以使用一个数组q ue en[]来记录每一行放置的皇后的列位置。

2.所有皇后不能在同一对角线上：我们可以使用两个数组up D ia g[]和d ow nD ia g[]来记录每一条对角线上是否已经存在皇后。

对于任意一个位置(i,j)，它所在的主对角线上的元素满足i-j的值相等，次对角线上的元素满足i+j的值相等。

在放置皇后时，我们可以逐个尝试每一列，然后检查当前位置是否与已经放置的皇后位置冲突，如果冲突则继续尝试下一列，直到找到一个合适的位置。

然后，继续递归放置下一行的皇后，直到放置了n个皇后或者无法再放置为止。

伪代码定义一个全局整型数组q ue en[]，用于记录每一行放置的皇后的列位置定义两个全局整型数组u pD ia g[]和do wn D ia g[]，用于记录每一条对角线上是否已经存在皇后P r oc ed ur en Qu ee ns(r ow):i f ro w=n://找到一个解P r in tS ol ut io n()r e tu rnf o rc ol fr om0t on-1:i f Ca nP la ce Qu ee n(r o w,co l):P l ac eQ ue en(r ow,co l)n Q ue en s(ro w+1)R e mo ve Qu ee n(ro w,c o l)P r oc ed ur eC an Pl ace Q ue en(r ow,c ol):i f qu ee n[co l]!=-1:r e tu rn fa ls ei f up Di ag[r ow-c ol+n-1]!=-1o rd ow nDi a g[ro w+co l]!=-1:r e tu rn fa ls er e tu rn tr ueP r oc ed ur eP la ce Que e n(ro w,co l):q u ee n[co l]=r owu p Di ag[r ow-c ol+n-1]=1d o wn Di ag[r ow+c ol]=1q u ee n[co l]=-1u p Di ag[r ow-c ol+n-1]=-1d o wn Di ag[r ow+c ol]=-1P r oc ed u r eP ri nt Sol u ti on():f o rr ow fr om0t on-1:f o rc ol fr om0t on-1:i f qu ee n[co l]=r ow:p r in t"Q"e l se:p r in t"*"p r in tn ew li nep r in tn ew li neC语言实现下面是使用C语言实现的n皇后问题递归算法的代码示例：#i nc lu de<s td io.h>#d ef in eN8i n tq ue en[N];//记录每一行放置的皇后的列位置i n tu pD ia g[2*N-1];//记录每一条对角线上是否已经存在皇后i n td ow nD ia g[2*N-1];//记录每一条对角线上是否已经存在皇后v o id nQ ue en s(in tro w);i n tc an Pl ac eQ ue en(i nt ro w,in tc ol);v o id pl ac eQ ue en(in t ro w,in tc ol);v o id pr in tS ol ut ion();i n tm ai n(){f o r(in ti=0;i<N;i++){q u ee n[i]=-1;}f o r(in ti=0;i<2*N-1;i++){u p Di ag[i]=-1;d o wn Di ag[i]=-1;}n Q ue en s(0);r e tu rn0;}v o id nQ ue en s(in tro w){i f(r ow==N){p r in tS ol ut io n();r e tu rn;}f o r(in tc ol=0;c ol<N;c ol++){ i f(c an Pl ac eQ ue en(r ow,c ol)){ p l ac eQ ue en(r ow,co l);n Q ue en s(ro w+1);r e mo ve Qu ee n(ro w,c o l);}}}i n tc an Pl ac eQ ue en(i nt r o w,in tc ol){i f(q ue en[c ol]!=-1){r e tu rn0;}i f(u pD ia g[ro w-col+N-1]!=-1||do wnD i ag[r ow+c ol]!=-1){ r e tu rn0;}r e tu rn1;}v o id pl ac eQ ue en(in t ro w,in tc ol){q u ee n[co l]=r ow;u p Di ag[r ow-c ol+N-1]=1;d o wn Di ag[r ow+c ol]=1;}v o id re mo ve Qu ee n(i n tr ow,i nt co l){q u ee n[co l]=-1;u p Di ag[r ow-c ol+N-1]=-1;d o wn Di ag[r ow+c ol]=-1;}v o id pr in tS ol ut ion(){f o r(in tr ow=0;r ow<N;r ow++){f o r(in tc ol=0;c ol<N;c ol++){i f(q ue en[c ol]==ro w){p r in tf("Q");}e ls e{p r in tf("*");}}p r in tf("\n");}p r in tf("\n");}总结本文使用C语言实现了n皇后问题的递归算法。

湖州师范学院实验报告课程名称：算法实验四：回溯算法一、实验目的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后问题分析只要不要在同一直线和斜线上就行。