《皇后问题(源程序)》由会员分享,可在线阅读,更多相关《皇后问题(源程序)(4页珍藏版)》请在金锄头文库上搜索。
1、#include #include #include #define StackSize 20 typedef struct int row,col; DataType; typedef struct DataType dataStackSize; int top; SeqStack; typedef struct int chess2020; QueenType;void main() SeqStack S; DataType newelem; QueenType Q; int row,col,number; void InitStack(SeqStack *S, QueenType *Q,
2、 int number);void Push(SeqStack *S, DataType newelem, QueenType *Q, int number); DataType Pop(SeqStack *S, QueenType *Q, int number); void PrintStack(SeqStack S);do coutnumber; if (number!=0) InitStack( row=0; col=0; while (row!=-1) while (col0) col+; if (col=number)/回溯到上一个皇后 newelem=Pop( row-; col=
3、newelem.col+1; else /放置皇后 newelem.row=row; newelem.col=col; Push( row+; col=0; if (row=number)/皇后已放满,输出,退后二步 PrintStack(S); newelem=Pop(/最后一个皇后 newelem=Pop(/最后第二个皇后 row=newelem.row; col=newelem.col+1; while(number!=0); void InitStack(SeqStack *S, QueenType *Q, int number) int i,j; S-top=-1; for (i=0
4、;ichessij=0; void Push(SeqStack *S, DataType newelem, QueenType *Q, int number) /放置皇后时,在四条线上各单元加 1, (行、列、左上右下、右上 左下) int i,j,k; S-top+; S-dataS-top=newelem; for (i=0;ichessinewelem.col+; for (j=0;jchessnewelem.rowj+;if (newelem.rowchessij+; i+; j+; if (newelem.row=0) Q-chessij+; i+; j-; DataType Pop
5、(SeqStack *S, QueenType *Q, int number) /撤销皇后时,在四条线上各单元减 1, (行、列、左上右下、右上 左下) int i,j,k; DataType elem; S-top-; elem=S-dataS-top+1; for (i=0;ichessielem.col-; for (j=0;jchesselem.rowj-; if (elem.rowchessij-; i+; j+; if (elem.row=0) Q-chessij-; i+; j-; return elem; void PrintStack(SeqStack S) int i; cout“ 答案为:“; for (i=0; i=S.top;i+) cout“(“S.datai.row“,“S.datai.col“) “; coutendl;