开发者社区> 龙盛国际> 正文

各大计算机公司 笔试及面试 题目 - 深信服(八皇后问题)

简介:
+关注继续查看

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。


在n×n格的棋盘上摆放n个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,求解满足条件的棋盘布局。

n-皇后问题是典型的可以使用回溯算法求解的问题。如果你明白了问题的具体执行过程,也就对该问题的特点有了把握,从而选择合适的算法去求解。

以8-皇后问题为例,假设皇后所在的行用变量row表示,对应的列使用数组column[row]表示。

使用回溯算法执行的过程如下:

(1)第一次放置第1个皇后

将第1个皇后放在第0行第0列,即row=0,column[row]=column[0],如图所示:

第1个皇后放置在坐标(0,0)处。

(2)第一次放置第2个皇后

因为第1个皇后已经放好,第1个皇后放置到第0行第0列,从第1个皇后下方的格子开始判断。第2个皇后位于第1行,则row=1:

当column[row]=column[1]=0时,与第1个皇后在同一列上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[1]=1时,与第1个皇后在同一对角线上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[1]=2时,与第1个皇后不在同一行、同一列、同一对角线上,故放置第2个皇后。

如图所示:

第2个皇后放置在坐标(1,2)处。

(3)第一次放置第3个皇后

因为第2个皇后已经放好,第2个皇后放置到第1行第2列,从第2个皇后下方的格子开始判断。第3个皇后位于第2行,则row=2:

当column[row]=column[2]=0时,与第1个皇后在同一对角线上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[2]=1时,与第2个皇后在同一对角线上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[2]=2时,与第2个皇后在同一列上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[2]=3时,与第2个皇后在同一对角线上,冲突,继续后移到下一列(即column[row]++);

当column[row]=column[1]=4时,与第1、2个皇后不在同一行、同一列、同一对角线上,故放置第3个皇后。

如图所示:

第3个皇后放置在坐标(2,4)处。

(4)第一次放置第4个皇后

如图所示:

第4个皇后放置在坐标(3,1)处。

(5)第一次放置第5个皇后

如图所示:

第4个皇后放置在坐标(4,3)处。其余依次类推。


代码如下:



备注:转载于 http://hi.baidu.com/shirdrn/blog/item/2720311b5cc970108618bfb1.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【iOS开发】Xcode 7 Simulator 问题小记
问题1:Xcode -> Preferences -> Downloads 点击下载按钮弹出错误提示框 这里我没有再重现当时 Xcode 弹出错误提示框的场景,大概是在你想要下载 iOS 8.x 的 Simulator 或者 iOS 9.0 Documentation 的时候,告诉你有个什么什么地址不安全,你是否仍然要下载模拟器,然后你跟 Xcode 说『是的,我仍然要下载』 的时候,就没有然后了。
767 0
找优质的直播软件开发公司不用担心系统架构问题
文章标题中提到的系统架构问题,在直播软件开发过程中也是非常重要的一部分。为什么这么说呢?我们举个简单的例子,一个施工队盖楼肯定先要把整体的框架用钢筋扎好,然后再进行下一步的工作。开发直播软件也是一样,先把整体的架构设计好罗列出来,再把其中的功能挨个添加进去。
938 0
回应员工大规模罢工抗议,谷歌CEO发内部信解决公司性骚扰问题
谷歌表示正在通过三种方式改变可能存在的公司性骚扰问题。
184 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
17731 0
+关注
龙盛国际
南京师范大学虚拟地理环境教育部重点实验室,研究方向为地图综合,并行计算和云计算相关领域。 从事电子地图开发,室内导航开发。 QQ:592701357
211
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载