八皇后問題是一個經(jīng)典的遞歸回溯問題蜗字。
描述
八皇后問題是在一個 8*8 的棋盤上放置皇后，要求其放置后滿足同一行铅辞，同一列埋酬，同一對角線上沒有重復(fù)的皇后出現(xiàn)哨啃。試問有多少種擺盤方式？
思路
我們的主要思路是通過一行一行的放置皇后写妥，來使得每一行都有一個皇后拳球。當然，這些皇后在放置時都必須要滿足規(guī)定的要求才行珍特。
因此就會出先如下情況:
- 放置時不符合規(guī)則祝峻，繼續(xù)檢索同一行的下一列位置是否合理
- 如果符合規(guī)則就將其放置，然后進行下一行的嘗試（遞歸）
- 如果有某一行沒有可行的解扎筒，則退回上一行莱找，消除上一行擺放的皇后，檢索剩余的列嗜桌，看是否有合理的位置奥溺，然后繼續(xù)進行。(回溯)
- 直到所有的行都被放置為止骨宠。
需要注意的是浮定，我們在放置皇后時需要檢測其防止和理性的判斷條件為:
- 同一列的上方所有行中是否有皇后
- 左上方對角線上是否有皇后
- 右上方對角線上是否有皇后
算法實現(xiàn)
public class EightQueen {
private static final int num = 8; // 可以拓展為N皇后問題
private static int[][] item = new int[num][num];
private static int methods = 0; // 總方法數(shù)
public static void main(String[] args) {
buildQueen(0);
System.out.println(methods);
}
/**
* 構(gòu)建棋盤的第row行
*
* @param row
*/
private static void buildQueen(int row) {
if (row == num) {
methods++;
// System.out.println("第" + methods + "種解法:");
// for (int i = 0; i < num; i++) {
// for (int j = 0; j < num; j++) {
// System.out.print(item[i][j] + " ");
// }
// System.out.print("\n");
// }
return;
} else {
for (int col = 0; col < num; col++) { // 每一列進行檢查相满，試探性放置
if (isSatisfy(row, col)) {
item[row][col] = 1;
buildQueen(row + 1);
item[row][col] = 0;
}
}
}
}
/**
* 檢查row行col列元素是否滿足要求
* 因為是一行行的放置皇后，所以不需要檢測同一行是否存在重復(fù)皇后
* 在判斷重復(fù)元素時桦卒，只需要判斷上半部分的區(qū)域即可
*
* @param row
* @param col
* @return
*/
private static boolean isSatisfy(int row, int col) {
for (int i = 0; i < row; i++) {
if (item[i][col] == 1) { // 同一列的上方元素
return false;
}
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) { // 左上方斜對角線
if (item[i][j] == 1) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j < num; i--, j++) { // 右上方斜對角線
if (item[i][j] == 1) {
return false;
}
}
return true;
}
}
優(yōu)雅的位運算解法
我們直接從一個例子來講解思路吧立美。先看看下圖的情況：
我們可以看到，前三行已經(jīng)放置了皇后方灾，我們需要在第四行選擇放置皇后的點建蹄。陰影部分表示會出現(xiàn)沖突的格子，而沖突我們主要分為三種：同列沖突迎吵、右下方?jīng)_突和左下方?jīng)_突躲撰。
而就這對這種情況而言(此例為八皇后問題，可拓展到N皇后)击费，一行剛好8個格子，對應(yīng)8位二進制數(shù)字桦他。因此我們可以首先定義沖突:
同列沖突: A = 1000 1001蔫巩；
右下沖突: B = 0001 0010；
左下沖突: C = 0010 0010快压；
其中1表示沖突的格子圆仔，0表示可以放置皇后的格子。因此我們可以輕松得出綜合的沖突情況：
D = (A | B | C) = 1011 1011蔫劣；
對于我們將要放置的第四行而言坪郭，現(xiàn)在有兩個0，意味著有兩個可以放置皇后的位置脉幢，我們需要將所有的情況都考慮到歪沃，這里有一個神奇的式子：bit = (D + 1) & ~D; 它計算得出的結(jié)果是: 0000 0100;
其實它能夠得到最右邊一個可以放置皇后的位置，并用1來表示嫌松，其余位是0沪曙。 這樣做是有好處的...
我們現(xiàn)在得出 bit = 0000 0100，便能夠輕松得到下一行的沖突 A' = (A | bit); B' = (B | bit) >> 1; C' = (C | bit) << 1; 便能夠很輕易地寫出遞歸式了萎羔。
而我們的第4行試探其實并沒有結(jié)束液走，只是從左向右的第一個可以放置的位置進行了試探，那想要取到第二個可以放置的位置怎么辦呢贾陷？很簡單缘眶，只需要做如下運算：
D = D + bit 將剛才試過的那一位設(shè)置為不能放置皇后狀態(tài)，然后繼續(xù)做 bit = (D + 1) & ~D 即可髓废。
一直循環(huán)的試探巷懈，知道D 全部為1 為止。
下面是整個程序的代碼：
public class NQueen {
private static final int N = 8; // 皇后數(shù)量瓦哎，可拓展為N皇后
private static int count = 0; // 總方法數(shù)
private static int limit;
public static void main(String[] args) {
limit = (1 << N) - 1;
backtracking(0, 0, 0, 0);
System.out.println(count);
}
private static void backtracking(int a, int b, int c, int depth) {
if (depth == N) {
count++;
return;
}
int d = a | b | c;
while (d < limit) {
int bit = (d + 1) & ~d;
backtracking(a | bit, limit & ((b | bit) >> 1), limit & ((c | bit) << 1), depth + 1);
d |= bit;
}
}
}
