本文的网课内容学习自B站左程云老师的算法详解课程，旨在对其中的知识进行整理和分享~

网课链接：算法讲解040【必备】N皇后问题-重点是位运算的版本_哔哩哔哩_bilibili

一.N皇后问题

题目：N 皇后 II

算法原理

①基于数组表示路径的方法

• 整体思路

  • 采用递归的方式逐行放置皇后，对于每一行，尝试在每一列放置皇后，通过检查是否与之前放置的皇后冲突来确定该位置是否可行。如果可行，则继续递归放置下一行的皇后，直到所有行都放置了皇后或者无法再放置皇后。

• 具体步骤

  • 主函数totalNQueens1
    • 如果n小于1，直接返回0，表示没有可行的放置方案。否则，调用f1函数从第0行开始放置皇后，传入初始的空路径（用一个长度为n的数组表示，初始值未设定，在f1函数中逐步确定）和n（皇后数量）。
  • f1函数
    • 递归终止条件：当i（当前行）等于n时，表示已经成功放置了所有n个皇后，返回1，表示找到一种有效的放置方案。
    • 尝试放置皇后：通过一个循环遍历当前行的每一列（j从0到n - 1）。对于每一列，调用check函数检查在i行j列放置皇后是否与之前放置的皇后冲突。如果不冲突（check函数返回true），则将皇后放置在i行j列（path[i]=j），然后递归调用f1函数处理下一行（i + 1），并将返回值累加到ans中。
  • check函数
    • 遍历0到i - 1行（k），检查当前位置（i行j列）与之前放置的皇后（k行path[k]列）是否在同一列（j == path[k]）或者在同一对角线上（Math.abs(i - k) == Math.abs(j - path[k])）。如果存在冲突，则返回false；如果没有冲突，则返回true。

代码实现 

// N皇后问题
// 测试链接 : https://leetcode.cn/problems/n-queens-ii/
public class NQueens {

    // 用数组表示路径实现的N皇后问题，不推荐
    public static int totalNQueens1(int n) {
        if (n < 1) {
            return 0;
        }
        return f1(0, new int[n], n);
    }

    // i : 当前来到的行
    // path : 0...i-1行的皇后，都摆在了哪些列
    // n : 是几皇后问题
    // 返回 : 0...i-1行已经摆完了，i....n-1行可以去尝试的情况下还能找到几种有效的方法
    public static int f1(int i, int[] path, int n) {
        if (i == n) {
            return 1;
        }
        int ans = 0;
        // 0 1 2 3 .. n-1
        // i j
        for (int j = 0; j < n; j++) {
            if (check(path, i, j)) {
                path[i] = j;
                ans += f1(i + 1, path, n);
            }
        }
        return ans;
    }

