运用回溯法求解把皇后问题

1、算法分析与设计实验报告第6次实验八皇后问题姓名杨玉茹学号201508010325班级计科1503时间5. 12下午地点软件大楼109实验名称运用冋溯法求解把皇后问题实验目的通过上机实验，要求掌握冋溯法，解决皇后算法的问题描述、算法设计思想、 程序设计。实验原理运用回溯法来解决这个问题：1.首先需要用一个量来表示这个皇后的位置，i来表示皇后所在行的位置， xi来表示皇后所在的列，根据实验题目的要求，不能够让皇后之间在同一行 或者同一列，或者同一对角线上，同一行和同一列这是一个显示约束条件，但 是同一对角线上这个是一个隐式约束条件，应该将这个转化为一个显示的约束 条件，所以根据分析，同一个对角线上

2、的两个元素的坐标只差相等，也就是1, j均表示皇后所在的列，xi与xj均表示皇后所在的列，那么2. 根据约朿条件以及回溯法的规则來查找每一个皇后的位置，如果每一个皇后 都找到正确的位置，那么方案数目就加1；实验步骤1.用一个bool函数来描述皇后之间位置的约束条件；queen函数就是来依次判断每一个皇后的位置，当i<=n的吋候， xi二1, 2, 3,. n 共n个子节点，对当前的每一个子节点用约朿函数去检查 每一个儿子节点是否符合，并且运用深度优先的方法去搜索子树，或者剪去不 可行的子树，然后再回溯到第一个皇后查找还有没有其他的方案；bool place (int t)ffor (in

3、t i二1;it;i+)关键代码1if (abs (i-t) =abs (xt-xi) | | (xt二二xi) return false;/ return true;lreturn true; void queen() /iint i;xl二0;int k=l;while (k>0)xk+二 1;while(xk<=n)&&!place(k)xk+=l;if(xk=n)if(k=n)sum+;elsek+； xk=0;elsek-;/回溯测试结果实验心得在这次实验当中最重要的就是利用回溯法去解决这个问题，当然最开始还应当 将隐约束问题转换为显约束问题，即同一个对角

4、线上的两个皇后也是不可行 的，因此应该观察对角线上的元素之1'可的特征，最后即可得到这个约朿函数， 再者就是运用回溯法当中的排列树去解决，将每一行的皇后看成树的每一层， 这样深度搜索的方式搜索，然后再回溯，最后得到方案，这里最重要的就是牢 牢把握住回溯法的思想。实验得分助教签名算法分析与设计实验报告第6次实验子集合问题姓名杨玉茹时间5. 12下午学号201508010325班级计科1503地点软件大楼109实验名称运用回溯法解决子集合问题实验目的 通过上机实验，要求掌握回溯算法的问题描述、算法设计思想、程序设计。运用非递归冋溯法来解答子集合的问题的时候，首先分析出来，可以运用子 集树的

5、方法来解决这个问题，那么根据子集树的概念，在本题当中，我们只需 要找出一个符合问题的方案即可，所以假若第一次就找到，那么我们就返回， 如果一直到达了叶子节点也没有找到，那么我们就再冋溯回去接着找。实验原理1h 2, 31, 2 b 312, 323 将这个函数声明为一个bool函数，然后只要相加的结果等于目标值，那么 就返回true;实验步骤 如果所得的结果大于目标值，那么我们就朝右子树搜索，如果所得结果小于 目标值，那么我们就朝左子树搜索，如果到了叶子节点，依然没有找到我们想 要的节点，那么就再回溯回去； 只要还有元素没有判断就继续选择。直到第n个元素，如果第n个元素判断 完还没有找到解的话

6、，就回溯到上一次选择的那个点，将其从集合里面删除并 从它后一个点继续重复前面的操作。如果冋溯的时候回溯到了笫一个元素z前 的话呢，表示这个时候要么所有元素都加入到集合都不够，或者是所有的情况 都找过了还是没有解决方案，这个时候返回无解。关键代码bool backtrack(int t)if(sum=c)return true;if(t>n)return false; r-=datat;if(sum+datat<=c)xt=l;/t+; sum=sum+datat;if(backtrack(t+1) return true; sum-=datat;if(sum+r>=c) xt

7、二0;t+;if(backtrack(t+1) return true; r+=datat;return false;测试结果实验心得这次实验主要学会的是运用非递归冋溯法进行解题，这道题和之前所学的例题 稍微有些不同，这道题不是求最优解，而是寻找一个目标值，如果这个目标值 存在，那么就返回true,否则就false,所以运用子集树进行深度优先搜索，然 后如果没有得到理想值，再冋溯，通过这道题，以后做其他的题也可以进行类 比分析。实验得分助教签名算法分析与设计实验报告第6次实验排列宝石问题姓名杨玉茹学号201508010325 班级计科 1503时间5. 12下午地点软件大楼109实验名称运用回

8、溯法解决排列宝石的问题实验目的通过上机实验，要求掌握回溯算法的问题描述、算法设计思想、程序设计。实验原理运用回溯法解决排列宝石的问题，这个问题和皇后问题有一些相似的地方， 在同一列同一行不能有相同颜色和形状的宝石，因此也需要相应的约束条件进 行约束和判断，然后再分别进行判断每一个元素。实验步骤1、定义一个解空间，它包含问题的解，也就是一颗排列树。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间，利用回溯算法backtrack,当行号（列号） 大于n吋，算法搜索至叶节点，当前找到可行性方案，sum+1；否者当前扩展 节点是解空间中的内部节点，找出未排列的宝石，用place检验当前宝

9、石是否 可以放置，并以深度优先的方式递归的对可行子树搜索。4、利用限界函数place函数避免移动到不可能产生解的子空间，这道题中的 限界函数就是同一行与同一列的宝石的颜色和形状不能相同。关键代码bool place (diamond *a, int *s, int x, int y)for (int i=l; iy; i+)/判断行中是否有颜色形状重复if(asxi. color=asxy. color|asxi. shape二二asxy. shape)return 0;for (int j二1; jx; j+)/判断列屮是否有颜色形状重复if(asjycolor二二asxy. colori

10、|asj y.shape=asxy. shape)return 0;return 1;/用回溯法递归搜索void backtrack(diamond *a,int *s, int t,int n,int &sum)int x, y;x=(t-l)/n+l;/存放的行号 y=(t-l)%n+l;/存放的列号 if (x>n)sum+;elsefor(int i=l;i<=n*n;i+)if (ai. use)/当前宝石未排列sxy=i;if (place (a, s, x, y)/当前宝石颜色形状不重复 ai. use=0;backtrack (a, s, t+1, n, s

11、um); ai. use=l;测试结果 e：学习法分折与设计实验谟篦六次实验涣踐列宝石问麴exe6回1123724&9125a三j实验心得这个实验由于套路和算法的思想和八皇后问题是一样的，只是稍微问题复杂了 一点，但是万变不离英宗，运用排列树的方法将这个问题套进去，问题就解决 了，还是将每一层的树看成是一行，分别对子树进行深度优先搜索，然后再回 溯，最后得到方案，这里最重要的就是牢牢把握住回溯法的思想，进行深度优 先搜索。实验得分助教签名附录：完整代码八皇后问题ttinclude "stdlib. h"include <iostream>using na

12、mespace std;define n 8int sum二0;int *x=new intn+l;bool place (int t)for(int i=l;i<t;i+)辻(abs(i-t)=abs(xt-xi)|(xt=xi) return false;/ return true;return true;void queen()int i;xl=0;int k=l;while(k>0)xk+=l;wh订e (xk<=n)&&!place(k)xk+=l;if(xk<=n)辻(k=n) sum+; else k+; xk=o; else k-; 回溯

13、 int main ()queen (); cout«sum;子集合问题 ttinclude <iostream> using namespace std;define max 1000 int datamax; int xmax=0;int c=0;int n=0;int r=0;int sum=0;bool backtrack(int t)if(sum=c)return true;if (t>n)return false;r-=datat;if (sum+datat<=c) xt=l;t卄； sum=sum+datat;辻(backtrack(t+1) r

14、eturn true; sum-二datat;if(sum+r>=c)xt=o;t+;if(backtrack(t+1)return true;r+=datat;return false;int main()cin»n»c;for(int i=0;i<n;i+)cin»datai;r+=datai;if(!backtrack(0) cout«/zno solution!*; elsefor(int i=0;i<n;i+)if (xi) cout«datai«/z ”；/排列宝石的问题#include<iostr

15、eam>#include<fstream>using namespace std;class diamondpublic:int color;/颜色编号int shape;/形状编号int use;/是否己经排列，默认1为未排列；/初始化n*n个宝石void init(diamond *a,int n)/分别为n种颜色各具n种形状的宝石赋初值for(int i=l;i<=n*n;i+)ai color=(i-l)/n+l;ai shape=(i-l)%n+l;ai use=l;检验宝石是否可放bool place(diamond *a, int *s,int x, in

16、t y)for (int i二l;i<y; i+)/判断行中是否有颜色形状重复if(asxi color=asxy. color| |asxi shape=asxy shape)return 0;for (int j=l; j<x; j+) /判断列中是否有颜色形状重复if(asjy color=asxy. color| |asjy. shape=asxy shape)return 0;return 1;/用回溯法递归搜索void backtrack(diamond *a, int *s, int t,int n,int &sum)int x, y;x=(t-l)/n+l;

17、/存放的行号y=(t-l)%n+l；/存放的列号if(x>n)sum+;elsefor (int i=l;i<=n*n;i+)if (ai. use)/当前宝石未排列 sx y二i;if (place (a, s, x, y)/当前宝石颜色形状不重复 ai use=o;back track (a, s, t+1, n, sum);ail use=l;/计算当前宝石排列的方案数int numdiamond(int n)diamond *a=new diamondn*n+1;init (a, n);int sum二0;int *s=new int*n+l;for (int m=l;m<=n;m+)sm二new intn+1;backtrack (a, s, 1, n, sum);:return sum;int main()读出输入文件中的数据fstream fin;fin. open(/zinput txt"，ios: in);if (fin. fail ()cout«f订e does not exist!"«endl;cout<"exit program/z«