【困难】N皇后问题－Java：解法二_javan 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后;编写代码:求给一个整数 n ,返

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程

package live.every.day.ProgrammingDesign.CodingInterviewGuide.RecursionAndDynamicPrograming;
 
/**
 * N皇后问题
 *
 * 【题目】
 * N皇后问题是指在NxN的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。给定一个整数n，返回n皇后的
 * 摆法有多少种。
 *
 * 【难度】
 * 困难
 *
 * 【解答】
 * 下面介绍最优解，基本过程与上面的方法一样，但使用了位运算来加速。具体加速的递归过程中，找到每一行还有哪些位置可以放置皇
 * 后的判断过程。因为整个过程比较超自然，所以先列出代码，然后对代码进行解释，请参看如下代码中的num2方法。
 *
 * num2方法中，变量upperLim表示当前行哪些位置是可以放置皇后的，1代表可以放置，0代表不能放置。8皇后问题中，初始时
 * upperLim为00000000000000000000000011111111，即32位整数的255。32皇后问题中，初始时upperLim为
 * 11111111111111111111111111111111，即32位整数的-1。
 *
 * 接下来解释一下process2方法，先介绍每个参数。
 * upperLim：已经解释过了，而且这个变量的值在递归过程中是始终不变的。
 * colLim：表示递归计算到上一行为止，在哪些列上已经放置了皇后，1代表已经放置，0代表没有放置。
 * leftDiaLim：表示递归计算到上一行为止，因为受已经放置的所有皇后的左下方斜线的影响，导致当前行不能放置皇后，1代表不能
 * 放置，0代表可以放置。举个例子，如果在第0行第4列放置了皇后。计算到第1行时，第又行皇后的左下方斜线影响的是第1行第了列。
 * 当计算到第2行时，第又行皇后的左下方斜线影响的是第2行第2列。当计算到第3行时，影响的是第了行第1列。当计算到第4行时，影响
 * 的是第4行第0列。当计算到第5行时，第0行的那个皇后的左下方斜线对第5行无影响，并且之后的行都不再受第0行皇后左下方斜线的
 * 影响。也就是说，lentDiaLim每次左移一位，就可以得到之前所有皇后的左下方斜线对当前行的影响。
 * rightDiaLim：表示递归计算到上一行为止，因为已经放置的所有皇后的右下方斜线的影响，导致当前行不能放置皇后的位置，1代表
 * 不能放置，0代表可以放置。与leftDiaLim变量类似，rightDiaLim每次右移一位就可以得到之前所有皇后的右下方斜线对当前行的
 * 影响。
 *
 * process2方法的返回值代表剩余的皇后在之前皇后的影响下，有多少种合法的摆法。其中，变量pos代表当前行在colLim、
 * lefDiaLim和rightDiaLim这三个状态的影响下，还有哪些位置是可供选择的，1代表可以选择，0代表不能选择。变量
 * mostRightOne代表在pos中，最右边的1是在什么位置。然后从右到左依次筛选出pos中可选择的位置进行递归尝试。
 *
 * @author Created by LiveEveryDay
 */
public class NQueen2 {
 
    public static int num2(int n) {
        // 因为本方法中位运算的载体是int型变量，所以该方法只能算1~32皇后问题
        // 如果想计算更多的皇后问题，需使用包含更多位的变量
        if (n < 1 || n > 32) {
            return 0;
        }
        int upperLim = n == 32 ? -1 : (1 << n) - 1;
        return process2(upperLim, 0, 0, 0);
    }
 
    public static int process2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == upperLim) {
            return 1;
        }
        int pos = 0;
        int mostRightOne = 0;
        pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
        int res = 0;
        while (pos != 0) {
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;
            res += process2(upperLim,
                    colLim | mostRightOne,
                    (leftDiaLim | mostRightOne) << 1,
                    (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }
 
    public static void main(String[] args) {
        int n = 8;
        System.out.printf("The number is: %d", num2(n));
    }
 
}
 
// ------ Output ------
/*
The number is: 92
*/