八皇后問題是一個以國際象棋為背景的問題：如何能夠在 8×8 的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處于同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變為n1×n1，而皇后個數也變成n2。而且僅當 n2 ≥ 1 或 n1 ≥ 4 時問題有解。

皇后問題是非常著名的問題，作為一個棋盤類問題，毫無疑問，用暴力搜索的方法來做是一定可以得到正確答案的，但在有限的運行時間內，我們很難寫出速度可以忍受的搜索，部分棋盤問題的最優解不是搜索，而是動態規劃，某些棋盤問題也很適合作為狀態壓縮思想的解釋例題。

進一步說，皇后問題可以用人工智能相關算法和遺傳算法求解，可以用多線程技術縮短運行時間。本文不做討論。

（本文不展開講狀態壓縮，以后再說）

?

一般思路：

?

N*N的二維數組，在每一個位置進行嘗試，在當前位置上判斷是否滿足放置皇后的條件（這一點的行、列、對角線上，沒有皇后）。

?

優化1：

?

既然知道多個皇后不能在同一行，我們何必要在同一行的不同位置放多個來嘗試呢？

我們生成一維數組record，record[i]表示第i行的皇后放在了第幾列。對于每一行，確定當前record值即可，因為每行只能且必須放一個皇后，放了一個就無需繼續嘗試。那么對于當前的record[i]，查看record[0...i-1]的值，是否有j = record[k]（同列）、|record[k] - j| = | k-i |（同一斜線）的情況。由于我們的策略，無需檢查行（每行只放一個）。

public class NQueens {public static int num1(int n) {if (n < 1) {return 0;}int[] record = new int[n];return process1(0, record, n);}public static int process1(int i, int[] record, int n) {if (i == n) {return 1;}int res = 0;for (int j = 0; j < n; j++) {if (isValid(record, i, j)) {record[i] = j;res += process1(i + 1, record, n);}}//對于當前行，依次嘗試每列return res;}
//判斷當前位置是否可以放置public static boolean isValid(int[] record, int i, int j) {for (int k = 0; k < i; k++) {if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {return false;}}return true;}public static void main(String[] args) {int n = 8;System.out.println(num1(n));}
}

優化2：

?

分析：棋子對后續過程的影響范圍：本行、本列、左右斜線。

黑色棋子影響區域為紅色

本行影響不提，根據優化一已經避免

本列影響，一直影響D列，直到第一行在D放棋子的所有情況結束。

?

左斜線：每向下一行，實際上對當前行的影響區域就向左移動

比如：

嘗試第二行時，黑色棋子影響的是我們的第三列；

嘗試第三行時，黑色棋子影響的是我們的第二列；

嘗試第四行時，黑色棋子影響的是我們的第一列；

嘗試第五行及以后幾行，黑色棋子對我們并無影響。

?

右斜線則相反：

隨著行序號增加，影響的列序號也增加，直到影響的列序號大于8就不再影響。

?

我們對于之前棋子影響的區域，可以用二進制數字來表示，比如:

每一位，用01代表是否影響。

比如上圖，對于第一行，就是00010000

嘗試第二行時，數字變為00100000

第三行：01000000

第四行：10000000

?

對于右斜線的數字，同理：

第一行00010000，之后向右移：00001000，00000100，00000010，00000001，直到全0不影響。

?

同理，我們對于多行數據，也同樣可以記錄了

比如在第一行我們放在了第四列：

第二行放在了G列，這時左斜線記錄為00100000（第一個棋子的影響）+00000010（當前棋子的影響）=00100010。

到第三行數字繼續左移：01000100，然后繼續加上我們的選擇，如此反復。

?

這樣，我們對于當前位置的判斷，其實可以通過左斜線變量、右斜線變量、列變量，按位或運算求出（每一位中，三個數有一個是1就不能再放）。

具體看代碼：

注：怎么排版就炸了呢。。。貼一張圖吧

public class NQueens {public static int num2(int n) {// 因為本方法中位運算的載體是int型變量，所以該方法只能算1~32皇后問題// 如果想計算更多的皇后問題，需使用包含更多位的變量if (n < 1 || n > 32) {return 0;}int upperLim = n == 32 ? -1 : (1 << n) - 1;//upperLim的作用為棋盤大小，比如8皇后為00000000 00000000 00000000 11111111//32皇后為11111111 11111111 11111111 11111111return 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;            //pos：所有的合法位置int mostRightOne = 0;   //所有合法位置的最右位置//所有記錄按位或之后取反，并與全1按位與，得出所有合法位置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.println(num2(n));}
}

完整測試代碼：

32皇后：結果/時間

暴力搜：時間就太長了，懶得測。。。

public class NQueens {public static int num1(int n) {if (n < 1) {return 0;}int[] record = new int[n];return process1(0, record, n);}public static int process1(int i, int[] record, int n) {if (i == n) {return 1;}int res = 0;for (int j = 0; j < n; j++) {if (isValid(record, i, j)) {record[i] = j;res += process1(i + 1, record, n);}}return res;}public static boolean isValid(int[] record, int i, int j) {for (int k = 0; k < i; k++) {if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {return false;}}return true;}public static int num2(int n) {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 = 32;long start = System.currentTimeMillis();System.out.println(num2(n));long end = System.currentTimeMillis();System.out.println("cost time: " + (end - start) + "ms");start = System.currentTimeMillis();System.out.println(num1(n));end = System.currentTimeMillis();System.out.println("cost time: " + (end - start) + "ms");}
}

?