【困难】N皇后问题－Java：解法二

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

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 */