    // 当前在i行、j列的位置，摆了一个皇后
    // 0...i-1行的皇后状况，path[0...i-1]
    // 返回会不会冲突，不会冲突，有效！true
    // 会冲突，无效，返回false
    public static boolean check(int[] path, int i, int j) {
        // 当前 i
        // 当列 j
        for (int k = 0; k < i; k++) {
            // 0...i-1
            // 之前行 : k
            // 之前列 : path[k]
            if (j == path[k] || Math.abs(i - k) == Math.abs(j - path[k])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 14;
        long start, end;
        System.out.println("测试开始");
        System.out.println("解决" + n + "皇后问题");
        start = System.currentTimeMillis();
        System.out.println("方法1答案 : " + totalNQueens1(n));
        end = System.currentTimeMillis();
        System.out.println("方法1运行时间 : " + (end - start) + " 毫秒");

      
    }

}

②基于位信息表示路径的方法

• 整体思路

  • 利用位运算来表示皇后的放置位置和相互之间的影响关系。通过位运算快速判断哪些位置可以放置皇后，减少了不必要的比较操作，提高了效率。

• 具体步骤

  • 主函数totalNQueens2
    • 如果n小于1，返回0。然后计算一个limit值，它是一个二进制数，其中低n位为1，其余位为0，表示所有可能放置皇后的位置。调用f2函数开始放置皇后，传入limit、初始的列影响（0，表示没有皇后放置）、初始的右上到左下对角线影响（0）和初始的左上到右下对角线影响（0）。
  • f2函数
    • 递归终止条件：当col（表示已经放置皇后的列的位信息）等于limit时，意味着所有皇后都已放置完毕，返回1，表示找到一种有效的放置方案。
    • 计算可放置位置：通过ban = col | left | right计算出被禁止放置皇后的位置（由于之前放置的皇后在列、右上到左下对角线和左上到右下对角线的影响）。然后candidate = limit & (~ban)计算出当前可以放置皇后的位置（通过取limit和ban的补集的交集）。
    • 尝试放置皇后：通过一个循环，当candidate不为0时，每次提取出candidate最右侧的1（place = candidate & (-candidate)），表示一个可放置皇后的位置。然后将这个位置从candidate中移除（candidate ^= place），并递归调用f2函数，更新col（将放置皇后的位置添加到已放置皇后的列信息中，col | place）、left（将放置皇后的位置对右上到左下对角线的影响更新，(left | place) >> 1）和right（将放置皇后的位置对左上到右下对角线的影响更新，(right | place) << 1），并将返回值累加到ans中。

代码实现

// N皇后问题
// 测试链接 : https://leetcode.cn/problems/n-queens-ii/
public class NQueens {
    // 用位信息表示路径实现的N皇后问题，推荐
    public static int totalNQueens2(int n) {
        if (n < 1) {
            return 0;
        }
        // n = 5
        // 1 << 5 = 0...100000 - 1
        // limit  = 0...011111;
        // n = 7
        // limit  = 0...01111111;
        int limit = (1 << n) - 1;
        return f2(limit, 0, 0, 0);
    }

    // limit : 当前是几皇后问题
    // 之前皇后的列影响：col
    // 之前皇后的右上 -> 左下对角线影响：left
    // 之前皇后的左上 -> 右下对角线影响：right
    public static int f2(int limit, int col, int left, int right) {
        if (col == limit) {
            // 所有皇后放完了！
            return 1;
        }
        // 总限制
        int ban = col | left | right;
        // ~ban : 1可放皇后，0不能放
        int candidate = limit & (~ban);
        // 放置皇后的尝试！
        int place = 0;
        // 一共有多少有效的方法
        int ans = 0;
        while (candidate != 0) {
            // 提取出最右侧的1
            // 0 0 1 1 1 0
            // 5 4 3 2 1 0
            // place :
            // 0 0 0 0 1 0
            // candidate :
            // 0 0 1 1 0 0
            // 5 4 3 2 1 0
            // place :
            // 0 0 0 1 0 0
            // candidate :
            // 0 0 1 0 0 0
            // 5 4 3 2 1 0
            // place :
            // 0 0 1 0 0 0
            // candidate :
            // 0 0 0 0 0 0
            // 5 4 3 2 1 0
            place = candidate & (-candidate);
            candidate ^= place;
            ans += f2(limit, col | place, (left | place) >> 1, (right | place) << 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        int n = 14;
        long start, end;
        System.out.println("测试开始");
        System.out.println("解决" + n + "皇后问题");
     

        start = System.currentTimeMillis();
        System.out.println("方法2答案 : " + totalNQueens2(n));
        end = System.currentTimeMillis();
        System.out.println("方法2运行时间 : " + (end - start) + " 毫秒");
        System.out.println("测试结束");

        System.out.println("=======");
        System.out.println("只有位运算的版本，才能10秒内跑完16皇后问题的求解过程");
        start = System.currentTimeMillis();
        int ans = totalNQueens2(16);
        end = System.currentTimeMillis();
        System.out.println("16皇后问题的答案 : " + ans);
        System.out.println("运行时间 : " + (end - start) + " 毫秒");
    }

}