皇后問題--回溯算法

1、八皇后問題問題描述八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數(shù)學家高斯1850 年提出： 在 8× 8 格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。 1854 年在柏林的象棋雜志上不同的作者發(fā)表了40 種不同的解，后來有人用圖論的方法解出92 種結果。問題分析所謂回溯就是走回頭路，該方法是在一定的約束條件下試探地搜索前進，若在前進中受阻，則回頭另擇通路繼續(xù)搜索。為了能夠沿著原路逆序回退，須用棧保存曾經到達的每一個狀態(tài)， 棧頂?shù)臓顟B(tài)即為回退的第一站。因此回溯法

2、均可用棧來實現(xiàn)?，F(xiàn)在我們利用回溯算法求出其中一種解。其算法的基本思想如下：從第一行起逐行放置皇后，每放置一個皇后均要依次對第1，2，8 列進行試探，并盡可能取小的列數(shù)。若當前試探的列位置是安全的，即不與已放置的其他皇后沖突，則將該行的列位置保存在棧中，然后繼續(xù)在下一行上尋找安全位置；若當前試探的列位置不安全，則用下一列進行試探。當 8 列位置試探完畢都未找到安全位置時，就退?；厮莸缴弦恍校匦聦ο乱涣羞M行試探，直到找到問題的解。圖1 為八皇后問題的一種解。怎樣判斷一個位置是安全的為解決這個問題，我們對棋盤進行分析，將棋盤橫坐標定為i ，縱坐標定為j,i和 j 的取值范圍是從到。當某個皇后占了位

3、置(i,j)時，在這個位置的垂直方向、 水平方向和斜線方向都不能再放其它皇后了。用語句實現(xiàn)， 可定義如下三個整型數(shù)組： a8,b15,c24。其中，各數(shù)組的代表的意義如下：程序實現(xiàn)程序清單如下：#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; /*從下一列繼續(xù)探索 */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)上面的程序采用了非遞歸方法尋找八皇后問題的一種解，要找到八皇后問題的所有解，可通過修改函數(shù)EightQueen ，使其找到一個解后，程序并不終止，而是

6、打印輸出解的信息，然后退棧回溯，繼續(xù)尋求下一個解；一旦當前行是第1 行又仍需退?；厮輹r，算法終止。八皇后問題也可采用遞歸實現(xiàn)， 下面的程序是采用遞歸方法求解八皇后問題的所有解的源程序。#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);/*調用遞歸函數(shù) */return 0;1 表示第 j列上無皇后a j10 表示第 j列上有皇后1位置 (i , j )的對