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

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(k>0){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(i<n)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],'