资源描述：
《--八皇后问题--回溯算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、八皇后问题问题描述八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 问题分析所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若在前进中受阻，则回头另择通路继续搜索。为了能够沿着原路逆序回退，须用栈保存曾经到达的每一个
2、状态，栈顶的状态即为回退的第一站。因此回溯法均可用栈来实现。现在我们利用回溯算法求出其中一种解。其算法的基本思想如下：从第一行起逐行放置皇后，每放置一个皇后均要依次对第1，2，．．．，8列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列进行试探。当8列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，重新对下一列进行试探，直到找到问题的解。图1为八皇后问题的一种解。怎样判断一个位置是安全的
3、？为解决这个问题，我们对棋盘进行分析，将棋盘横坐标定为i，纵坐标定为j,i和j的取值范围是从１到８。当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。用语句实现，可定义如下三个整型数组：a[8],b[15],c[24]。其中，各数组的代表的意义如下： 程序实现程序清单如下：#includeinta[8],b[15],c[24];intsit[8];/*记录8个皇后所在列,并且起到栈的作用*/voidEightQueen(void){inti,j;i=1;/*从
4、第一行开始，试探每个皇后的位置*/j=1;/*从第一列开始试探*/while(i<=8){while(j<=8){if(a[j-1]+b[i+j-2]+c[i-j+7]==3)/*在当前列上寻找安全位置*/break;j++;}if(j<=8)/*为第i个皇后找到了安全位置*/{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*皇后移入位置(i,j)*/sit[i-1]=j;/*相当于位置(i,j)进栈*/i++;/*为下一个皇后寻找位置*/j=1;}else/*未找到安全位置*/{i--;j=sit[i-
5、1];/*出栈，回溯到上一行*/a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;/*移去位置(i,j)上的皇后*/j=j+1;/*从下一列继续探索*/}}for(i=1;i<=8;i++)/*输出第i个皇后所在的列位置*/printf("(%1d,%1d)",i,sit[i-1]);printf("");}intmain(void){inti;for(i=0;i<=7;i++)a[i]=1;for(i=0;i<=14;i++)b[i]=1;for(i=0;i<=23;i++)c[i]=1;EightQue
6、en();return0;}程序运行结果：(1,1)(2,5)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4) 上面的程序采用了非递归方法寻找八皇后问题的一种解，要找到八皇后问题的所有解，可通过修改函数EightQueen，使其找到一个解后，程序并不终止，而是打印输出解的信息，然后退栈回溯，继续寻求下一个解；一旦当前行是第1行又仍需退栈回溯时，算法终止。八皇后问题也可采用递归实现，下面的程序是采用递归方法求解八皇后问题的所有解的源程序。#includeinta[8],b[15],c[15
7、],i;intsit[8];voidEightQueen(inti){intj;for(j=1;j<=8;j++)if(a[j-1]+b[i+j-2]+c[i-j+7]==3)/*如果第i列第j行为空*/{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/sit[i-1]=j;if(i<8)EightQueen(i+1);else/*输出一组解*/{for(intk=1;k<9;k++)printf("(%1d,%1d)",k,sit[k-1]);printf("");}a[j-1]
8、=1;b[i+j-2]=1;c[i-j+7]=1;}}intmain(void){for(i=0;i<=7;i++)a[i]=1;for(i=0;i<=14;i++)b[i]=1;for(i=0;i<=14;i++)c[i]=1;EightQueen(1);/*调用递归函数*/return0;}
