一,问题描述
在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
二,分析
采用逐步试探的方式,先从一个方向往前走,能进则进,不能进则退并尝试另外的路径。首先我们来分析一下国际象棋的规则,这些规则能够限制我们的前进,也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉
1)x=row(纵向不能有两个皇后)
2) y=col(横向不能有两个皇后)
3)col + row = y+x;(斜向正方向)
4)col - row = y-x;(斜向反方向)
遇到上述问题之一的时候,说明我们已经遇到了障碍,不能继续向前了。我们需要退回来,尝试其他路径。
我们将棋盘看作是一个8*8的数组,这样可以使用一种蛮干的思路去解决这个问题,这样我们就是在8*8=64个格子中取出8个的组合,C(64,8) = 4426165368,显然这个数非常大,在蛮干的基础上我们可以增加回溯,从第0列开始,我们逐列进行,从第0行到第7行找到一个不受任何已经现有皇后攻击的位置。
前面四列的摆放如上图则 第五列,我们会发现找不到皇后的安全位置
第五列的时候,摆放任何行都会受到上图所示已经存在的皇后的攻击,这时候我们认为我们撞了南墙了,是回头的时候了,我们后退一列,将原来摆放在第四列的皇后
(3,4)拿走,从(3,4)这个位置开始,我们在第四列中寻找下一个安全位置为(7,4),再继续到第五列,发现第五列仍然没有安全位置,回溯到第四列,此时第四列也是一个死胡同了,我们再回溯到第三列,这样前进几步,回退一步,最终直到在第8列上找到一个安全位置(成功)或者第一列已经是死胡同,但是第8列仍然没有找到安全位置为止
总结一下,用回溯的方法解决8皇后问题的步骤为:
1>从第一列开始,为皇后找到安全位置,然后跳到下一列
2>如果在第n列出现死胡同,如果该列为第一列,棋局失败,否则后退到上一列,在进行回溯
3>如果在第8列上找到了安全位置,则棋局成功。
三,源码(精选自网友解答)
回溯法非递归
更牛解答
分享到:
相关推荐
算法-八皇后问题-C语言实现-代码精简-可通过acm系统测试
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
回溯算法(八皇后问题) 绝对可以运行 c语言
主要介绍了C语言基于回溯算法解决八皇后问题的方法,简单描述了八皇后问题,并结合实例形式分析了C语言使用回溯算法解决八皇后问题的相关操作技巧,需要的朋友可以参考下
回溯算法解0--1背包问题
数据结构.-n皇后问题-回溯算法设计
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
北京工业大学--算法作业4--回溯算法--任务分配--Java 有n份作业分配给n个人去完成,每人完成一份作业。假定第i个人完成第j份作业需要花费cij时间, cij>0,1≦i,j≦n。试设计一个回溯算法,将n份作业分配给n个人完成...
八皇后问题的回溯算法的实现,实现语言为c++
回溯算法--解决 八皇后 四色图 背包 自己改写的程序 回溯算法--解决 八皇后 四色图 背包 自己改写的程序
可自定义皇后数量,采用遗传算法求解,已经vs编译通过,可运行
最近负责招聘,面试别人的时候自己也温习一下算法,呵呵,就用C++随便写了一个 呵呵
经典的算法,八皇后问题,c++实现,回溯法
八皇后问题的MonteCarlo算法与回溯法的混合实现,代码精确实现,实验报告或者说论文有详细的阐述!
利用回溯算法设八皇后问题,掌握回溯法的基本思想和算法设计的基本步骤。注意回溯算法解决此问题要找出问题所有的可行解。
可自定义皇后数量,采用爬山法求解,已经vs编译通过,可运行
利用回溯的递归方式解决八皇后问题,给出所有的解法;代码有详细注释,我花了一个晚上弄明白的,尽量写得让大家都能看懂:-)
个人写的一个八皇后问题,有需要的,可以下载。用C++编写的!
本算法是根据经典的八皇后的问题提出来的,采用了递归回溯法解决问题。
算法 加 算法算法 八皇后问题 八皇后问题