皇后問題(源程序)

《皇后問題(源程序)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、#include#include#include#defineStackSize20typedefstruct{introw,col;}DataType;typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;typedefstruct{intchess[20][20];}QueenType;voidmain(){SeqStackS;DataTypenewelem;QueenTypeQ;introw,col,number;voidInit

2、Stack(SeqStack*S,QueenType*Q,intnumber);voidPush(SeqStack*S,DataTypenewelem,QueenType*Q,intnumber);DataTypePop(SeqStack*S,QueenType*Q,intnumber);voidPrintStack(SeqStackS);do{cout<<"請(qǐng)輸入皇后數(shù)(結(jié)束為0)：";cin>>number;if(number!=0){InitStack(&S,&Q,number);row=0;col=0;while(row!=-1){while(

3、(col0))col++;if(col==number)//回溯到上一個(gè)皇后{newelem=Pop(&S,&Q,number);row--;col=newelem.col+1;}else{//放置皇后newelem.row=row;newelem.col=col;Push(&S,newelem,&Q,number);row++;col=0;if(row==number)//皇后已放滿，輸出，退后二步{PrintStack(S);newelem=Pop(&S,&Q,number);//最后一個(gè)皇

4、后newelem=Pop(&S,&Q,number);//最后第二個(gè)皇后row=newelem.row;col=newelem.col+1;}}}}}while(number!=0);}voidInitStack(SeqStack*S,QueenType*Q,intnumber){inti,j;S->top=-1;for(i=0;ichess[i][j]=0;}voidPush(SeqStack*S,DataTypenewelem,QueenType*Q,intnumber){//

5、放置皇后時(shí)，在四條線上各單元加1，（行、列、左上右下、右上左下）inti,j,k;S->top++;S->data[S->top]=newelem;for(i=0;ichess[i][newelem.col]++;for(j=0;jchess[newelem.row][j]++;if(newelem.row

6、ile((ichess[i][j]++;i++;j++;}if(newelem.row<(number-1-newelem.col))//右上左下k=newelem.row;elsek=number-1-newelem.col;i=newelem.row-k;j=newelem.col+k;while((i=0)){Q->chess[i][j]++;i++;j--;}}DataTypePop(SeqStack*S,QueenType*Q,intnumber){//撤銷皇后時(shí)，在

7、四條線上各單元減1，（行、列、左上右下、右上左下）inti,j,k;DataTypeelem;S->top--;elem=S->data[S->top+1];for(i=0;ichess[i][elem.col]--;for(j=0;jchess[elem.row][j]--;if(elem.row

8、number)){Q->chess[i][j]--;i++;j++;}if(elem.row<