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皇后問題比較難，尤其是用位運算優化比較難理解，博主費心寫下這篇文章做個記錄，因為有的面試官可能會問到這些經典的問題，
感謝您的三連或點贊評論支持🙇?🙇?🙇?
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/396247.html
標籤：其他
上一篇：nginx+tomcat+redis*+mysql（redis重點）
下一篇：R語言str_sub函式從字串中提取或替換子字串（substring）：str_sub函式指定起始位置和終止位置抽取子字符、str_sub函式指定起始位置和終止位置替換子字串