八皇后问题码.doc

【注：本代码是在百度知道中一同事的答案中摘录的。】 /*八皇后问题（栈的应用-回溯法） 在8*8的国际象棋盘上，安放8个皇后，要求没有一个皇后能够吃掉其它皇后 即：没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线*/ //作者：yangyizhi //日期：2012/1/13 //设计思路： /* 先假定在第一行第一列放一个皇后。从第二行开始，每一行根据上一行皇后的位置，选定一个合适的位置， 把走的每一步都压到一个栈中。 若不能选出合适的位置，则弹栈。（即，退一步）改变上一步皇后的位置，再继续试探 */ #include stdio.h #define Status int #define FALSE 0 #define SUCCESS 1 #define STACK_MAXSIZE 8 typedef struct QUEEN { char x ; //行号 char y ; //列号 } ElemType ; /*数据结构-栈*/ typedef struct STACK { ElemType data[STACK_MAXSIZE] ; int top ; //指向栈顶 } SqStack ; //进栈操作 //参数stackPtr为指向栈的指针 //参数x为压入栈的值 Status Push( SqStack * stackPtr , ElemType x ) { //如果栈满 if(stackPtr-top == STACK_MAXSIZE) { return FALSE ; } //先把游标加1，再向其所指的位置填数据 stackPtr-top++ ; stackPtr-data[stackPtr-top].x = x.x ; stackPtr-data[stackPtr-top].y = x.y ; return SUCCESS ; } //出栈操作 Status Pop( SqStack * stackPtr , ElemType * ret ) { //如果栈空 if(stackPtr-top == -1) { return FALSE ; } ret-x = stackPtr-data[stackPtr-top].x ; ret-y = stackPtr-data[stackPtr-top].y ; stackPtr-top-- ; return SUCCESS ; } /*函数声明*/ Status PrintQipan(char fun_qipan[9][9]) ; Status GetLegalLocate(char fun_qipan[9][9] , int row , ElemType * legalLocatePtr) ; Status PutEightQueen(char fun_qipan[9][9] , SqStack * queenStackPtr) ; /*主函数*/ Status main(void) { //初始化棋盘（0代表可用位置，1代表皇后已占用，2代表该位置经过验证不可用） char qipan[9][9] = {0} ; int count=0 ; //统计有多少可能的解 ElemType popLocate ; //定义栈 SqStack queenStack ; queenStack.top = -1 ; //根据求得的这一个解，不停地退栈 回溯 进而求得其它的解（相当于从某个叶子节点开始遍历整棵树） while(PutEightQueen(qipan , queenStack) != FALSE) { Pop(queenStack , popLocate) ; qipan[popLocate.x][popLocate.y] = 2 ; count++ ; } printf(\n八皇后问题共有%d种解 , count); return SUCCESS ; } //根据当前棋盘情况生成一个最终棋盘 //参数fun_qipan,参数queenStackPtr ,可确定一个棋盘的状态 Status PutEightQueen(char fun_qipan[9][9] , SqStack * queenStackPtr) { int currentRow ; //当前应该处理棋盘的第几行 ElemType popLocate ; ElemType legalLocate ; while( (currentRow=queenStackPtr-top+2) currentRow = 8 currentRo