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

1、2算法设计与分析算法设计与分析报告报告3算法设计与分析实验报告算法设计与分析实验报告八皇后问题的最佳解决方案八皇后问题的最佳解决方案回溯法概述回溯法概述1八皇后问题八皇后问题2解决八皇后问题常用算法解决八皇后问题常用算法3算法分析与总结算法分析与总结4回溯法概述回溯法概述1一一 回溯法回溯法 回溯法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试中找问题的解，当不满足求解条件就”回溯”(返回)，尝试别的路径。回溯算法是尝试搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头”的思想，作为其控制结构。本文主要描述递归回溯与非递归回溯，并用这两个算法解决经典的“八皇后”问题,找出该问

2、题的最佳解决方案。八皇后问题描述八皇后问题描述2二二 八皇后问题描述：八皇后问题描述： 八皇后问题：要在8*8的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。如图2-1为一种方案，求所有的解。：图图 2-12-1 解决八皇后问题常用算法解决八皇后问题常用算法3三三 解决八皇后问题常用的算法：解决八皇后问题常用的算法： 枚举法解决八皇后问题枚举法解决八皇后问题3.1 非递归回溯法解决八皇后问题非递归回溯法解决八皇后问题3.2 递归回溯法解决八皇后问题递归回溯法解决八皇后问题3.2 这是一种最简单的算法，通过八重循环模拟搜索空间中的8

3、8个状态，按深度优先思想，把第1个皇后放在第1列，然后开始搜索第2到第8个皇后的合理位置，每个皇后只能在同一行的8个位置存放，每前进一步检查是否满足约束条件,不满足时，检查下一个位置，若满足约束条件，开始下一个皇后的合理位置检查，直到找出8个皇后的所有合理位置（即问题的全部解）。 枚举法解决八皇后问题枚举法解决八皇后问题3.13.1枚举算法解决八皇后问题：枚举算法解决八皇后问题：概述概述：n不在同一列的表达式为：不在同一列的表达式为：xixj；n不在同一主对角线上的表达式为：不在同一主对角线上的表达式为：xi-ixj-j；n不在同一负对角线上的表达式为：不在同一负对角线上的表达式为：xi+ix

4、j+j. 枚举法解决八皇后问题枚举法解决八皇后问题3.1 约束条件约束条件 算法算法描述描述 枚举法解决八皇后问题枚举法解决八皇后问题3.1Mainain1（ ）int a9; / /初始化定义数组初始化定义数组 for (x1=1; x1=8; x1+) /从第一列开始搜索从第一列开始搜索 for (x2=1; x2=8; x2+) if （ check(x2,2)=0 ） continue; /如果约束条件满足，则执行下一如果约束条件满足，则执行下一个个for 语句，否则当前皇后位置向右移动一位继续检查约束条件语句，否则当前皇后位置向右移动一位继续检查约束条件 for (x3=1;x3=8

5、;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; x

6、8=8; x8+) /同上同上 if （check(x8,8)=0） continue; /同上同上 else /找到了一组解找到了一组解 for(i=1;i=8;i+) /输出一组满足约束的解输出一组满足约束的解 print(xi);); check(int xi, int n) /该函数是用来判断是否满足约束该函数是用来判断是否满足约束 int i; for(i=1;i0 ) ak=ak+1; while (ak=n) and (check(k)=0) /搜搜索第索第k个皇后位置个皇后位置 ak=ak+1; if（ ak=n） if(k=n ) output(n); /找到一组解找到一组解

7、/ else k=k+1; /继续为第继续为第k+1个皇后找到位置个皇后找到位置/ ak=0; /注意下一个皇后一定要从头开始搜索注意下一个皇后一定要从头开始搜索/ else k=k-1; /回溯回溯 非递归回溯法解决八皇后问题非递归回溯法解决八皇后问题3.2check(int k)/检查皇后是否满足约束检查皇后是否满足约束 int i; for(i=1;i=k-1;i+)if (abs(ai-ak)=abs(i-k) or (ai=ak) return(0); return(1);output( ) /输出满足该约束下的一组皇后位置输出满足该约束下的一组皇后位置 int i; for(i=1

8、;i=n;i+) print(ai); 递归回溯法解决八皇后问题递归回溯法解决八皇后问题3.23.3递归回溯解决八皇后问题：递归回溯解决八皇后问题：概述概述：n对于回溯算法，更方便地是用递归控制方式实现，这种方式也可对于回溯算法，更方便地是用递归控制方式实现，这种方式也可以解决任意的以解决任意的n皇后问题，算法的思想同样用深度优先搜索，在不满皇后问题，算法的思想同样用深度优先搜索，在不满足约束条件时及时回溯。足约束条件时及时回溯。n与上面两个算法不同，都是用与上面两个算法不同，都是用check（）函数来检查当前状态是否（）函数来检查当前状态是否满足约束条件，由于递归调用、回溯的整个过程是非线性

9、的，用满足约束条件，由于递归调用、回溯的整个过程是非线性的，用check（）函数来检查当前状态是否满足约束条件是不充分的，而（）函数来检查当前状态是否满足约束条件是不充分的，而用用check（）函数（在算法（）函数（在算法1中说明）来检查当前状态是否满足约束中说明）来检查当前状态是否满足约束条件又有太多冗余。条件又有太多冗余。n这里，我们这里，我们 “利用数组记录状态信息利用数组记录状态信息”的技巧，用三个数组的技巧，用三个数组c,b,d分别记录棋盘上的分别记录棋盘上的n个列、个列、2n-1个主对角线和个主对角线和2n-1个负对角线的占用个负对角线的占用情况。情况。 算法描述算法描述 递归回溯

10、法解决八皇后问题递归回溯法解决八皇后问题3.2int a20,b20,c40,d40; int n,t,i,j,k; /t/t记录解的个数，记录解的个数，i控制行，控制行，j控制列控制列 main( ) int i, input(n); /输入皇后的个数输入皇后的个数 for(i=1;i=n;i+) bi=0;/记录棋盘记录棋盘n个列个列 ci+1=0; cn+i=0;/记录棋盘负对角线记录棋盘负对角线 di=0; dn+i-1=0;/记录棋盘主对角线记录棋盘主对角线 try（1）; 递归回溯法解决八皇后问题递归回溯法解决八皇后问题3.2try(int i) int j; for(j=1;j=

11、n;j+) /j表示列号，第表示列号，第i个皇后有个皇后有n种可能位置种可能位置 if (bj=0) and (ci+j=0) and (di-j+n=0)/判断位置是否冲突判断位置是否冲突 ai=j; /第第i行第行第j列可以摆放编号为列可以摆放编号为i的皇后的皇后 bj=1; /占领第占领第j列列 ci+j=1; di-j+n=1; /占领两个对角线占领两个对角线 if (in) try(i+1); /n个皇后没有摆完个皇后没有摆完, ,递归摆放下一皇后递归摆放下一皇后 else output( ); /完成任务，打印结果完成任务，打印结果 bj=0; ci+j=0; di-j+n=0; /回溯，清理现场，从低向上回溯回溯，清理现场，从低向上回溯 output( ) t=t+1;/;/这里的这里的t只是用来统计满足条件的解的个数只是用来统计满足条件的解的个数 print(t, ); for( k=1;k=n;k+) print(ak, ); print(“ “ 换行符换行符”); 算法分析与总结算法分析与总结4 四四 算法分析与总结：算法分析与总结：三种算法比较分析三种算法比较分析：算法分析与总结算法分析与总结4 本文给出了求解八皇后的三种算法：枚举算本文给出了求解八皇后的三种算法：枚举算法、递归回溯算法和非递归回溯算法，