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)为下标的标记置为被占领状态。

实验四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皇后问题就不再叙述了，Google⼀下就知道了（这⾥我们讨论找出⼀个或⼏个解，不讨论找出全部解的⽅法）N皇后有⼀个解法是回溯法，这个可以解决，但是效率不是很⾼。

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

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

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

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

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

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

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

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

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

实验报告一、实验名称：回溯法求解‎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皇后课程设计总结一、教学目标本课程的教学目标是使学生掌握n皇后问题的解法，理解其背后的数学原理和计算机科学思想。

知识目标包括理解n皇后问题的定义、解法和应用场景；技能目标包括能够使用适当的编程语言或工具解决n皇后问题；情感态度价值观目标包括培养学生的逻辑思维能力、创新意识和团队合作精神。

二、教学内容教学内容主要包括n皇后问题的定义和解法。

首先，介绍n皇后问题的背景和定义，让学生了解其意义和应用场景。

然后，讲解n皇后问题的解法，包括回溯法、遗传算法等，并通过实例让学生理解这些算法的原理和实现方式。

最后，通过实际案例分析，让学生了解n皇后问题在计算机科学中的应用。

三、教学方法为了激发学生的学习兴趣和主动性，将采用多种教学方法。

首先，通过讲授法，向学生传授n皇后问题的基本概念和解法。

然后，通过讨论法，让学生分组讨论并分享各自的解题思路和经验。

接着，通过案例分析法，让学生分析实际案例并了解n皇后问题的应用场景。

最后，通过实验法，让学生动手编程实现n皇后问题的解法，并进行调试和优化。

四、教学资源为了支持教学内容和教学方法的实施，将选择和准备适当的教学资源。

教材方面，选择《算法导论》等经典教材，介绍n皇后问题的基本概念和解法。

参考书方面，推荐学生阅读《计算机科学概论》等书籍，了解n皇后问题在计算机科学中的应用。

多媒体资料方面，制作PPT和教学视频，生动形象地展示n皇后问题的解法。

实验设备方面，准备计算机和编程环境，让学生能够动手编程实现n皇后问题的解法。

五、教学评估本课程的评估方式将包括平时表现、作业和考试三个部分。

平时表现主要评估学生的课堂参与度和团队合作能力，通过观察和记录学生在课堂上的表现进行评估。

作业主要评估学生的理解和应用能力，通过布置相关的编程练习和案例分析进行评估。

考试主要评估学生的综合运用能力，通过笔试和上机考试进行评估。

评估方式将力求客观、公正，全面反映学生的学习成果。

六、教学安排本课程的教学安排将共计32课时，每周2课时，共计16周完成。

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皇后问题实验报告1. 引言n皇后问题是一个经典的组合优化问题，旨在找到如何在一个n × n的棋盘上放置n个皇后，使得任意两个皇后不在同一行、同一列或同一对角线上。

这个问题可以通过回溯算法来解决。

在本实验报告中，我们将详细介绍n皇后问题，并提供一个实现回溯算法解决该问题的步骤。

2. 算法步骤以下是解决n皇后问题的步骤：2.1 初始化首先，我们需要定义一个n × n的棋盘，并初始化所有位置为空。

2.2 递归回溯接下来，我们使用递归回溯来找到合适的解决方案。

我们从第一行开始，逐个尝试在每个位置放置一个皇后。

2.2.1 判断位置是否合法在放置皇后之前，我们需要判断当前位置是否符合规则。

判断的条件包括当前位置所在的行、列以及对角线上是否已经存在其他皇后。

如果存在冲突，则需要尝试下一个位置。

2.2.2 放置皇后如果当前位置合法，我们将在该位置放置一个皇后，并继续递归地尝试下一行。

2.2.3 回溯如果放置皇后后无法找到合适的解决方案，我们需要回溯到上一行，将上一行的皇后位置向后移动一位，并尝试下一个位置。

2.3 输出解决方案当找到一个合适的解决方案时，我们输出棋盘的状态，显示每个位置是否有皇后。

2.4 继续寻找其他解决方案如果还存在其他解决方案，我们将继续递归回溯，直到找到所有的解决方案。

3. 实验结果经过实验，我们使用回溯算法成功解决了n皇后问题。

对于不同的n值，我们找到了所有的解决方案并进行了输出。

以下是几个n皇后问题的解决方案示例：3.1 n = 4- Q - -- - - QQ - - -- - Q -3.2 n = 8Q - - - - - - -- - - - Q - - -- - - - - - - Q- - - - - Q - -- - Q - - - - -- - - - - - Q -- Q - - - - - -- - - Q - - - -4. 总结通过本实验，我们了解了n皇后问题，并学习了回溯算法的应用。

