八皇后非递归加栈

《八皇后非递归加栈》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include"stdio.h"#defineSCALE8//问题的阶数，8为八皇后问题charchessboard[SCALE][SCALE];//全局变量，棋盘，放置棋子为''，否则为'*'intcount=0;//全局变量，记录可能结果个数typedefstruct{intdata[SCALE];inttop;}SeqStack,*PSeqStack;PSeqStackInitialPseqStcak(void){PSeqStackS;S=(PSeqStack)malloc(sizeof(SeqStack));if(S)S

2、->top=-1;returnS;}intEmpty_SeqStack(PSeqStackS){//判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空if(S->top==-1)return1;elsereturn0;}intPush_SeqStack(PSeqStackS,intx){//入口参数：顺序栈，返回值：1表示入栈成功，0表示失败。if(S->top==SCALE)//栈满不能入栈return0;else{S->top++;S->data[S->top]=x;return1;}}intPop_SeqStack(PSeqStackS){//删

3、除栈顶元素并保存在*x，入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。if(Empty_SeqStack(S))//栈空不能出栈return0;else{S->top--;return1;}}intGetTop_SeqStack(PSeqStackS){//取出栈顶元素，入口参数：顺序栈，被取出的元素指针，这里用指针带出栈顶值;返回值：1表示成功，0表示失败。intx;if(Empty_SeqStack(S))//栈空return0;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