【算法】【递归与动态规划模块】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++语言版本