N皇后问题爬山法和回溯法的实现及性能分析云南大学信息学院专业：计算机软件与理论目录一、N皇后问题 (3)1.问题描述 (3)2.数据结构 (3)二、爬山算法 (3)1.爬山算法一般介绍 (3)2. 爬山算法的伪代码 (4)3. 算法评价 (4)三、回溯法 (4)1.回溯法一般介绍 (4)2. 回溯法的伪代码 (4)3. 算法评价 (5)四、算法实现及性能比较 (5)五、两种算法性能分析 (6)六、结论 (7)七、参考文献 (7)附录 (8)一、N皇后问题1.问题描述（1）n皇后问题：在n*n格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，（2）分别用回溯法（递归）、爬山法和GA算法求解n皇后问题。

要求：输入n，并用运行时间比较几种算法在相同规模的问题时的求解效率。

列表给出结果。

2.数据结构1、逻辑结构：用到线性结构包括数组等。

2、存储结构（物理结构）：顺序存储结构。

二、爬山算法1.爬山算法一般介绍爬山法是指从当前的节点开始，和周围的邻居节点的值进行比较。

如果当前节点是最大的，那么返回当前节点，作为最大值(既山峰最高点)；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。

如此循环直到达到最高点。

每次都选择是与目标结点启发函数值最小的那个结点，经过迂回前进,最终达到解决问题的总目标。

如果我们把目标函数的几何图形看成一个山峰,那么点的直接移动就像人在爬山,选择方向,逐步向山顶移动。

爬山法需要建立一个描述数据库变化的单极值函数，且使极值对应目标状态；选取使函数值增长最大的那条规则作用于数据库；重复上步，直到没有规则使函数值继续增长。

爬山法是一种局部搜索算法，也属一种启发式方法。

但它一般只能得到局部最优，并且这种解还依赖于起始点的选取。

它是一种解多变量无约束最优化问题的一类方法，通过点的直接移动产生的目标值有所改善的点,经过这样的移动,逐步到达使目标函数最优的点。

计算机与信息技术学院实验报告专业：计算机科学与技术年级/班级：2009级 2011—2012学年第一一、实验项目N皇后问题二、需求分析八皇后问题是一个古老而著名的问题。

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

八皇后问题要求在一个8*8的棋盘上放上8个皇后，使得每一个皇后既不攻击到另外七个皇后，也不被另外七个皇后所攻击。

按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法：并找出所有的摆法。

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

本次实验算法设计中，用到的主要知识有：递归法的运用，for 语句的灵活运用，数据结构中树知识的灵活运用、数组及动态数组技术的掌握。

系统要求：win98 以上操作系统；语言平台：vc++6.0 或以上版本。

根据程序的设计要求，需要设计一个八皇后问题的演示程序，程序需要具备以下功能：能够快速查找并显示八皇后的布局方式有多少种正确方法。

能够逐个查看每种布局的结果。

能够很方便的改变皇后个数即棋盘规格。

三、概要设计：本实验是用递归和回溯法来实现的，分别测试了每一种摆法，并将一个解图形化显示输出。

在这程序中，思路主要是这样的：1、解决冲突问题和数据结构的实现对于数据结构的实现，则是着重于：（1）数组x[i]：表示第i个皇后放置的列；i的范围：0—n-1；（2）数据初始化（3）从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先用xx函数测试当前位置是未被占领；如果是，摆放第n-1个皇后后并宣布占领，接着进行递归；如果不是，测试下一个位置（n,m+1），但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。

（4）当n=8时，便一一打印出结果。

）首先定义一个递归找全部的解的递归函数FindQueen(int i)，设有一个参数i,表示1至i-1行都已有皇后合理放置的情况下，寻找第i行的合理放置。

09级计算机科学与技术2班组长：郭惠芝40912091小组成员：席菲菲40912098闫卫红40912099王铝红40912103回溯法----------n皇后问题王铝红，郭惠芝，席菲菲，闫卫红（陕西师范大学计算机科学学院陕西西安710062）摘要：文章中对“八皇后问题”进行了分析，给出了一种回溯算法解决“八皇后问题”并用C++语言实现，从而上升为对“n皇后问题”的解决。

