递归法解八皇后问题.doc

例：八皇后问题。要求在88 格的国际象棋棋盘上摆放8 个皇后，使其不能互相攻击。由于皇后的走棋法是可以横走或直走或走斜线，每次走任意格数，所以要求这八个皇后中的任意两个都不处于同一行、同一列或同一斜线上。问有多少种摆法？#include#define N 8 /*设置最大皇后数*/int padN; /*声明数组，索引值为行号，数据值为列号*/int count; /*声明计数器，记录找到解的个数*/*-*/* 放置皇后的递归函数 */*-*/int put_queen(int x) int i,j; if(x=N) /*终止条件*/ for(i=0;iN;i+) /*通过遍历输出解*/ for(j=0;jN;j+) if(padi=j) /*是皇后*/ printf(“*“); else /*不是皇后*/ printf(“0“); printf(“n“); /*换行*/ count+; /*解的个数加1*/ printf(“Press any key to look for the next KEY:“); getchar(); /*按任意键继续求解*/ else for(i=0;iN;i+) if(place(x,i) /*检查是否可放置皇后*/ padx=i; put_queen(x+1); /*-*/* 检查皇后是否相互攻击 */*-*/int place(int r,int c) int i; if(r=0) /*第一行可以随意放置*/ return 1; for(i=0;ir;i+) /*判断是否与前边的皇后相互攻击*/ if(c=padi | (c+r)=i+padi | (c-r)=padi-i) return 0; return 1;/*-*/* 主程序：递归法解八皇后问题 */*-*/main() clrscr(); /*清屏*/ count=0; /*解的个数置零*/ put_queen(0); /*调用递归函数*/ printf(“There are %d keys.n“,count); /*输出解的个数*/代码2：递归实现n皇后问题算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a0a7代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；数组代表主对角线冲突，为bi-j+7，即从b0b14，如果某条主对角线上已经有皇后，则为1，否则为0；数组c代表从对角线冲突，为ci+j，即从c0c14，如果某条从对角线上已经有皇后，则为1，否则为0。程序如下：#include static char Queen88;static int a8;static int b15;static int c15;static int iQueenNum=0; /记录总的棋盘状态数void qu(int i); /参数i代表行int main()int iLine,iColumn;/棋盘初始化，空格为*，放置皇后的地方为for(iLine=0;iLine8;iLine+)aiLine=0; /列标记初始化，表示无列冲突for(iColumn=0;iColumn8;iColumn+)QueeniLineiColumn=*;/主、从对角线标记初始化，表示没有冲突for(iLine=0;iLine15;iLine+)biLine=ciLine=0;qu(0);return 0;void qu(int i)int iColumn;for(iColumn=0;iColumn8;iColumn+)if(aiColumn=0&bi-iColumn+7=0&ci+iColumn=0) /如果无冲突QueeniiColumn=; /放皇后aiColumn=1; /标记，下一次该列上不能放皇后bi-iColumn+7=1; /标记，下一次该主对角线上不能放皇后ci+iColumn=1; /标记，下一次该从对角线上不能放皇后if(i7) qu(i+1); /如果行还没有遍历完，进入下一行else /否则输出/输出棋盘状态int iLine,iColumn;printf(第%d种状态为：n,+iQueenNum);getchar();for(iLine=0;iLine8;iLine+)for(iColumn=0;iColumn8;iColumn+)printf(%c ,QueeniLineiColumn);printf(n);prin