皇后问题--回溯算法

1、八皇后问题问题描述八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850 年提出： 在 8× 8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。 1854 年在柏林的象棋杂志上不同的作者发表了40 种不同的解，后来有人用图论的方法解出92 种结果。问题分析所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若在前进中受阻，则回头另择通路继续搜索。为了能够沿着原路逆序回退，须用栈保存曾经到达的每一个状态， 栈顶的状态即为回退的第一站。因此回溯法

2、均可用栈来实现。现在我们利用回溯算法求出其中一种解。其算法的基本思想如下：从第一行起逐行放置皇后，每放置一个皇后均要依次对第1，2，8 列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列进行试探。当 8 列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，重新对下一列进行试探，直到找到问题的解。图1 为八皇后问题的一种解。怎样判断一个位置是安全的为解决这个问题，我们对棋盘进行分析，将棋盘横坐标定为i ，纵坐标定为j,i和 j 的取值范围是从到。当某个皇后占了位

3、置(i,j)时，在这个位置的垂直方向、 水平方向和斜线方向都不能再放其它皇后了。用语句实现， 可定义如下三个整型数组： a8,b15,c24。其中，各数组的代表的意义如下：程序实现程序清单如下：#include <>int a8,b15,c24;int sit8; /*记录 8 个皇后所在列, 并且起到栈的作用*/void EightQueen(void)int i,j;i=1; /*从第一行开始，试探每个皇后的位置*/j=1; /*从第一列开始试探*/while (i<=8)while (j<=8)if (aj-1+bi+j-2+ci-j+7=3) /*在当前列上寻找

4、安全位置 */break;j+;if (j<=8) /*为第 i 个皇后找到了安全位置*/aj-1=0;bi+j-2=0;ci-j+7=0;/*皇后移入位置 (i,j)*/siti-1=j; /*相当于位置 (i,j)进栈 */i+; /*为下一个皇后寻找位置*/j=1;else /* 未找到安全位置 */i-;j=siti-1; /*出栈，回溯到上一行*/aj-1=1;bi+j-2=1;ci-j+7=1;/*移去位置 (i,j)上的皇后 */j=j+1; /*从下一列继续探索 */for (i=1;i<=8;i+) /*输出第 i 个皇后所在的列位置*/printf("

5、(%1d,%1d) ",i,siti-1);printf("n");int main(void)int i;for (i=0;i<=7;i+) ai=1;for (i=0;i<=14;i+) bi=1;for (i=0;i<=23;i+) ci=1;EightQueen();return 0;程序运行结果：(1,1) (2,5) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)上面的程序采用了非递归方法寻找八皇后问题的一种解，要找到八皇后问题的所有解，可通过修改函数EightQueen ，使其找到一个解后，程序并不终止，而是

6、打印输出解的信息，然后退栈回溯，继续寻求下一个解；一旦当前行是第1 行又仍需退栈回溯时，算法终止。八皇后问题也可采用递归实现， 下面的程序是采用递归方法求解八皇后问题的所有解的源程序。#include <>int a8,b15,c15,i;int sit8;void EightQueen(int i)int j;for (j=1;j<=8;j+)if (aj-1+bi+j-2+ci-j+7=3) /*如果第 i 列第 j 行为空 */aj-1=0;bi+j-2=0;ci-j+7=0;/*siti-1=j;if(i<8) EightQueen(i+1);else /*输出一组解 */占用第i 列第j行 */for (int k=1;k<9;k+)printf("(%1d,%1d)printf("n");",k,sitk-1);aj-1=1;bi+j-2=1;ci-j+7=1;int main(void)for (i=0;i<=7;i+) ai=1;for (i=0;i<=14;i+) bi=1;for (i=0;i<=14;i+) ci=1;EightQueen(1);/*调用递归函数 */return 0;1 表示第 j列上无皇后a j10 表示第 j列上有皇后1位置 (i , j )的对