- 浏览: 40138 次
- 性别:
最新评论
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯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 1336求最小公倍数方法如下: (1)、两数相乘法。 ... -
裴波那契算法
2012-05-18 21:40 840裴波那契算法,数组算法 #include<st ... -
一些的算法的格式
2012-05-17 12:15 1043做题目做久了之后就会发现,算法是有格式的。 一、深度优 ... -
第三届蓝桥杯预赛真题-C++本科组-10题(Java实现)
2012-05-15 11:11 943今盒子里有n个小球,A、B两人轮流从盒中取球,每个 ... -
第三届蓝桥杯预赛真题-C++高职组-10题(Java实现)
2012-05-15 10:57 12562x3=6个方格中放入ABCDE五个字母,右下角的那个 ... -
第三届蓝桥杯预赛真题-Java高职组-10题
2012-05-14 13:16 1943匪警请拨110,即使手机欠 ... -
第三届蓝桥杯预赛真题-Java本科组-10题
2012-05-14 12:41 1481泊松是法国数学家、物理学家和力学家。他一生致力科学事 ... -
计算24点-利用二叉树原理
2012-01-10 21:03 1622问题描述80年代全世界流行一种数字游戏,在中国我们把这种游戏称 ... -
吸血鬼数字
2012-01-09 20:32 909题目: 吸血鬼数字是 ... -
字符串的排列(A(m,n)),可重复选
2012-01-09 13:28 1269题目:现有ABCDE 5个球 构成的排列组合 可重复抽取 最多 ... -
蛇形矩阵
2012-01-09 13:38 1018Problem蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上 ... -
寻找最短路径
2012-01-07 18:51 1146题目:给定一个起点和一个终点。在一个8*8的棋盘上找出一条最短 ... -
字符串的排列(A(m,n))
2012-01-07 18:18 954题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
字符串的组合(C(m,n))
2012-01-07 17:46 1335题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
汉诺塔
2012-01-07 17:32 918关于汉诺塔大家应该很熟悉吧。 河內之塔(Towers ... -
三角螺旋矩阵
2012-01-07 17:27 1083打印如下矩阵,如果 n=7 则输出: 1 18 2 ...
相关推荐
本资源使用c++代码实现N-皇后问题并附上研究小论文,实现算法有:回溯法(递归),回溯法(递归)的镜像优化,回溯法(非递归),回溯法(非...N-皇后问题是八皇后问题的拓展,要解决八皇后问题只需要将输入的值赋为8即可。
八皇后课程设计 源程序 流程表 运算结果 八皇后课程设计 源程序 流程表 运算结果
这个程序是用于解决八皇后问题的。八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。做这个课题,重要的就是先搞清楚哪个位置是合法的放皇后的位置,哪个不能,要先判断,后放置。我的...
八皇后问题用最简短的递归代码来描述,可扩展到N皇后问题。还可以输出到文本中保存运算结果。
八皇子leetcode 编码实践 ...八皇后拼图中的实现。 中实施。 参考 依赖注入 设计模式 编程语言 函数式编程 编程生活 数字用户线 敏捷 微服务架构 Java 杂项container_of(ptr,类型,成员) 人工智能 并发
1.掌握使用VC++上机调试数组的基本方法; 2.通过此问题掌握了解数组的类型定义和表示方法;特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现。
本文为大家分享了python八皇后问题的解决方法,供大家参考,具体内容如下 题目: 给定一个 N*N 正方形棋盘,在上面放置 N个棋子,又叫皇后,使每两个棋子都不在同一条横线上、竖线上、斜线上。一般我们都讨论8皇后...
N皇后算法的运算过程用图形的方式显示。 本压缩包包含编译好的exe可运行文件和源代码。可以重新编译和修改。 本程序在Microsoft Visual C++ 2008 Express Edition编译并调试通过。 想运行本程序需要您的机器上装有...
八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题(Knapsack Problem) 数、运算 蒙地卡罗法求 PI Eratosthenes筛选求质数 超长整数运算(大数运算) 长 PI 最大公因数、最小公倍数、因式...
八个皇后 八枚银币 生命游戏 字串核对 双色 三色河内塔 背包问题(Knapsack Problem) 数 运算 蒙地卡罗法求 PI Eratosthenes筛选求质数 超长整数运算(大数运算) 长 PI 最大公因数 最小公倍数 因式...
155 AM6081 双极型8位D-A变换器 1994x-127 AMP1200 音频功放皇后 1993s-104 AN115 立体声解码 1991-135 AN2510S 摄象机寻象器 1994x-109 AN2661NK 影碟机视频 1995s-45 AN2662K 时基校正(模拟) 1995s-45 AN2664FBP...
八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题(Knapsack Problem) 数、运算 蒙地卡罗法求 PI Eratosthenes筛选求质数 超长整数运算(大数运算) 长 PI 最大公因数、最小公倍数、...
案例十八 八皇后问题 案例十九 老鼠钻迷宫 案例二十 基于词表的词频统计 案例二十一 括号嵌套匹配分析器 案例二十二 基数排序的实现 案例二十三 人机下棋问题 案例二十四 虚基类演示 案例二十五 异质链表问题 案例二...
8.Algorithm Gossip: 八皇后 9.Algorithm Gossip: 八枚银币. 10.Algorithm Gossip: 生命游戏. 11.Algorithm Gossip: 字串核对 12.Algorithm Gossip: 双色、三色河内塔 13.Algorithm Gossip: 背包问题(Knapsack ...
• 八个皇后 • 八枚银币 • 生命游戏 • 字符串核对 • 双色、三色河内塔 • 背包问题(Knapsack Problem) 数、运算 • 蒙地卡罗法求 PI • Eratosthenes筛选求质数 • 超长整数运算(大数运算) • 长...
八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题(Knapsack Problem) 数、运算 蒙地卡罗法求 PI Eratosthenes筛选求质数 超长整数运算(大数运算) 长 PI 最大公因数、最小公倍数、...
八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题(Knapsack Problem) 数、运算 蒙地卡罗法求 PI Eratosthenes筛选求质数 超长整数运算(大数运算) 长 PI 最大公因数、最小公倍数、...
八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题(Knapsack Problem) 数、运算 蒙地卡罗法求 PI Eratosthenes筛选求质数 超长整数运算(大数运算) 长 PI 最大公因数、最小公倍数、...
黑白棋,八皇后,哥德巴赫猜想,自守数,矩阵运算,三色旗,青蛙过河等问题。
八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题(Knapsack Problem) 数、运算 蒙地卡罗法求 PI Eratosthenes筛选求质数 超长整数运算(大数运算) 长 PI 最大公因数、最小公倍数、因式...