N皇后
N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1。n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。n=8，返回92
N皇后游戏原则：
- 不能在同一行
- 不能在同一列
- 不能在同一条斜线上（左右斜线都不行）
现在我们来分析题目：
在一行上每次只摆一个皇后，从左往右开始摆，每一行都如此。并且记下这个皇后的位置。后续行数摆的时候只用避免共列和共斜线的问题。如果到某一行发现违反规则，那就退回上一行重新摆，将皇后右移一个位置，后续行数再接着递归。
如何记录皇后的位置，也就是记录皇后的坐标（x,y），只需要用一个数组既可。比如recored[7]=13，代表第7行的皇后在第13列；record[0]=3代表第0行的皇后在第3列。
如何检测皇后是否冲突，共行问题不用考虑，因为一开始我们就规定每一行都是只摆放一个。假设有两个皇后的位置如下：
(a,b) 和 (c,d)
不共列：b != d
不共斜线：|a-c| != |b-d|
如果i来到了第n行，那就说明越界了，并且隐含的条件是之前行的摆放都有效，所以可以返回一种摆放结果。
如果没有来到第n行，说明当前行可以摆放皇后，那么就尝试这一行上所有的列，看是否与0~i-1行的皇后冲突。 如果不冲突，就记录好这一行皇后的位置并且去下一行递归；如果冲突就跳到下一列。
// 尝试i行上所有的列（0~n-1列） // 如果当前i行的皇后，放在第j列， // 不会和之前行（0~i-1行）的皇后冲突（不共行&&不共列&&不公斜线） // 那放第j列可以，认为有效，接着去i+1行递归 // 否则，无效，放下一列 for(int j=0; j<n; j++) { if(isValid(record, i, j)) {// record记录的是0~i-1行皇后的位置 record[i]=j;// 第i行的皇后在第j列 ans+=process1(i+1, record, n); // 因为在每一行都是直接改要放的列数，所以无需恢复现场 } }
完整代码：
package com.harrison.class12; public class Code08_NQueens { // 0~i-1行的皇后位置都摆放好了，不用再考虑，并且符合要求：不共行、不共列、不共斜线 // i 表示当前来到第i行摆皇后 // record[0~i-1] 存放摆好的记录 // record[0]=3 -> 第0行皇后摆在第3列 // n 表示一共有多少行（0~n-1行），如果来到n行就越界了 // 在[0~i-1]行皇后都摆好的情况下， // 返回i及其后面行数摆放有效的方式有多少种（整个棋盘都摆好） public static int process1(int i,int[] record,int n) { // 如果i来到终止行，说明之前行数的摆放都有效， // 返回一种合理的摆放方式 if(i==n) { return 1; } // 如果i没有到终止行，那么当前行可以摆 int ans=0; // 尝试i行上所有的列（0~n-1列） // 如果当前i行的皇后，放在第j列， // 不会和之前行（0~i-1行）的皇后冲突（不共行&&不共列&&不公斜线） // 那放第j列可以，认为有效，接着去i+1行递归 // 否则，无效，放下一列 for(int j=0; j<n; j++) { if(isValid(record, i, j)) {// record记录的是0~i-1行皇后的位置 record[i]=j;// 第i行的皇后在第j列 ans+=process1(i+1, record, n); // 因为在每一行都是直接改要放的列数，所以无需恢复现场 } } return ans; } // record[0~i-1]的皇后需要看，第i行的皇后不需要 // 返回第i行皇后放在了第j列是否有效 public static boolean isValid(int[] record,int i,int j) { for(int k=0; k<i; k++) {// 0~i-1行的某一行的皇后，假设是第k行的皇后 if(record[k]==j || (Math.abs(record[k]-j)==Math.abs(i-k))) { return false; } } return true; } public static int nums1(int n) { if(n<1) { return 0; } int[] record=new int[n];// record[i] i行的皇后 放在了第几列 return process1(0, record, n); } public static void main(String[] args) { int n=8; long start=System.currentTimeMillis(); System.out.println(nums1(n)); long end=System.currentTimeMillis(); System.out.println("cost time："+(end-start)+"ms"); } }
上面这种方法对于解决N皇后问题在如何尝试的方式上已经是最优的了，如果我们不去搞学术的话，对于工作尝试到这里就可以了，但是！！！不知道大家知不知道位运算是比普通运算快很多的呢？所以我们还可以在常数项方面优化一下，但是注意：用位运算优化后的时间复杂度还是跟原来一样，只是在常数项方面进行了优化，但这么一优化还是快了很多的，请接着往下看。
我们把N皇后问题中的列想象成一个正整数的二进制位。什么意思，比如，8皇后问题就只用最后面的八个二进制位；9皇后问题就只用最后面九个二进制位，，，依次类推。如果在哪一列放了皇后，就将该二进制位设为1（一开始全部为0）。也就是说，1代表放了皇后，0代表没有放。
比如8皇后，在第一行的第二列摆了皇后，
那么就是 01000000
当然，在Java里面，int是只占4个字节的整型，所以最多也只有32个二进制位，所以，用这种方式的话，不能超过32个皇后，因为摆不下。
注意：以下文字描述都是以8皇后举例子！！！
那么，当前行如何知道在哪该放皇后呢？主要看两点，第一，当前行是不是跟之前行的皇后共列，第二，之前行的皇后的左右斜线贯穿的位置，当前行不能放。
所以，接下来准备三个变量，列限制columnLimit，左斜线限制leftLimit，右斜线限制rightLimit。
columnLimit：00000000
leftLimit：00000000
rightLimit：00000000
在第一行的时候，是没有任何限制的，那就可以随便放。
假如放在第4列（下标从0开始算），那么上述三个变量就会变成：
columnLimit：00001000
leftLimit：00010000（columnLimit往左移一位）
rightLimit：00000100（columnLimit往右移一位）
ok，第i行上的皇后放好了，那么如何知道第i+1行上哪些列可以放皇后呢？
上述三个变量一起做或运算的结果就是总的限制：假设第i行第4列放了皇后（下标从0开始算），columnLimit | leftLimit |rightLimit 结果就是：00011100，代表第i+1行上第3、4、5列都不可以再放了。
00001000
00010000
00000100
00011100
好的，那么当前情况就是00011100， 0的位置还可以放皇后，所以每个位置都会去尝试一遍。
假设又在第1列放了个皇后(01000000)，那么对于i+1行来说，此时的列限制 columnLimit 就是 01001000（之前是00001000），左斜线限制就是 10100000，右斜线限制就是 00100010。不仅受上一行列限制的影响，而且受之前所有行延申的左右斜线的影响。
给大家画个图加深理解：
那接下来对于i+1行的下一行的限制就是 上面三个变量一起做或运算后的答案——11101010，只能在剩下的三个零上放皇后。
01001000
10100000
00100010
11101010
处理完三个变量后，继续往下这么玩。。。
补充知识：如何提取二进制数中最右侧的1， => int Ans=N&((~N)+1)，请参考这篇文章——利用异或运算的性质进行骚操作。
两种方法的完整代码：
package com.harrison.class12; public class Code08_NQueens { // 0~i-1行的皇后位置都摆放好了，不用再考虑，并且符合要求：不共行、不共列、不共斜线 // i 表示当前来到第i行摆皇后 // record[0~i-1] 存放摆好的记录 // record[0]=3 -> 第0行皇后摆在第3列 // n 表示一共有多少行（0~n-1行），如果来到n行就越界了 // 在[0~i-1]行皇后都摆好的情况下， // 返回i及其后面行数摆放有效的方式有多少种（整个棋盘都摆好） public static int process1(int i,int[] record,int n) { // 如果i来到终止行，说明之前行数的摆放都有效， // 返回一种合理的摆放方式 if(i==n) { return 1; } // 如果i没有到终止行，那么当前行可以摆 int ans=0; // 尝试i行上所有的列（0~n-1列） // 如果当前i行的皇后，放在第j列， // 不会和之前行（0~i-1行）的皇后冲突（不共行&&不共列&&不公斜线） // 那放第j列可以，认为有效，接着去i+1行递归 // 否则，无效，放下一列 for(int j=0; j<n; j++) { if(isValid(record, i, j)) {// record记录的是0~i-1行皇后的位置 record[i]=j;// 第i行的皇后在第j列 ans+=process1(i+1, record, n); // 因为在每一行都是直接改要放的列数，所以无需恢复现场 } } return ans; } // record[0~i-1]的皇后需要看，第i行的皇后不需要 // 返回第i行皇后放在了第j列是否有效 public static boolean isValid(int[] record,int i,int j) { for(int k=0; k<i; k++) {// 0~i-1行的某一行的皇后，假设是第k行的皇后 if(record[k]==j || (Math.abs(record[k]-j)==Math.abs(i-k))) { return false; } } return true; } public static int nums1(int n) { if(n<1) { return 0; } int[] record=new int[n];// record[i] i行的皇后 放在了第几列 return process1(0, record, n); } public static int nums2(int n) { if(n<1 || n>32) { return 0; } // n==8 limit最右边8个1，其余全是0 // n==9 limit最右边9个1，其余全是0 // n==32 最右边32位全是1 -> 十进制-1 // n!=32 1左移n位再减一 // 比如n==8 limit=100000000-00000001 -> 11111111 int limit=n==32?-1:((1<<n)-1); // 一开始第0行的时候，没有任何限制 return process2(limit, 0, 0, 0); } // limit 划定了问题的规模，是固定不变的参数 public static int process2(int limit,int columnLimit,int leftLimit,int rightLimit) { if(columnLimit==limit) {// base case return 1; } // pos 当前行可以放皇后的位置 1：不能放 0：可以放 // (columnLimit | leftLimit | rightLimit ) 总限制 // 为什么要 & limit // 1）~(columnLimit | leftLimit | rightLimit ) 左侧的一坨0取反后变成1会干扰 // 2）左斜线限制会越界，右斜线不会 int pos=limit&(~(columnLimit | leftLimit | rightLimit )); int ans=0; int mostRightOne=0; // 尝试pos上的每一个1 while(pos!=0) { mostRightOne=pos & ((~pos)+1); pos=pos-mostRightOne; ans+=process2(limit, columnLimit | mostRightOne, (leftLimit | mostRightOne)<<1, (rightLimit | mostRightOne)>>>1); } return ans; } public static void main(String[] args) { int n=13; long start=System.currentTimeMillis(); System.out.println(nums1(n)); long end=System.currentTimeMillis(); System.out.println("cost time："+(end-start)+"ms"); start=System.currentTimeMillis(); System.out.println(nums2(n)); end=System.currentTimeMillis(); System.out.println("cost time："+(end-start)+"ms"); } }
两种方法的时间复杂度都是O(N^N)。
但是用位运算优化后，还是肉眼可见的快。
以下是13皇后的测试结果，
N皇后问题比较难，尤其是用位运算优化比较难理解，博主费心写下这篇文章做个记录，因为有的面试官可能会问到这些经典的问题。
感谢您的三连或点赞评论支持????????????