关键字：回溯法，八皇后问题，算法，实现Eight Queens PuzzleAbstract: Article in the “Eight Queens Puzzle” issues were analyzed and given an iteration method to solve “Eight Queen Puzzle” and use C ++ language implementation.Keywords:Iteration method , Eight Queens Puzzle, Algorithm, Implementation中心内容：1、问题描述八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。

该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有76种方案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论比较特殊的是，皇后6x6棋盘的解比5 x 5少，其余解的数目随着皇后数目增加。

但似乎无数学表达式可以描述。

2、模型建立下面以8皇后为例建立模型，让大家更清楚的理解n皇后问题。

不妨设8个皇后为X i,她们分别在第i行（i=1，2，3，4，…，8），这样问题的解空间，就是一个8个皇后所在列的序号，为n元一维向量（X1 ，X2 ，X3，X4，X5 ，X6 ，X7 ，X8），搜索空间是1≦X i≦8（i=1,2,3,4,…，8），共88个状态。

N皇后问题实验报告电子工程学院A.实验内容在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，求解可以放置的方法种数。

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

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

C.算法设计1. 解决冲突问题:这个问题包括了行，列，两条对角线;列:规定每一列放一个皇后，不会造成列上的冲突;行:当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态;对角线:对角线有两个方向。

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

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

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

2. 算法设计因为n皇后问题，从n大于11开始求解过程耗时就很长，所以定义x数组的最大值MAXNUM=30;即最大可解决30皇后问题。

1) 判断当前位置是否可放置皇后皇后k在第k行第x[k]列时，x[i]==x[k] 时，两皇后在同一列上;abs(x[i]-x[k])==abs(i-k)时，两皇后在同一斜线上;两种情况两皇后都可相互攻击，返回false表示不符合条件。

bool Place(int k){int i;i=1;while(i<k){if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))return false;i=i+1;}return true;2) 输出当前解void Print(int x[],int n) {num++;printf("第%d\t种解法:(",num);for(int i=1;i<=n;i++) {printf("%d,",x[i]);if(i%n==0)printf(");\n"); }3) 回溯法搜索解空间void NQueens(int n){int k=1;x[1]=0;while(k>0){x[k]+=1;while(x[k]<=n&&!Place(k)) x[k]+=1;if(x[k]<=n)1 / 6{if(k==n)Print(x,n);else{k=k+1;x[k]=0;}}//回溯至上一行;elsek--;}}3. 实验结果及分析n皇后问题解的情况皇后的个问题的解数N=1 X=(1) N=2 无解N=3 无解N=4 X1=(2,4,1,3); X2=(3,1,4,2) N=5 X1=(1,3,5,2,4); X2=(1,4,2,5,3); X3=(2,4,1,3,5);X4=(2,5,3,1,4);X5=(3,1,4,2,5); X6=(3,5,2,4,1); X7=(4,1,3,5,2);X8=(4,2,5,3,1);X9=(5,2,4,1,3); X10=(5,3,1,4,2) N=6X1=(2,4,6,1,3,5);X2=(3,6,2,5,1,4);X3=(4,1,5,2,6,3);X4=(5,3,1, 6,4,2)N=7 40个解 N=8 92个解4. 实验程序随着N 的增大，解的个数增多，以N=4为例#include <stdio.h>#include<math.h>#define N 4 /* 定义棋盘大小 */static int sum; /* 当前已找到解的个数 */static int x[N];int place(int k){int j;for (j = 0; j < k; j ++)if (x[j] == x[k] || abs(j - k) == abs(x[j] - x[k])) return 0;2 / 6return 1;}/* 打印棋局 */void chessboard(){int i,j;int site[N];printf("第%d种解法:\n", ++ sum);for (i = 0; i < N; i ++) {for (j = 0; j < N; j ++)if (j == x[i]) {printf("Q ");site[i]=j+1;}else printf("* ");printf("\n");}printf("A%d(",sum);for(i = 0; i < N; i ++){printf("%d,",site[i]);}printf(");");printf("\n");}/* 回溯搜索解空间 */void backtrack(){int k = 0;x[0] = -1;while (k >= 0) {x[k] += 1; /* 向右移一列 *//* 向右移至出最右列或可以放置皇后的列 */ while ((x[k] < N) && !(place(k))) x[k] += 1; if (x[k] < N) /* 向右移未移出棋盘 */if (k == N - 1) chessboard(); /* 已移至最后一行 */else x[++ k] = -1; /* 向下移一行 */else k --; /* 回溯到上一行 */}}int main(void){backtrack();printf("%d皇后有%d个解:\n",N,sum); return 0;}3 / 6实验结果截图:5. 流程图4 / 6D.心得体会通过算法老师布置的这次大作业，首先使我们更好地理解皇后问题和回溯法的原理;其次，在作业过程中遇到的困难，使我们3人学会了如何合作才能更高效的解决问题;最后，在这次作业中，锻炼了我们收集资料，学习新技能的能力，感谢老师～E.参考文献《算法设计技巧与分析》——电子工业出版社《C程序设计》——西安电子科技大学出版社《回溯法》——百度文库5 / 6。

printf("\nMemory full!\n"); getchar(); exit(-1); }
size=MAX; n=0; printf("\nPlease input the Max weight(0 or negative numbers to exit)\n");
- 10 -
计算机算法实验报告
fflush(stdin); getchar(); } }
-7-
0/1 背包问题:
计算机算法实验报告
一 实验内容描述和功能分析
内容描述
已知有 N 种物品，和一个可以容纳 M 重量的背包，每种第 i 号的物品重量为 wi，假定物品 的每一部分 Xi 放入背包就会得到 Pi*Xi 的效益，这里 Xi=0 or 1，Pi>=0。要求出一种算法使 装入背包之物品的效益值达到最大值。
计算机算法实验报告
<<计算机算法基础>>实验报告
姓名： 学号： 专业： 班级：
报告日1-
计算机算法实验报告
目录
N 皇后问题
一、实验内容描述和功能分析 二、算法过程设计 三、程序调试及结果（附截图） 四、源代码（附源程序）
0/1 背包问题
一、实验内容描述和功能分析 二、算法过程设计 三、程序调试及结果（附截图） 四、源代码（附源程序）
if(!pp&&!ww) goto A;
while(pp!=0&&ww!=0) //当输入的都是 0 时，进行中断操作 {
p[n]=pp;w[n]=ww; n++; printf("Please input the price of %d bag\n",n+1); scanf("%f",&pp); printf("Please input the weight of %d bag\n",n+1); scanf("%f",&ww);

