八皇后||算法

栏目: IT技术 · 发布时间: 4年前

内容简介:八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8个格子的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后, 为了达到此目的,八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当

一、背景

八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8个格子的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后, 为了达到此目的, 任两个皇后都不能处于同一条横行、纵行或斜线上 (中国象棋,车可以走横线,纵线),问有多少种摆法,高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以编程解决此问题。

八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。

当且仅当 n = 1n ≥ 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。

注:正数的原码,反码,补码相同,计算机中运算是以补码的形式存储计算的。

本次算法相关:

  1. x & -x : 该运算只保留x最右边的第一个1 ,其余置为0。
    例如:x= 00110110, -x = 10110110 (负值是符号位取反,其他位不变), x的补码还是其原码,-x的补码是反码+1
    即 01001001 (反码) +1 = 01001010,两数按位与计算结果
    00110110
    01001010
    =00000010
  2. 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

  1. 确定下一行可以哪些位置可以摆放皇后: cloumn | p

  2. 获取下一行左下斜被占用的情况: (pie | p) << 1

  3. 获取下一行右下斜被占用的情况: (na | p) >> 1

  4. 清除该行摆放皇后的位置: 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;
    }

以上所述就是小编给大家介绍的《八皇后||算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

How to Think Like a Computer Scientist: Learning with Python

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》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换