回溯算法解决N皇后问题实验及其代码.doc

《回溯算法解决N皇后问题实验及其代码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告4回溯算法实验4回溯算法解决N皇后问题一、实验目的1）掌握回溯算法的实现原理，生成树的建立以及限界函数的实现；2）利用回溯算法解决N皇后问题；二、实验内容回溯算法解决N皇后问题。三、算法设计1）编写限界函数boolPLACE(intk,intx[])，用以确定在k列上能否放置皇后；2）编写voidNQUEENS(intn)函数用以摆放N个皇后；3）编写主函数，控制输入的皇后数目；4）改进和检验程序。四、程序代码//回溯算法解决N皇后问题的c++程序#include#includeusingnamespacestd;intcoun

2、t=0;//皇后摆放的可能性boolPLACE(intk,intx[]);//限界函数voidNQUEENS(intn);//摆放皇后intmain(){intqueen;cout<<"先生（女士）请您输入皇后的总数，谢谢！:"<>queen;NQUEENS(queen);cout<<"所有可能均摆放完毕,谢谢操作"<

3、=0;k=0;while(k>=0&&k

4、<"";}cout<<"";}else{k=k+1;x[k]=0;}//移向下一行}elsek=k-1;//回溯}}boolPLACE(intk,intx[]){/*如果一个皇后能放在第k行和x(k)列，返回ture;否则返回false。x是一个全局变量，进入此过程的时候已经置了k个值。ABS(r)过程返回r的绝对值*/inti=0;while(i

5、

6、abs(x[i]-x[k])==abs(i-k))return(false);//在同一列或者在同一斜角线上有两个皇后i=i+1;}return(true);}五、运行结果输入皇后的

7、个数为4，程序输出如下：六、结果分析此程序用回溯算法成功地解决了N皇后问题，以上输入的值为：4，由结果的显示可知，程序切实可行。通过输入其它数值并分析可知：随着皇后数目的增大，排列的个数也越多！