当前位置:首页 >> 理学 >>

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


实验报告 4 回溯算法
实验 4 一、实验目的 1)掌握回溯算法的实现原理,生成树的建立以及限界函数的实现; 2)利用回溯算法解决 N 皇后问题; 二、 实验内容 回溯算法解决 N 皇后问题。 三、 算法设计 1)编写限界函数 bool PLACE(int k,int x[]),用以确定在 k 列上能否放置皇后; 2)编写 void NQUEENS(int n)函数用以摆放 N 个皇后; 3)编写主函数,控制输入的皇后数目; 4)改进和检验程序。 四、 程序代码 //回溯算法解决 N 皇后问题的 c++程序 #include<math.h> #include<iostream> using namespace std; int count=0; //皇后摆放的可能性 bool PLACE(int k,int x[]);//限界函数 void NQUEENS(int n);//摆放皇后 回溯算法解决 N 皇后问题

int main() { int queen; cout<<"先生(女士)请您输入皇后的总数,谢谢!:"<<endl; cin>>queen; NQUEENS(queen); cout<<"所有可能均摆放完毕,谢谢操作"<<endl; return 0; } void NQUEENS(int n){

/*此过程使用回溯算法求出在一个 n*n 棋盘上放置 n 个皇后,使其即不同行,也不同列, 也不在同一斜角线上*/ int k, *x=new int[n];//存放皇后所在的行与列 x[0]=0; k=0; while (k>=0&&k<n){ 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(int i=0;i<n;i++)//打印皇后的排列 { for (int j=0;j<n;j++) { if (x[i] == j+1) { cout<<"*"; } else { cout<<". "; } } cout<<"\n"; } cout<<"\n"; } else } { k=k+1; x[k]=0;} //移向下一行

else } }

k=k-1;

//回溯

bool PLACE(int k,int x[]){ /* 如果一个皇后能放在第 k 行和 x(k)列,返回 ture;否则返回 false。x 是一个全局变量, 进入此过程的时候已经置了 k 个值。ABS(r)过程返回 r 的绝对值*/ int i=0; while (i<k){ if( x[i]==x[k]||abs(x[i]-x[k])==abs(i-k) ) return (false); i=i+1; } return (true); } 五、运行结果 输入皇后的个数为 4,程序输出如下: //在同一列 或者在同一斜角线上 有两个皇后

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


相关文章:
实验报告:回溯法求解N皇后问题(Java实现)
实验报告一、实验名称:回溯法求解 N 皇后问题(Java 实现) 二、学习知识:回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规 模开始...
回溯法实验(n皇后问题)
回溯法实验(n皇后问题) - 算法分析与设计实验报告 第六 次实验 姓名 时间 实验名称 12.12 上午 学号 地点 班级 工训楼 309 回溯法实验(n 皇后问题) 实验...
回溯法解决8皇后问题实验报告
回溯法解决8皇后问题实验报告_计算机软件及应用_IT/计算机_专业资料。使用c#语言 回溯法解决8皇后问题 有图形界面 可选择查看任一种方案 ...
n皇后问题算法实验报告
二、实验目的 1.巩固和加深对回溯法的理解 2.了解递归和迭代法在回溯法...皇后有 10 个可行解 五、源代码 #include&lt;stdio.h&gt; static int n, sum=0...
实验四 回溯法求n皇后问题
实验四 回溯法求n皇后问题 - 本科实验报告 课程名称: 算法设计与分析 实验项目:回溯法n 皇后问题 实验地点: 专业班级: 学号: 学生姓名: 指导教师: 实验四...
实验四 用回溯法解n皇后问题等
实验四 用回溯法解n皇后问题等 - 课程名称: 算法设计与分析 实验项目:实验四 用回溯法解 n 皇后问题等 指导教师: 实验位置: 班姓组级: 长: 员: 虞勤国 ...
回溯算法实验
回溯算法实验 - 算法设计分析实验: 素数环问题和n皇后问题... 回溯算法实验_计算机软件及应用_IT/计算机_专业资料。算法设计分析实验: 素数环问题和n皇后问题 ...
回溯法解决n皇后问题
回溯法解决n皇后问题 - 该文档用回溯法解决n后问题,有程序的实现和回溯树的表示... 回溯法解决n皇后问题_IT/计算机_专业资料。该文档用回溯法解决n后问题,有程序...
N皇后问题回溯算法c语言版
N皇后问题回溯算法c语言版_计算机软件及应用_IT/计算机_专业资料。N皇后问题回溯算法c语言版,并调试成功 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;...
n皇后问题算法设计
算法设计及分析 n 皇后问题---回溯求解国际象棋中...程序代码: #include&quot;stdio.h&quot; int a[20],b[20...算法实验 递归回溯解八皇... 暂无评价 9页 1下载...
更多相关标签: