文档章节

八皇后问题(回溯法)

1
 1944864971
发布于 2016/07/24 11:59
字数 500
阅读 10
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

//在棋盘上放置八个皇后,使得他们互不攻击,每个皇后的攻击范围
//是同行同列和同对角线要求找出所有的解
void serarch(int cur)//cur是行
{
if(cur==n)tot++;//递归边界,只要走到这里所有的皇后必然不会冲突
else
{
for(int i=0;i<n;i++)
{
int ok=1;
c[cur]=i;//c[cur]代表的是列,尝试把第cur的皇后放在第i列
for(int j=0;j<cur;j++)//检查是否和前面的皇后冲突
if(c[cur]==j||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])
{
ok=0;
break;
}
}
if(ok)search(cur+1);//如果合法则继续递归
}
}
//既然是逐行放置的就不会横向攻击,因此只需要检查纵向和斜向即可;
//cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j]是来检查
//皇后(cur,c[cur])和(j,c[j])是否在同一条对角线上(画出棋盘图就可明白)

~~~~~~~~~~~~~~~~~~~~~~~~~~~
/*
程序效率可以进一步提高:利用二维数组vis[2][]直接判断当前的皇后所在列以及对角线已有
其他的皇后,注意道到主对角线标识y-x可能为负数存取是要加上n;

*/

void search(int cur
{
if(cur==n)tot++;
else
{
for(int i=0;i<n;i++)
if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n])//利二维数组直接判断
{
c[cur]=i;//如果不用记录数组c则可以省略
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1;
search(cur+1);
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=0; //切记!!!!一定要该回来
}
}
}
/*
上面的程序有个及其关键的地方:vis数组的使用,他表示已经放置的皇后占据了
哪些lie 主对角线以及副对角线,一般的,如果在回溯法中修改了辅助的全局变量,则
一定要及时的把它们恢复原状
特别的 若函数有多个出口则在每个出口处修复被修改的值

*/

本文转载自:http://www.cnblogs.com/aaaadengchaochao/p/5234983.html

1
粉丝 0
博文 57
码字总数 0
作品 0
郑州
私信 提问

暂无文章

有哪些常用的命名git分支实例的例子? [关闭]

现在,我已经使用本地git存储库与我的组的CVS存储库进行了几个月的交互。 我已经制作了一个几乎神经质的分支,其中大部分幸运地合并回我的行李箱。 但是命名开始成为一个问题。 如果我有一个...

javail
2分钟前
0
0
在virtualenv中使用不同的Python版本

我有一个目前使用python 2.5.4运行的Debian系统。 我正确安装了virtualenv,一切正常。 我是否可以将virtualenv与其他版本的Python一起使用? 我编译了Python 2.6.2,并希望将其与一些virtu...

技术盛宴
17分钟前
3
0
保证金术语参考

术语,定义 1.钱包, 余额. ON THE ENCHANGED CONVERGENCE OF STANDARD LATTICE METHODS FOR OPTION PRICING...

MtrS
20分钟前
2
0
x006-函数和模块的使用

函数和模块的使用 在Python中可以使用def关键字来定义函数,和变量一样每个函数也有一个响亮的名字,而且命名规则跟变量的命名规则是一致的。在函数名后面的圆括号中可以放置传递给函数的参数...

伟大源于勇敢的开始
30分钟前
2
0
为什么面试必问线程状态?你的回答满分了吗

看很多同学的面经、网上的面试资料,都不约而同的提到了一个基础问题:“你知道线程有几种状态吗?状态之间的扭转是怎样的?”,有准备的同学都知道有五种:New(新建)、Runnable(可运行)...

Z_J_H
31分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部