- 浏览: 41760 次
- 性别:
最新评论
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
import java.util.Calendar; public class BaHuangHou { public static int sum = 0, upperlimit = 1; /** * * @param row 纵列 * @param ld 左斜线 * @param rd 右斜线 */ public static void compute(int row, int ld, int rd) { //当row=11111111的时候,就是全部找完了。 if (row != upperlimit) { //找到该列的所以可以放的位置 int pos = upperlimit & ~(row | ld | rd); while (pos != 0) { //取出第一个可以放的位置,也就是最右边的1 int p = pos & -pos; //去除刚取出来的位置 pos -= p; //继续寻找,个个参数平移一位 compute(row + p, (ld + p) << 1, (rd + p) >> 1); } } else sum++;//种数自加 } public static void main(String[] args) { Calendar start; //输入皇后数字 int n = 8; //设置开始时间 start = Calendar.getInstance(); //保证数字在1到32之间,避免系统溢出 if ((n < 1) || (n > 32)) { System.out.println(" 只能计算1-32之间\n"); return; } System.out.println(n + " 皇后\n"); //结束标志 uperlimti=255 转换为二进制就是11111111 upperlimit = (upperlimit << n) - 1; //从0,0,0开始 compute(0, 0, 0); System.out.println("共有" + sum + "种排列, 计算时间" + (Calendar.getInstance().getTimeInMillis() - start .getTimeInMillis()) / 1000 + "秒 \n"); } }
乍一看似乎完全摸不着头脑,实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟,实在没研究出来再看下面的解说。
和普通算法一样,这是一个递归过程,程序一行一行地寻找可以放皇后的地方。过程带三个参数,row、ld和rd,分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6x6的棋盘为例,看看程序是怎么工作的。假设现在已经递归到第四层,前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置,位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来,得到该行所有的禁位,取反后就得到所有可以放的位置(用pos来表示)。p=p = pos & -pos;其结果是取出最右边的那个1。这样,p就表示该行的某个可以放子的位置,把它从pos中移除并递归调用compute过程。注意递归调用时三个参数的变化,每个参数都加上了一个禁位,但两个对角线方向的禁位对下一行的影响需要平移一位。最后,如果递归到某个时候发现row=111111了,说明六个皇后全放进去了,此时程序从第1行跳到第11行,找到的解的个数加一。
发表评论
-
2012-03-16 20:52 最大公约数;最小公倍数
2012-05-18 21:45 1371求最小公倍数方法如下: (1)、两数相乘法。 ... -
裴波那契算法
2012-05-18 21:40 892裴波那契算法,数组算法 #include<st ... -
一些的算法的格式
2012-05-17 12:15 1084做题目做久了之后就会发现,算法是有格式的。 一、深度优 ... -
第三届蓝桥杯预赛真题-C++本科组-10题(Java实现)
2012-05-15 11:11 975今盒子里有n个小球,A、B两人轮流从盒中取球,每个 ... -
第三届蓝桥杯预赛真题-C++高职组-10题(Java实现)
2012-05-15 10:57 12822x3=6个方格中放入ABCDE五个字母,右下角的那个 ... -
第三届蓝桥杯预赛真题-Java高职组-10题
2012-05-14 13:16 1992匪警请拨110,即使手机欠 ... -
第三届蓝桥杯预赛真题-Java本科组-10题
2012-05-14 12:41 1522泊松是法国数学家、物理学家和力学家。他一生致力科学事 ... -
计算24点-利用二叉树原理
2012-01-10 21:03 1658问题描述80年代全世界流行一种数字游戏,在中国我们把这种游戏称 ... -
吸血鬼数字
2012-01-09 20:32 942题目: 吸血鬼数字是 ... -
字符串的排列(A(m,n)),可重复选
2012-01-09 13:28 1312题目:现有ABCDE 5个球 构成的排列组合 可重复抽取 最多 ... -
蛇形矩阵
2012-01-09 13:38 1060Problem蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上 ... -
寻找最短路径
2012-01-07 18:51 1177题目:给定一个起点和一个终点。在一个8*8的棋盘上找出一条最短 ... -
字符串的排列(A(m,n))
2012-01-07 18:18 990题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
字符串的组合(C(m,n))
2012-01-07 17:46 1402题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
汉诺塔
2012-01-07 17:32 973关于汉诺塔大家应该很熟悉吧。 河內之塔(Towers ... -
三角螺旋矩阵
2012-01-07 17:27 1120打印如下矩阵,如果 n=7 则输出: 1 18 2 ...
相关推荐
总的来说,这三份Java代码为我们提供了学习和理解八皇后问题的不同角度,包括回溯法、位运算以及可能的优化技巧。通过阅读和分析这些代码,我们可以深入理解如何用编程语言解决实际问题,同时提升我们的算法设计和...
八皇后课程设计 源程序 流程表 运算结果 八皇后课程设计 源程序 流程表 运算结果
本资源使用c++代码实现N-皇后问题并附上研究小论文,实现算法有:回溯法(递归),回溯法(递归)的镜像优化,回溯法(非递归),回溯法(非...N-皇后问题是八皇后问题的拓展,要解决八皇后问题只需要将输入的值赋为8即可。
根据给定文件的信息,本文将围绕“用汇编语言编写八皇后问题并将结果显示在屏幕上”的主题进行详细解析。首先,我们需要了解八皇后问题的基本概念及其解决思路,随后深入探讨汇编语言实现的具体细节。 ### 八皇后...
在8086汇编语言中,实现八皇后问题的图形输出是一项挑战,因为它涉及到屏幕显示、内存管理和算法设计等多个方面。"8086汇编八皇后图形输出草稿"是一个项目,其目标是在640x480分辨率且支持16色的显示器上以图形方式...
在八皇后问题中,可以使用位操作来表示棋盘的状态,每个皇后的位置对应一个二进制位,如第i行皇后位置可以用2^(i-1)表示,通过按位与、按位或等操作可以快速检查某行、某列或对角线是否已有皇后。 2. **数组和矩阵*...
在实际代码中,可能会有额外的优化措施,如使用位运算来高效地检查和设置棋盘状态,或者使用标志来跟踪已尝试过的位置,以减少不必要的计算。 总之,这个压缩包提供了使用两种不同搜索策略解决八皇后问题的Java实现...
这个程序是用于解决八皇后问题的。八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。做这个课题,重要的就是先搞清楚哪个位置是合法的放皇后的位置,哪个不能,要先判断,后放置。我的...
《N皇后问题与八皇后问题的C++实现》 N皇后问题和八皇后问题是计算机科学领域经典的回溯算法实例,其主要目标是在一个N×N的棋盘上放置N个皇后,使得任意两个皇后都无法在同一行、同一列或同一对角线上相互攻击。这...
八皇后问题是一个经典的问题,在棋盘上放置八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一对角线上。这个问题在计算机科学中常被用来教授回溯法和递归思想。在这个实现中,我们不仅解决...
标题中的“bahuanghou.rar_栈八皇后”暗示了这是一个关于解决八皇后问题的程序,使用了栈作为数据结构,编程语言为C。八皇后问题是经典的计算机算法问题,目标是在一个8x8的棋盘上放置八个皇后,使得任何两个皇后都...
这需要利用回溯、递归等方法来尝试所有可能的放置方案,并通过位运算或者数组来标记已放置的皇后位置,避免冲突。此问题能锻炼对冲突检测和解决方案优化的能力,是学习算法和数据结构的好例子。 在课程设计中,这些...
总的来说,解决八皇后问题需要理解并运用回溯法、递归、数组(或位运算)表示以及问题的约束条件。通过这个题目,程序员可以锻炼逻辑思维能力,学习如何处理复杂问题的求解策略。在分析提供的压缩包文件...
在计算机科学领域,八皇后问题是一个经典的问题,它涉及到算法设计、回溯法以及位运算等核心概念。该问题由19世纪的数学家弗里德里希·高斯提出,要求在8×8的棋盘上摆放8个皇后,使得任意两个皇后都不能在同一行、...
- 为了避免重复计算,可以使用位运算来标记列和对角线的状态,提高效率。 - 使用深度优先搜索(DFS)进行回溯,因为八皇后问题的解数量相对较少,DFS通常足够高效。 7. **实际应用**: - 八皇后问题的解决思路...
### 八皇后问题求解——之递归 #### 一、八皇后问题概述 八皇后问题是由国际西洋棋棋手马克斯·贝瑟尔在1848年提出的经典问题。这个问题要求在8×8的国际象棋棋盘上放置八个皇后,使得任意两个皇后之间都不能相互...
总的来说,八皇后问题的求解是对数据结构和算法的实践运用,它涵盖了回溯法、递归、位运算以及基础的用户交互设计。这个课程设计有助于提升学生的逻辑思维能力和编程技巧,同时也是对经典问题的现代计算机科学解答。
八皇子leetcode 编码实践 ...八皇后拼图中的实现。 中实施。 参考 依赖注入 设计模式 编程语言 函数式编程 编程生活 数字用户线 敏捷 微服务架构 Java 杂项container_of(ptr,类型,成员) 人工智能 并发