随笔记录

算法-N皇后问题（含加速版本）

2022-4-20 diaba 算法

package com.jiucaiyuan.net.question;

/**
 * 【问题】N皇后问题,指的是n*n的棋盘，可以放n个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上
 * 给出一个整数n，返回n皇后的摆法有多少种
 * 给n=1，返回1
 * n=2或者3，2皇后和3皇后，无论怎么摆放都不行，返回0
 * n=8，返回92
 * 【思路】按照行往下摆放，然后一列一列尝试（加速版本会使用按照位操作来加速器处理，但是整体上也是所有都尝试一遍）
 * 时间复杂度O(N^N)
 *
 * @Author jiucaiyuan  2022/4/19 23:26
 * @mail services@jiucaiyuan.net
 */
public class NQueens {
    /**
     * @param n 皇后数
     * @return 摆放种数
     */
    public static int nQueens(int n) {
        System.out.println("--------------" + n + "----------------------");
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n]; //record[i] i行的皇后放到第几列上
        return process1(0, record, n);
    }

    /**
     * @param i      当前处理第i行元素
     * @param record record[0~i-1]表示之前的行，放了皇后的位置，不共行、不共列、不共斜线
     * @param n      总共有多少行（皇后个数）
     * @return i行的摆法
     */
    public static int process1(int i, int[] record, int n) {
        if (i == n) {
            print(record);
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            //当前i行的皇后放到j列，会不会和之前i-1个皇后共列、共斜线
            //如果是，无效，如果不是，有效
            if (isValid(record, i, j)) {
                record[i] = j;
                res += process1(i + 1, record, n);
            }
        }
        return res;
    }

    /**
     * 检查是否存在共列、共斜线情况（不可能有共行情况，因为是一行一行处理的）
     *
     * @param record record[k] 表示k行摆放在record[k]列  0<=k<=i-1
     * @param i      当前放到i行
     * @param j      i行放到j列
     * @return 是否和之前的有共列、共斜线情况
     */
    public static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            if (record[k] == j  //共列
                    || Math.abs(k - i) == Math.abs(record[k] - j)  //共斜线
            ) {
                return false;
            }
        }
        return true;
    }

    private static void print(int[] record) {
        System.out.print(record[0]);
        for (int i = 1; i < record.length; i++) {
            System.out.print("," + record[i]);
        }
        System.out.println();
    }

    /**
     * <pre>
     * n皇后问题（加速版本）
     * 【适用范围】由于限制用的是int类型值来表示，所以支持n<=32
     * 【加速思路】：未加速版本是通过一个数组记录已经放置皇后，再放置时检查是否和已经放置的
     * 共行、共列、共斜线，加速版本思路也是要检查是否共行、共列、共斜线，不过是每次处理
     * 时往下传入列限制、左斜线限制、右斜线限制，其中这些限制是通过二进制运算得到，达到
     * 加速的效果
     * 【限制规则】：1的位置不能放皇后，0的位置可以
     * 列限制 | 左斜线限制 | 右斜线限制 = 总限制
     * colLim | leftDiaLim | rightDiaLim
     * </pre>
     *
     * @param n 皇后个数
     * @return 返回摆法的种数
     */
    public static int nQueens2(int n) {
        if (n < 1 || n > 32) {
            System.out.println("加速方法的处理不支持超过32个皇后");
            return 0;
        }
        //因为是32位，所以用upperLim来标识当前指定的是皇后个数，即22皇后时，upperLim值是 00000000001111111111111111111111
        //右侧1的个数就是当前皇后个数
        //(1<<n)-1 得到的是后面n个1，前面全是0
        int upperLim = n == 32 ? -1 : (1 << n) - 1;
        return process2(upperLim, 0, 0, 0);
    }

    /**
     * <pre>
     * 【加速思路】：未加速版本是通过一个数组记录已经放置皇后，再放置时检查是否和已经放置的
     * 共行、共列、共斜线，加速版本思路也是要检查是否共行、共列、共斜线，不过是每次处理
     * 时往下传入列限制、左斜线限制、右斜线限制，其中这些限制是通过二进制运算得到，达到
     * 加速的效果
     * 【限制规则】：1的位置不能放皇后，0的位置可以
     * 列限制 | 左斜线限制 | 右斜线限制 = 总限制
     * colLim | leftDiaLim | rightDiaLim
     * </pre>
     *
     * @param upperLim
     * @param colLim      列的限制
     * @param leftDiaLim  左斜线的限制
     * @param rightDiaLim 右斜线的限制
     * @return
     */
    public static int process2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == upperLim) {//列限制信息和皇后数一致了，即放完了所有皇后
            return 1;
        }
        int pos = 0;  //可以放皇后的位置
        int mostRightOne = 0;
        //colLim | leftDiaLim | rightDiaLim  总限制
        //~(colLim | leftDiaLim | rightDiaLim)  可以放皇后的位置
        //pos 指定n个皇后时可以放皇后的位置
        pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
        int res = 0;
        while (pos != 0) {
            mostRightOne = pos & (~pos + 1);//按照二进制的方式表示pos，取到pos最右侧的1在哪个位置
            pos = pos - mostRightOne;  //每次减去最右侧一个1（当前循环尝试了），即按照这种方式来尝试所有可以尝试的次数
            res += process2(upperLim,
                    colLim | mostRightOne,  //当前处理的位置加入下次尝试的列限制中
                    (leftDiaLim | mostRightOne) << 1,  //左侧限制向左侧移动一位作为下次尝试的左侧限制
                    (rightDiaLim | mostRightOne) >>> 1);// 右侧限制向右侧移动一位作为下次尝试的右侧限制
        }
        return res;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(nQueens(1));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(2));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(3));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(4));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(5));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(6));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(7));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(8));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(10));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(11));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens(15));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(nQueens2(15));
        System.out.println("耗时=" + (System.currentTimeMillis() - start));
    }
}