递归法解八皇后问题

《递归法解八皇后问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、例：八皇后问题。要求在8×8格的国际象棋棋盘上摆放8个皇后，使其不能互相攻击。由于皇后的走棋法是可以横走或直走或走斜线，每次走任意格数，所以要求这八个皇后中的任意两个都不处于同一行、同一列或同一斜线上。问有多少种摆法？#include　　#defineN8/*设置最大皇后数*/　　intpad[N];/*声明数组，索引值为行号，数据值为列号*/　　intcount;/*声明计数器，记录找到解的个数*/　　　　/*-----------------------------*/　　/*放置皇后的递归函数*/　　/*------

2、-----------------------*/　　intput_queen(intx)　　{　　inti,j;　　if(x==N)/*终止条件*/　　{　　for(i=0;i

3、henextKEY:“);　　getchar();/*按任意键继续求解*/　　}　　else　　for(i=0;i

4、　return1;　　for(i=0;i

5、

6、(c+r)==i+pad[i]

7、

8、(c-r)==pad[i]-i)　　return0;　　return1;　　}　　　　/*-----------------------------*/　　/*主程序：递归法解八皇后问题*/　　/*-----------------------------*/　　main()　　{　　clrscr();/*清屏*/　　count=0;/*解的个数置零*/　　put_queen(0);/*

9、调用递归函数*/　　printf(“Thereare%dkeys.“,count);/*输出解的个数*/　　}代码2：递归实现n皇后问题算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；数组代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]，如果某条主对角线上已经有皇后，则为1，否则为0；数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]，如果某条从对角线上已经有皇后，则为1，否则为0。程序如下：#include

10、io.h>staticcharQueen[8][8];staticinta[8];staticintb[15];staticintc[15];staticintiQueenNum=0;//记录总的棋盘状态数voidqu(inti);//参数i代表行intmain(){intiLine,iColumn;//棋盘初始化，空格为*，放置皇后的地方为@for(iLine=0;iLine<8;iLine++){a[iLine]=0;//列标记初始化，表示无列冲突for(iColumn=0;iColumn<8;iColumn++)Queen[iLine

11、][iColumn]='*';}//主、从对角线标记初始化，表示没有冲突for(iLine=0;iLine<15;iLine++)b[iLine]=c[iLine]=0;qu(0);return0;}voidqu(inti){intiColumn;for(iColumn=0;iColumn<8;iColumn++){if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)//如果无冲突{Queen[i][iColumn]='@';//放皇后a[iColumn]=1;//标记，下一次该列上不能

12、放皇后b[i-iColumn+7]=1;//标记，下一次该主对角线上不能放皇后c[i+iColumn]=1;//标记，下一次该从对角线上不能放皇后if(i<7)qu(i+1);/