【算法】【递归与动态规划模块】n皇后问题_n皇后 动态规划

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个数num，表示num x num 的棋盘，同时也代表存在n个皇后，在国际象棋中，皇后能够吃掉与其在同一斜线内，同一直线内的所有棋子，这里称为枪线，那么n个皇后如果共存于num x num 的棋盘中，那么有多少种共存的情况呢？
如果不能共存则返回0种情况，如 num = 2， num = 3 时，皇后们无法共存，结果为0

解决方案

原问题：
递归方法：
要素1：方法入参为 棋盘 map[num][num], 当前状态所在行数row
要素2：方法返回值 int，代表从map的row行开始放皇后一共有多少种情况
除了人工智能方法中的最优解（位运算）：
限制，位运算最多解决32个皇后
三个变量：map 代表总地图长度，为int类型，其中二进制表达中1表示能够放皇后，0表示不能放皇后。
record 代表当前状态下哪些列是否存在皇后，1表示已经有皇后，0表示没有皇后
leftR表示当前状态之前的所有状态放的皇后的左枪线，1代表存在枪线不能放皇后，0代表安全，可以放皇后
rightR表示当前状态之前的所有状态放的皇后的右枪线，1代表存在枪线不能放皇后，0代表安全，可以方皇后

首先通过位运算算出变量pos代表当前状态中可以放皇后的所有地方，1表示可放，0表示不能放。
遍历pos中为1的位，并累加种数即可，详情看代码

代码编写

java语言版本

原问题：
经典递归版本：

// 入口
    public static int nQCp1(int n) {
        if (n == 1) {
            return 1;
        }else if (n == 2 || n == 3) {
            return 0;
        }
        // record[i] 表示第i行的皇后在第几列
        int[] record = new int[n];
        return processCp1(record, 0);
    }

    private static int processCp1(int[] record, int row) {
        if (row == record.length) {
            // 遍历完成，返回一种情况
            return 1;
        }
        int res = 0;
        // 遍历当前行的每一个列，判断是否能放，如果能放入，则继续递归
        for (int i = 0; i < record.length; i ++) {
            if (canPut(record, i, row)) {
                // 继续递归
                record[row] = i;
                res += processCp1(record, row + 1);
            }
        }
        return res;
    }

    /**
     * 判断是否i位置能够放置皇后
     * @param record
     * @param i
     * @param row
     * @return
     */
    private static boolean canPut(int[] record, int i, int row) {
        for (int j = 0; j < row; j++) {
            // 获取j行皇后的位置
            int rRow = j;
            int rCol = record[j];
            if (rCol == i) {
                // 同列
                return false;
            }else if (Math.abs(row - rRow) == Math.abs(i - rCol)) {
                // 同斜线
                return false;
            }
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

经典动态规划版本：

    /**
     * 二轮测试：动态规划
     * @return
     */
    public static int dpCp1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] dp = new int[arr.length];
        dp[arr.length-1] = 0;
        for (int i = arr.length-2; i >= 0; i--) {
            int step = arr[i];
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= step; j++) {
                min = Math.min(min, dp[i+j]);
            }
            dp[i] = min + 1;
        }
        return dp[0];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最优解(位运算)：

    /**
     * 位运算版本
     *
     * @param n
     * @return
     */
    public static int nQCp2(int n) {
        if (n == 1) {
            return 1;
        }else if (n == 2 || n == 3) {
            return 0;
        }else if (n < 1 || n > 32) {
            return 0;
        }
        // 总地图长度
        int map = n == 32 ? -1 : (1 << n) - 1;
        return processCp2(map, 0, 0, 0);
    }

    /**
     * 递归主体
     * @param map 总地图，位中1表示可以放皇后的位置。0表示不能
     * @param record 当前记录，1表示已经放皇后了，0表示没有放皇后
     * @param leftRecord 当前记录，1表示通过前面的计算传承下来的左斜线中不能放的位置
     * @param rightRecord 当前记录，1表示通过前面计算传承下来的右斜线中不能放的位置
     * @return
     */
    private static int processCp2(int map, int record, int leftRecord, int rightRecord) {
        if (record == map) {
            // 说明已经放满了
            return 1;
        }
        // 已经有皇后枪线的地方全部是1，然后取反，枪线变0，与操作后，pos中0的地方都是枪线 没法放皇后
        int pos = map & (~(record | leftRecord | rightRecord));
        int res = 0;
        int thrMostRight = 0;
        while (pos != 0) {
            // 最右边的1，整体是从右往左遍历的
            thrMostRight = pos & (~pos + 1);
            pos -= thrMostRight;
            res += processCp2(map,
                    // record添加当前位置
                    record | thrMostRight,
                    // 左边的加上当前位置整体左一位
                    (leftRecord | thrMostRight) << 1,
                    // 右边的加上当前位置整体右一位，记得无符号移位
                    (rightRecord | thrMostRight) >>> 1);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

n皇后问题大学的时候算法课上有了解过，但是到现在才知道如何解决，惭愧。这道题我的电脑在16皇后的时候普通递归已经2分钟+都算不出来答案。但是位运算8秒，这里是我第一次感受到算法优化之后对性能的提升如此之大，大家感兴趣可以cp下来自己测试一下，真的很神奇。我发现，其中 int pos = map & (~(record | leftRecord | rightRecord)); 这一句位运算可以代替我们递归的一次完整的位置判断循环，不需要遍历每一个位置判断是否能够写入。
其实我刚开始想这个问题的时候想用三维数组，num x num x 3 的三维数组，主要就是想把每一个位置都记录下来三个信息，1、是否在皇后直枪线上？2、是否在皇后的左枪线上？3、是否在皇后的右枪线上。这样的话每一个状态只需要参考上一层的数据就能够推算出当前行的可行位置，其实就是位运算中的 record，leftR和rightR。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！