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

回溯算法解决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皇后问题实验及其代码.doc
回溯算法解决N皇后问题实验及其代码 - 实验报告 4 回溯算法 实验 4 一、实
回溯法实验(n皇后问题)(迭代法).doc
回溯法实验(n皇后问题)(迭代法) - 算法分析与设计实验报告 第三 次附加实验 姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 回溯法实验(n 皇后...
用回溯算法解n皇后问题实验步骤.doc
回溯算法解n皇后问题实验步骤_IT/计算机_专业资料。详细写明了如何用回溯算法...3、 上机输入和调试自己所写的程序。 4、附程序主要代码: 1.n 后问题: #...
JAVA求解N皇后问题代码及答案.pdf
JAVA求解N皇后问题代码及答案 - 实验题目:回溯法n 皇后问题 班级:信息 112 姓名:孙波 学号:110111213 日期:2014-5-13 一、 实验目的 会用回溯法求解 n ...
实验四 用回溯法解N皇后问题等.pdf
实验四 用回溯法解N皇后问题等 - 课程名称: 算法设计与分析 实验项目:实验四 用回溯法解 n 皇后问题等 指导教师: 实验位置: 班姓组级: 长: 员: 虞勤国 ...
java求解N皇后问题代码及答案.doc
java求解N皇后问题代码及答案 - 实验题目:回溯法n 皇后问题 班级:信息 112 姓名:孙波 学号:110111213 日期:2014-5-13 一、 实验目的 会用回溯法求解 n ...
回溯法解决n皇后问题.doc
回溯法解决n皇后问题 - 该文档用回溯法解决n后问题,有程序的实现和回溯树的表示... 回溯法解决n皇后问题_IT/计算机_专业资料。该文档用回溯法解决n后问题,有程序...
n皇后问题算法实验报告.doc
二、实验目的 1.巩固和加深对回溯法的理解 2.了解递归和迭代法在回溯法...皇后有 10 个可行解 五、源代码 #include<stdio.h> static int n, sum=0...
河师大算法设计与分析N皇后问题实验报告_图文.doc
算法设计与分析 指导教师 史霄波 学号姓名 一、实验项目 N 皇后问题 0908114006...本实验是用递归和回溯法来实现的,分别测试了每一种摆法,并将一个 解图形化显示...
n皇后实验报告.doc
实验报告 实验名称 课程名称 n 皇后问题 计算机算法设计与分析 专业班级: 学号:...但这样做,你要有相当耐心才行, 这是很费时的。采用回溯算法进行求解,在搜索...
n皇后问题实验报告.doc
n皇后问题实验报告_计算机软件及应用_IT/计算机_专业资料。N 后问题算法一、...\n"<<endl; delete []queen; } } 运行结果: 回溯法求解八皇后问题 2010-...
回溯法解决8皇后问题实验报告.doc
回溯法解决8皇后问题实验报告_计算机软件及应用_IT/计算机_专业资料。使用c#语言 回溯法解决8皇后问题 有图形界面 可选择查看任一种方案 ...
算法实验 递归回溯解八皇后问题.doc
算法实验 递归回溯解皇后问题_计算机软件及应用_IT/计算机_专业资料。递归回溯...回溯法的实现及实验结果: 1、判断函数 代码 1: procedure BTrack_Queen(n) ...
回溯法解决n皇后问题_图文.doc
回溯法解决 n 皇后问题 回溯法解决 n 皇后问题摘要:回溯法是一种选优搜索法,
回溯法求解N皇后问题.ppt
回溯法求解N皇后问题_计算机软件及应用_IT/计算机_专业资料。HHIT Algorithm 8.1.3 回溯法的求解过程由于问题的解向量 X=(x1, x2, …, xn) 中的每个分量 ...
回溯法之N皇后问题(C语言).doc
//回溯法N 皇后问题 当 N>10,就有点抽了~~ /*结果前 to
回溯算法实验.doc
回溯算法实验 - 算法设计分析实验: 素数环问题和n皇后问题... 回溯算法实验_计算机软件及应用_IT/计算机_专业资料。算法设计分析实验: 素数环问题和n皇后问题 ...
n皇后问题实验报告.doc
n皇后问题实验报告 - 算法分析与设计报告 N 皇后问题 院系:计算机与通信工程
用回溯法实现n皇后问题.doc
回溯法实现n皇后问题 - 今天学习了一个经典的算法题:N 皇后问题。在 N*N
回溯法求N皇后问题.doc
=N && cb[h][m-h] == 1 && h != i) return false; //检查斜,...回溯法之N皇后问题(C语言... 2页 免费 实验报告:回溯法求解N皇... 暂无...
更多相关标签: