八皇后问题的最佳解决方案

2算法设计与分析报告3算法设计与分析实验报告八皇后问题的最佳解决方案回溯法概述1内容提要八皇后问题2解决八皇后问题常用算法3算法分析与总结4回溯法概述1一回溯法回溯法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试中找问题的解，当不满足求解条件就”回溯”(返回)，尝试别的路径。回溯算法是尝试搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头”的思想，作为其控制结构。本文主要描述递归回溯与非递归回溯，并用这两个算法解决经典的“八皇后”问题,找出该问题的最佳解决方案。八皇后问题描述2二八皇后问题描述：八皇后问题：要在8*8的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。如图2-1为一种方案，求所有的解。：图2-1解决八皇后问题常用算法3三解决八皇后问题常用的算法：枚举法解决八皇后问题3.1非递归回溯法解决八皇后问题3.2递归回溯法解决八皇后问题3.2这是一种最简单的算法，通过八重循环模拟搜索空间中的88个状态，按深度优先思想，把第1个皇后放在第1列，然后开始搜索第2到第8个皇后的合理位置，每个皇后只能在同一行的8个位置存放，每前进一步检查是否满足约束条件,不满足时，检查下一个位置，若满足约束条件，开始下一个皇后的合理位置检查，直到找出8个皇后的所有合理位置（即问题的全部解）。枚举法解决八皇后问题3.13.1枚举算法解决八皇后问题：①概述：不在同一列的表达式为：xi≠xj；不在同一主对角线上的表达式为：xi-ixj-j；不在同一负对角线上的表达式为：xi+i≠xj+j.枚举法解决八皇后问题3.1②约束条件③算法描述枚举法解决八皇后问题3.1Main1（）{inta[9];//初始化定义数组for(x1=1;x1=8;x1++)//从第一列开始搜索for(x2=1;x2=8;x2++){if（check(x2,2)=0）continue;//如果约束条件满足，则执行下一个for语句，否则当前皇后位置向右移动一位继续检查约束条件for(x3=1;x3=8;x3++){if（check(x3,3)=0）continue;//同上for(x4=1;x4=8;x4++){if（check(x4,4)=0）continue;//同上for(x5=1;x5=8;x5++){if（check(x5,5)=0）continue;//同上for(x6=1;x6=8;x6++){if（check(x6,6)=0）continue;//同上枚举法解决八皇后问题3.1for(x7=1;x7=8;x7++){if（check(x7,7)=0）continue;//同上for(x8=1;x8=8;x8++)//同上{if（check(x8,8)=0）continue;//同上else//找到了一组解for(i=1;i=8;i++)//输出一组满足约束的解print(xi);}}}}}}}}check(intxi,intn)//该函数是用来判断是否满足约束{inti;for(i=1;i=n-1;i++)//这里只需要判断前n-1个if(abs(xi-xn)=abs(i-n))or(xi=xn)//判断是否同一列或者同一对角线return(0);return(1);}非递归回溯法解决八皇后问题3.23.2非递归回溯解决八皇后问题：算法1的枚举算法可读性很好，但它只能解决八皇后问题，而不能解决任意的n皇后问题。因此不是通用的回溯算法。下面的非递归算法可以说是通用的n皇后问题算法模型。①概述：②算法描述非递归回溯法解决八皇后问题3.2ta[20],n;Main2(){input(n);bckdate（n）;}//初始化，输入皇后数目backdate(intn)//该函数是用来寻找满足约束的全部解{intk;a[1]=0;k=1;//k用来表示第k个皇后while(k0){a[k]=a[k]+1;while((a[k]=n)and(check(k)=0))//搜索第k个皇后位置a[k]=a[k]+1;if（a[k]=n）if(k=n)output(n);//找到一组解/else{k=k+1;//继续为第k+1个皇后找到位置/a[k]=0;}//注意下一个皇后一定要从头开始搜索/elsek=k-1;//回溯}}非递归回溯法解决八皇后问题3.2check(intk)//检查皇后是否满足约束{inti;for(i=1;i=k-1;i++)if(abs(a[i]-a[k])=abs(i-k))or(a[i]=a[k])return(0);return(1);}output()//输出满足该约束下的一组皇后位置{inti;for(i=1;i=n;i++)print(a[i]);}递归回溯法解决八皇后问题3.23.3递归回溯解决八皇后问题：①概述：对于回溯算法，更方便地是用递归控制方式实现，这种方式也可以解决任意的n皇后问题，算法的思想同样用深度优先搜索，在不满足约束条件时及时回溯。与上面两个算法不同，都是用check（）函数来检查当前状态是否满足约束条件，由于递归调用、回溯的整个过程是非线性的，用check（）函数来检查当前状态是否满足约束条件是不充分的，而用check（）函数（在算法1中说明）来检查当前状态是否满足约束条件又有太多冗余。这里，我们“利用数组记录状态信息”的技巧，用三个数组c,b,d分别记录棋盘上的n个列、2n-1个主对角线和2n-1个负对角线的占用情况。②算法描述递归回溯法解决八皇后问题3.2inta[20],b[20],c[40],d[40];intn,t,i,j,k;//t记录解的个数，i控制行，j控制列main(){inti,input(n);//输入皇后的个数for(i=1;i=n;i++){b[i]=0;//记录棋盘n个列c[i+1]=0;c[n+i]=0;//记录棋盘负对角线d[i]=0;d[n+i-1]=0;//记录棋盘主对角线}try（1）;}递归回溯法解决八皇后问题3.2try(inti){intj;for(j=1;j=n;j++)//j表示列号，第i个皇后有n种可能位置if(b[j]=0)and(c[i+j]=0)and(d[i-j+n]=0)//判断位置是否冲突{a[i]=j;//第i行第j列可以摆放编号为i的皇后b[j]=1;//占领第j列c[i+j]=1;d[i-j+n]=1;//占领两个对角线if(in)try(i+1);//n个皇后没有摆完,递归摆放下一皇后elseoutput();//完成任务，打印结果b[j]=0;c[i+j]=0;d[i-j+n]=0;//回溯，清理现场，从低向上回溯}}output(){t=t+1;//这里的t只是用来统计满足条件的解的个数print(t,'');for(k=1;k=n;k++)print(a[k],'');print(“换行符”);}算法分析与总结4四算法分析与总结：①三种算法比较分析：算法名字时间复杂度空间复杂度优缺点枚举法8864优点：简单，易实现。缺点：局限于皇后个数较少的情况非递归回溯法S(n2)O(nn)递归回溯法算法分析与总结4本文给出了求解八皇后的三种算法：枚举算法、递归回溯算法和非递归回溯算法，分析了其执行时间复杂度，并得到了运行结果，得到了从枚举解答八皇后问题到递归回溯解答N皇后问题的最佳解决方案。选择递归回溯法解决八皇后乃至N皇后问题更好，更具实用性。②算法总结