浅谈N皇后问题解法及可视化实现问题提出⼀般地，\({N}\)皇后问题描述如下：在⼤⼩为\({N×N}\)的棋盘上摆放\({N}\)个皇后，使其两两之间不能互相攻击，即任意两个皇后都不能处于棋盘的同⼀⾏、同⼀列或同⼀斜线上，求出满⾜条件的所有棋局及局⾯总数。

特殊地，当\({N=8}\)时为著名的以国际象棋棋盘为背景的8皇后问题，易解得符合条件的局⾯总数为92。

本实验主要探究\({N×N}\)的棋盘上摆放\({N}\)个皇后的⼀般问题。

问题分析\({N}\)皇后问题可以维护⼀个长度为\({N}\)的⼀维数组q表⽰局⾯情况。

\({q_i(i=0,…N-1)}\)表⽰第\({i}\)⾏皇后放置位置所在列数\({j(j=0,…N-1)}\)，每个局⾯可看作由\({0}\)到\({(N-1)}\)序列组成的⼀个排列，原问题可以转化成寻找所有不导致⾏/列/斜线冲突的排列。

直观的想法是将\({N}\)皇后问题看成组合问题，\({N×N}\)的棋盘上每个格都有防放置皇后和空格两种情况，总情况数达\({2^{N^2}}\)，指数爆炸在时间和空间复杂度上都难以负担。

⼀种改进思路是考虑每列仅允许出现⼀个皇后，按照⾏先序顺序放置皇后，第⼀⾏有\({N}\)种可能，第⼆⾏有\({N-1}\)种可能…第\({N}\)⾏有1种可能，总情况数缩减为\({N!}\)略有改善。

为进⼀步提⾼算法效率，考虑棋盘上每条斜线上仅允许出现⼀个皇后，在此联想到回溯和剪枝的算法。

算法描述引⼊N叉树的数据结构，构建\({N}\)皇后问题的解空间树。

排列长度\({N}\)为树的深度，据此判定递归的出⼝。

初始状态将⼀维数组q置空，以⾏先序从第0⾏开始递归求解。

遍历\({i}\)⾏每⼀列\({j}\)，若q中已有\({j}\)（即第\({j}\)列已经放置了皇后），则发⽣剪枝，继续遍历其他列；若q中没有\({j}\)，则\({q[i]=j}\)，递归式进⼊\({i+1}\)⾏的遍历，直到数组q中已经赋满\({N}\)个列号，则进⼊递归出⼝进⾏判定局⾯的合理性（即每个⾏/列/斜线最多仅有1个皇后）。