八皇后问题代码.doc

【注：本代码是在百度知道中一同事的答案中摘录的。】/*八皇后问题（栈的应用-回溯法）在8*8的国际象棋盘上，安放8个皇后，要求没有一个皇后能够吃掉其它皇后即：没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线*/作者：yangyizhi/日期：2012/1/13/设计思路：/*先假定在第一行第一列放一个皇后。从第二行开始，每一行根据上一行皇后的位置，选定一个合适的位置，把走的每一步都压到一个栈中。若不能选出合适的位置，则弹栈。（即，退一步）改变上一步皇后的位置，再继续试探*/#include #define Status int#define FALSE0#define SUCCESS1#define STACK_MAXSIZE8typedef struct QUEENchar x;/行号char y;/列号 ElemType;/*数据结构-栈*/typedef struct STACKElemType dataSTACK_MAXSIZE;int top; /指向栈顶 SqStack;/进栈操作/参数stackPtr为指向栈的指针/参数x为压入栈的值StatusPush( SqStack * stackPtr , ElemType x )/如果栈满if(stackPtr-top = STACK_MAXSIZE)return FALSE;/先把游标加1，再向其所指的位置填数据stackPtr-top+;stackPtr-datastackPtr-top.x = x.x;stackPtr-datastackPtr-top.y = x.y;return SUCCESS;/出栈操作StatusPop( SqStack * stackPtr , ElemType * ret )/如果栈空if(stackPtr-top = -1)return FALSE;ret-x = stackPtr-datastackPtr-top.x;ret-y = stackPtr-datastackPtr-top.y;stackPtr-top-;return SUCCESS;/*函数声明*/StatusPrintQipan(char fun_qipan99);StatusGetLegalLocate(char fun_qipan99 , int row , ElemType * legalLocatePtr);Status PutEightQueen(char fun_qipan99 , SqStack * queenStackPtr) ;/*主函数*/Statusmain(void)/初始化棋盘（0代表可用位置，1代表皇后已占用，2代表该位置经过验证不可用）char qipan99 = 0; int count=0; /统计有多少可能的解ElemType popLocate;/定义栈SqStack queenStack;queenStack.top = -1;/根据求得的这一个解，不停地退栈 回溯 进而求得其它的解（相当于从某个叶子节点开始遍历整棵树）while(PutEightQueen(qipan , &queenStack) != FALSE)Pop(&queenStack , &popLocate);qipanpopLocate.xpopLocate.y = 2; count+ ;printf(n八皇后问题共有%d种解 , count);return SUCCESS;/根据当前棋盘情况生成一个最终棋盘/参数fun_qipan,参数queenStackPtr ,可确定一个棋盘的状态StatusPutEightQueen(char fun_qipan99 , SqStack * queenStackPtr)int currentRow;/当前应该处理棋盘的第几行ElemType popLocate;ElemType legalLocate ;while( (currentRow=queenStackPtr-top+2) & currentRow =1 )/初始化合法位置坐标legalLocate.x = 0;legalLocate.y = 0;/在本行找出一个合法位置GetLegalLocate(fun_qipan , currentRow , &legalLocate);/若本行无合法位置，弹栈if(legalLocate.x = 0 & legalLocate.y = 0)if(Pop(queenStackPtr , &popLocate) = FALSE)/防止栈弹空break;fun_qipanpopLocate.xpopLocate.y = 2;/把该位置设置为 不可用else /有合法位置，压栈Push(queenStackPtr , legalLocate);fun_qipanlegalLocate.xlegalLocate.y = 1;/把该位置设置为 已占用/while()if(currentRow = 1) /栈已弹空，所有结果已求出return FALSE;else/打印结果PrintQipan(fun_qipan);return SUCCESS;/在本行找出一个合法位置/参数fun_qipan为棋盘二维数组/参数row为在棋盘的第row行找一个合法位置/参数legalLocatePtr为接收找出的合法位置坐标StatusGetLegalLocate(char fun_qipan99 , int row , ElemType * legalLocatePtr)int i , j ;int pass ;int flag ;/某位置的斜对角和竖列 不能有皇后for(pass=1 ; pass=8 ; pass+)/首先跳过那些不可用位置if(fun_qipanrowpass = 2)continue;flag = 1 ;/检查竖列for(i=1 ; ix = row ;legalLocatePtr-y = pass ;break ;/for()/若这一行没有合法的位置 ，把这一行位置全部设置为0if(flag = 0)for(pass=1 ; pass=8 ; pass+)fun_qipanrowpass = 0;return SUCCESS ;/打印棋盘StatusPrintQipan(char fun_qipan99)int i , j;/打