資源描述:
《八皇后非遞歸加?!酚蓵T上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、#include#include"stdio.h"#defineSCALE8//問題的階數(shù),8為八皇后問題charchessboard[SCALE][SCALE];//全局變量,棋盤,放置棋子為'',否則為'*'intcount=0;//全局變量,記錄可能結(jié)果個數(shù)typedefstruct{intdata[SCALE];inttop;}SeqStack,*PSeqStack;PSeqStackInitialPseqStcak(void){PSeqStackS;S=(PSeqStack)malloc(sizeof(SeqStack));if(S)S
2、->top=-1;returnS;}intEmpty_SeqStack(PSeqStackS){//判斷棧是否為空,入口參數(shù):順序棧,返回值:1表示為空,0表示非空if(S->top==-1)return1;elsereturn0;}intPush_SeqStack(PSeqStackS,intx){//入口參數(shù):順序棧,返回值:1表示入棧成功,0表示失敗。if(S->top==SCALE)//棧滿不能入棧return0;else{S->top++;S->data[S->top]=x;return1;}}intPop_SeqStack(PSeqStackS){//刪
3、除棧頂元素并保存在*x,入口參數(shù):順序棧,返回值:1表示出棧成功,0表示失敗。if(Empty_SeqStack(S))//??詹荒艹鰲eturn0;else{S->top--;return1;}}intGetTop_SeqStack(PSeqStackS){//取出棧頂元素,入口參數(shù):順序棧,被取出的元素指針,這里用指針帶出棧頂值;返回值:1表示成功,0表示失敗。intx;if(Empty_SeqStack(S))//??誶eturn0;else{x=S->data[S->top];//棧頂元素存入*x中returnx;}}voidTrial(PSeqStack
4、S);intRemoveChess(inti,intj);voidPrintBoard();//輸出當前棋盤的布局intIsValidLayout();//檢驗當前棋盤是否為合法布局voidTrial(PSeqStackS){inti=0;intj=0;while(i!=-1){if(i==SCALE){count++;printf_s("numberofvalidlayoutis%d.",count);PrintBoard();i--;j=GetTop_SeqStack(S)-i;RemoveChess(i,j);Pop_SeqStack(S);i--;j
5、=GetTop_SeqStack(S)-i;RemoveChess(i,j);Pop_SeqStack(S);if(j==SCALE-1){i--;j=GetTop_SeqStack(S)-i;RemoveChess(i,j);Pop_SeqStack(S);j++;}elsej++;}else{chessboard[i][j]='';if(1==IsValidLayout()){Push_SeqStack(S,i+j);i++;j=0;}else{RemoveChess(i,j);if(j==SCALE-1){i--;j=GetTop_SeqStack(S)-i;
6、RemoveChess(i,j);Pop_SeqStack(S);if(j==SCALE-1){i--;j=GetTop_SeqStack(S)-i;RemoveChess(i,j);if(i==-1&&Empty_SeqStack(S)){break;}Pop_SeqStack(S);j++;}elsej++;}elsej++;}}}}intRemoveChess(inti,intj){//移走第i行,第j列的棋子if(i>=SCALE
7、
8、j>=SCALE)return0;if(chessboard[i][j]=='*')return0;elsechessboar
9、d[i][j]='*';return1;}voidPrintBoard(){//輸出當前棋盤的布局inti,j;for(i=0;i