八皇后問題的非遞歸實現

2019-11-17 05:11:30

字體：大中小

來源：轉載

供稿：網友

　　我們都知道八皇后問題是一個很經典的問題，當時很多解決八皇后問題的編程解法都是用遞歸解法，下面我用非遞歸的解法來實現如下：

　　其中有關設置標志位來表示該位是否可以下皇后的原理，請看鄭啟華的《pascal程序設計（第二版)>〉清華大學出版社出版的。代碼如下：

#include

#define available 1 //用來標志該位是否可用，availabel表示可用，unailable表示不可
用

#define unavailable 0

#define true 1

#define false 0

int j,top=-1,flag,i,is_pop,total=0;
　　// top用來保存棧頂指針，flag用來說明該次是否成功下了一個皇后
　　　　//is_pop用來說明是否把棧彈出,total用來保存共有多少種下法
　　　　//i用來保存下一次皇后應下的列

int stack[8],a[15],b[15],c[7];
　　　//stack保存皇后的位置，a,b,c三個數住用來保存該位是否可以下皇后

void init(void);//初始化各位狀態，使之可以下皇后

void release (void);//當該列都不能下皇后，則解除上次下皇后試對相關位的鎖定

main()

{

　　cout<
　　init();

　　is_pop=false;//初始化

　　for( ; ;)

　　{

　　　do {

　　　　for (j=is_pop? stack[i]+1:0;j<=7;j++)

　　　　　if (a[i+j]&&b[i-j+7]&&c[j])//判定該位是否可用
　　　　　　{//若可用，則棧頂指針上移，在該位存入皇后號

　　　　　　top++;

　　　　　　stack[top]=j;

　　　　　　a[i+j]=b[i-j+7]=c[j]=unavailable;//并把相關位設為不可用

　　　　　　i++;//i指向下一個應填入皇后德列

　　　　　　flag=true;//設標志，說明成功

　　　　　　is_pop=false;

　　　　　　break;//則直接退出循環

　　　　　}

　　　　if (!flag)//若不成功，則釋放被鎖定的位

　　　　　release();

　　　　flag=false;

　　　　if (stack[0]+1==8&&top==-1)//若第一列也沒有位置可以放皇后，

　　　　　　goto END; //則說明沒有其他的放法了，則退出

　　　}

　　　while (top!=7);

　　　for (int k=0;k<=7;k++)

　　　　cout

上一篇：探索C++的秘密之詳解extern “C”

下一篇：利用C語言小程序來解決大問題