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

实验报告4回溯算法实验4回溯算法解决N皇后问题一、实验目的1）掌握回溯算法的实现原理，生成树的建立以及限界函数的实现；2）利用回溯算法解决N皇后问题；二、实验内容回溯算法解决N皇后问题。三、算法设计1）编写限界函数boolPLACE(intk,intx[])，用以确定在k列上能否放置皇后；2）编写voidNQUEENS(intn)函数用以摆放N个皇后；3）编写主函数，控制输入的皇后数目；4）改进和检验程序。四、程序代码//回溯算法解决N皇后问题的c++程序#includemath.h#includeiostreamusingnamespacestd;intcount=0;//皇后摆放的可能性boolPLACE(intk,intx[]);//限界函数voidNQUEENS(intn);//摆放皇后intmain(){intqueen;cout先生（女士）请您输入皇后的总数，谢谢！:endl;cinqueen;NQUEENS(queen);cout所有可能均摆放完毕,谢谢操作endl;return0;}voidNQUEENS(intn){/*此过程使用回溯算法求出在一个n*n棋盘上放置n个皇后，使其即不同行，也不同列，也不在同一斜角线上*/intk,*x=newint[n];//存放皇后所在的行与列x[0]=0;k=0;while(k=0&&kn){//对所有的行执行以下语句x[k]=x[k]+1;//移到下一列while(x[k]=n&&(!PLACE(k,x))){//此处能放置一个皇后吗?x[k]=x[k]+1;//移到下一列}if(x[k]=n){//找到一个位置if(k==n-1){//是一个完整的解吗cout第++count排法是：endl;for(inti=0;in;i++)//打印皇后的排列{for(intj=0;jn;j++){if(x[i]==j+1){cout*;}else{cout.;}}cout\n;}cout\n;}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(ik){if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))return(false);//在同一列或者在同一斜角线上有两个皇后i=i+1;}return(true);}五、运行结果输入皇后的个数为4，程序输出如下：六、结果分析此程序用回溯算法成功地解决了N皇后问题，以上输入的值为：4，由结果的显示可知，程序切实可行。通过输入其它数值并分析可知：随着皇后数目的增大，排列的个数也越多！