内容简介:八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8个格子的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后, 为了达到此目的,八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当
一、背景
八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8个格子的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后, 为了达到此目的, 任两个皇后都不能处于同一条横行、纵行或斜线上 (中国象棋,车可以走横线,纵线),问有多少种摆法,高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以编程解决此问题。
八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。
当且仅当 n = 1 或 n ≥ 4 时问题有解.
皇后可攻击范围如图所示:图中蓝色区块不允许放其他皇后
力扣(leetcode)原题链接: https://leetcode-cn.com/problems/n-queens-ii/
该题官方提供了2种方式,但是官方讲解的并不容易理解,且在主对角线和次对角线描述反了,利用位运算的方法只提供了方法,我通过自己的理解画了图形,所谓有图有真相,方便理解一些,在参考其他题解后,我再添加了一种利用斜率判断安全位置的解法。
二、思路
1.穷举法
时间复杂度:O(n^n)
如八皇后:8^8 = 16777216
进行暴力穷举: n个for循环嵌套遍历,找出所有合适的摆放方式,效率低下,不推荐!
2.递归和回溯法
时间复杂度: O(n!) =n*(n-2)(n-4)...
空间复杂度: O(n),保存对角线是否被占用以及列的信息
-
约束编程概念:
在放置每个皇后以后会增加限制。当在棋盘上放置了一个皇后后,立即排除当前行,列和对应的两个对角线。该过程传递了约束从而有助于减少需要考虑情况数。如下图所示:
-
回溯算法:
解决一个回溯问题,实际上就是一个决策树的遍历过程。
1、路径:也就是已经做出的选择。
2、选择列表:也就是你当前可以做的选择。
3、结束条件:也就是到达决策树底层,无法再做选择的条件。
DFS(深度优先搜索算法) 也采用了回溯源节点方式直到遍历完所有节点。
-
n皇后问题特点:
1.一行一列只能有一个皇后 (横线,纵线攻击), 且每行、每列必须有一个皇后 (n*n 棋盘 要摆放n个皇后)
2.皇后占据的每条斜线有规律,可据此判断当前位置是否安全(主对角线和次对角线的规律 )
摆放要求:任两个皇后都不能处于同一条横行、纵行或斜线上,问有多少种摆法
棋盘可用一个二维数组表示
1.不能在同一行,每个皇后放置在一行后,保证下一个皇后在下一行摆放。
2.不能在同一列,用一维数组记录每列是否被皇后占据,1:被占用; 0: 未被占用
3.如何确定是否在同一条斜线上?
有2种方式
-
方法一:主对角线和次对角线上的常数规律
相同主对角线上: row -col = 固定常数
而且每条对角线的常数值不同,因此用来标识该对角线是否已经被皇后占用
如下图所示:第一条主对角线上,row= col , row =col = 0 ,由右上数第二条 为-1,-2 ... 直到-7。
注:
注:如果在主对角线右上侧, col> row , 因此 const是负数,如果用数组下标索引存储会导致越界异常,因此可加一个固定正整数(大于等于n)避免 (下见代码可理解)。
相同次对角线上:row+col = const,每条次对角线的值也不相同。从上到下对角线的值从0到14依次递增
-
方法二:根据斜率确定在同一条斜线上
利用两点之间斜率绝对值为 1,即夹角的正切值为1,夹角为 45度或者 135度,据此判断是否在其他皇后的攻击斜线上。
公式: |y2-y1| = |x2-x1|
斜率如图所示:
在放置第三个皇后时,排除已有皇后占据的列,再剩下位置中与已经放置皇后的坐标计算斜率,如果斜率绝对值为1,即不是安全位置。
动态展示图:
三、代码展示
方法一:官方解法,利用 数组 记录被占据的列信息,以及根据每条斜线被占据记录。
- 初始化操作
public void initQueen(int n) { /** * 一行一列只能有一个queen,记录某列是否被占用,int数组记录,数组下标表示列;1表示占用,0表示未被占用 */ int[] cols = new int[n]; /**主对角线特点: row -col = const, 对角线的个数是 2*n-1 * 因为考虑row-col为负数情况(右上三角),会发生越界异常,加一个固定常数n,所以这里数组长度也变为 3*n-1, * 官方代码长度延长了2n, 即4*n-1。 */ int[] zhuDiagonal = new int[3*n - 1]; /** * 次对角线特点: row+col =const,次对角线不用延长数组长度,对角线的条数即为 2*n-1 */ int[] ciDiagonal = new int[ 2*n - 1]; // 调用递归回溯方法,下见 int count = back2Track(0, 0, n, cols, zhuDiagonal, ciDiagonal); System.out.printf("共有%d 种方法排列",count); }
- 判断当前位置是否安全
public boolean isSafe(int row,int col,int n,int[] cols,int[] zhu, int[] ci) { int res = cols[col] + zhu[row-col+ n] + ci[row+col]; return res ==0 ? true:false; } //如果当前位置列,主对角线,次对线均为0,表示当前位置安全,可以摆放皇后。
- 递归回溯
public int back2Track(int row,int count, int n ,int[] cols,int[] zhu, int[] ci) { for(int col= 0; col< n; col++) { if(isSafe(row,col,n,cols,zhu,ci)) { /** * 在安全位置,占用 */ //当前列,主对角线,列都占用标志:1 cols[col] =1; zhu[row-col + n] =1; ci[row +col] =1; //遍历到最后一行了,返回成功解一个 if(row +1 ==n ) {count ++;} else { //遍历下一行,此时 row+1 count = back2Track(row+1,count,n,cols,zhu,ci); } //如果某行所有列都不安全,递归回退,将原来置为1的位置清除,继续遍历下一列 cols[col] = 0; zhu[row-col+ n] =0; ci[row+col] =0; } } return count; }
方法二
关键方法:
1.利用一维数组表示二维空间的棋盘中皇后的位置
2.利用两点之间斜率绝对值为 1,即夹角的正切值为1,夹角为 45度或者 135度,据此判断是否在其他皇后的攻击斜线上。
代码如下:
- 初始化
/** * 表示n*n位棋盘,也表示n位皇后 */ int n ; /** * 一维数组存储皇后位置,数组下标代表行,数组值代表列;例如: locations[0]= 0: 表示 第一行第一列有一位皇后 */ int[] locations; /** * 记录可排列种类有多少 */ static int maxCount;
- 判断是否安全
/** * 判断第k个皇后在第k行某列是否安全 */ private boolean isSafe(int k) { //与前n-1个皇后比较 for(int i = 0 ; i< k; i++) { //这里较难理解 //1, 因为locations中记录前k-1行皇后的列摆放位置,数组下标代表行,数组值代表列 //如果locations[i] == locations[k],则表示这一列已经有皇后占据了,冲突不安全 //2,Math.abs(k- i) == Math.abs(locations[k] - locations[i]) 利用的是|y2-y1| = |x2-x1| 公式,斜率为1,也不安全 if(locations[i] == locations[k] || Math.abs(k- i) == Math.abs(locations[k] - locations[i])) { return false; } } return true; }
- 递归回溯方法
//k表示第k行,也表示第k个皇后, private void check(int k) { if(k ==n) { print(); //成功计数器+1 maxCount ++; return; } for (int i = 0; i<n; i++) { //遍历列,首先就将当前列设值,在判断安全时会进行比较 locations[k] =i; if(isSafe(k)) { //如果安全,在递归k+1行 check(k+1); } } }
- 打印每种解的皇后摆放
/** * 打印皇后可行排列顺序 */ private void print() { for (int col: locations) { System.out.print(col + " "); } System.out.println(); }
一行代表一种摆放方式
输出结果可以用游戏验证:8皇后游戏: http://360.6822.com/www1.9/play_76277.html
方法三:利用位运算实现
计算机对位运算计算更快,这个方法实现很巧妙,对位运算会有更深的理解。
在看该方法前,先复习一下位运算的基本运算,后面会用上。
- 位运算的基本运算
1.按位与 & : 有0则为0, 只有当两位都是 1 时结果才是 1,否则为0。 2.按位或 | : 有1则为1,即两位中只要有 1 位为 1 结果就是 1,两位都为 0 则结果为 0。 3. 取反 ~ : 0 则变为 1,1 则变为 0。 4.左位移 << :向左进行移位操作,高位丢弃,低位补 0 如 1<<3 1向左位移3位 000000001 --> 00001000 = 2^3 =8 (10) 5.右位移 >> :向右进行移位操作,对无符号数,高位补 0,对于有符号数,高位补符号位 如 00001011 向右位移2位,00001011>>2 = 00000010, 左边2位丢弃,高位补0
示例图如下:
与运算
或运算
1.原码:是最简单的机器数表示法。用最高位表示符号位,‘1’表示负号,‘0’表示正号。其他位存放该数的二进制的绝对值。
2.反码:正数的反码还是等于原码,负数的反码就是他的原码除符号位外,按位取反。
3.补码: 正数的补码等于他的原码,负数的补码等于反码+1。
注:正数的原码,反码,补码相同,计算机中运算是以补码的形式存储计算的。
本次算法相关:
- x & -x : 该运算只保留x最右边的第一个1 ,其余置为0。
例如:x= 00110110, -x = 10110110 (负值是符号位取反,其他位不变), x的补码还是其原码,-x的补码是反码+1
即 01001001 (反码) +1 = 01001010,两数按位与计算结果
00110110
01001010
=00000010 - x&(x-1): 该运算清除x最右边的第一个1为0,其余位值不变 。
可以证明:1,最低位为1,直接清0;2,最低位为0,中间某个位置为1,-1会向前借位,导致最右边第一个1,被借位为0 .
提示:该算法遍历是从低位开始,是从右到左的遍历,上2个方法是从左到右的方式,这个方法巧妙在于之前的方法是用数组存储被占用的位置,这个就是用3个int类型值,int 4个字节,32位来替代数组表示。
下面我们来看如何使用3个int类型的值 表示列,主对角线,次对角线占用信息的
int column // 比特位记录列被占用信息,如下图: 1001000表示 第1列和第4列被占用
int pie //表示左斜线,即次对角线的占用信息, 0010000,传递到第3行时,表示第3行3列位置不安全。
int na // 表示右斜线,即主对角线的占用信息,00101000
利用位运算 或,即可求得下一行的所有被占用的情况,运算结果如下图:
10111000 ,三个变量进行或运算,求出 1,3,4,5位置会被攻击,为0的位置是可以摆放皇后的
左斜线(pie)传递到下一行的约束推导,如下图, pie 与 当前行放置皇后位置求并集,再向左位移1位,即传递到下一行的左斜线约束
,同理,右斜线(na)求并集向右位移1位
所以公式如下:
p: 代表该行皇后摆放的位置,如 00000001
-
确定下一行可以哪些位置可以摆放皇后: cloumn | p
-
获取下一行左下斜被占用的情况: (pie | p) << 1
-
获取下一行右下斜被占用的情况: (na | p) >> 1
-
清除该行摆放皇后的位置: bits = bits & (bits - 1)
代码如下:
int totalNQueens(int n) { return backTrack(0,0,0,0,n); } //用于记录一共有多少种方式 private int count; public int backTrack(int row, int column, int pie, int na,int n) { if(row == n) { count++; return count; } /**下一行的可摆放的位置,1:代表可以摆放;0:不可以 * (column | pie | na),表示该行可以摆放的位置,此时 0 代表可以摆放,~ 取反方便下一步操作,1代表可以摆放 * 但是int类型 32 位,取反高位为1了,不需要,因此 (1<<n -1)按位与,抹去高位为0,只留下需要的n个低位 * 这里为什么要取反,1表示可以摆放的位置了,是为了方便bits与0比较 */ int bits = ~(column | pie | na) & ((1 << n) - 1); /** * 大于0,表示存在1,有可以摆放皇后的位置 */ while (bits > 0) { /** * 1,取出该行最右边的为1的那一位,表示可以摆放 * 涉及到计算机存储的是补码问题 */ int p = bits & -bits; backTrack(row + 1, column | p, (pie | p) << 1, (na | p) >> 1, n); /** * 抹去最右边为1的那位,将1变为0,继续从右遍历第二位为1的 */ bits = bits & (bits - 1); } return count; }
以上所述就是小编给大家介绍的《八皇后||算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- [经典算法]8皇后问题sql求解(回溯算法)
- 数据结构与算法(七):迷宫回溯和八皇后问题
- 八皇后问题分析和 golang 求解
- C语言解决八皇后问题代码及解析
- 一题征服面试官:N 皇后最优解
- 通俗易懂--决策树算法、随机森林算法讲解(算法+案例)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
How to Think Like a Computer Scientist: Learning with Python
Allen B. Downey、Jeffrey Elkner、Chris Meyers / Green Tea Press / 2002-1-4 / USD 24.95
""How to Think Like a Computer Scientist"" is an introduction to programming using Python, one of the best languages for beginners. This is a Free Book -- you can download it from thinkpython.com. But......一起来看看 《How to Think Like a Computer Scientist: Learning with Python》 这本书的介绍吧!