LintCode 題解丨大廠面試題：N皇後問題

n皇後問題是将n個皇後放置在n*n的棋盤上，皇後彼此之間不能互相攻擊(任意兩個皇後不能位于同一行，同一列，同一斜線)。

給定一個整數n，傳回所有不同的n皇後問題的解決方案。

每個解決方案包含一個明确的n皇後放置布局，其中“Q”和“.”分别表示一個女王和一個空位置。

線上評測位址：

LintCode 領扣

​

樣例1:

輸入:1

輸出:

[["Q"]]

樣例2:

輸入:4

[

// Solution 1

[".Q..",

"...Q",

"Q...",

"..Q."

],

// Solution 2

["..Q.",

".Q.."

]

]

算法：dfs（回溯法）

題目分析

這個問題要求把n個皇後放在一個nXn的棋盤上，使得任何兩個皇後都不能互相攻擊，即它們不能同行，不能同列，也不能位于同一條對角線上。對于n=1，問題的解很簡單，而且很容易看出對于n=2和n=3來說，這個問題是無解的。是以我們考慮4皇後問題，并用回溯法對它求解。

算法思路

因為每個皇後都必須分别占據一行，我們需要做的不過是棋盤上的每個皇後配置設定一列。

下面我們用4皇後的求解過程來講解算法思路：

從空棋盤開始，然後把皇後1 放到它所在行的第-一個可能位置上，也就是第一-行第一列。對于皇後2，在經過第-列和第二列的失敗嘗試之後，我們把它放在第一個可能的位置，就是格子(2, 3)，位于第二行第三列的格子。這被證明是一個死胡同，因為皇後3将沒有位置可放。是以，該算法進行回溯，把皇後2放在下一個可能位置(2,4)上。這樣皇後3就可以放在(3, 2),這被證明是另一個死胡同。該算法然後就回溯到底，把皇後1移到(1,2)。 接着皇後2到(2,4)， 皇後3到(3,1)， 而皇後4到(4, 3)， 這就是該問題的一個解。

整個過程實際上就是一個狀态樹的周遊過程

下圖為狀态樹

代碼思路

按行擺放，在确定一個皇後應該擺的列時，需要檢查目前列是否合法，如果合法，則将皇後放置在目前位置，并進行遞歸，回溯。每行都擺滿皇後時，則産生了一種解法，将所有解法收集并傳回。

合法性判斷方法：目前将要擺放皇後的位置和其他已擺放皇後的位置不能在同一列，且不能在同一條斜線上。這裡判斷是否在同一條斜線上可以通過兩個皇後的位置橫坐标之差和縱坐标之差的絕對值是否相等來判斷。

複雜度分析

空間複雜度：O(N!)

時間複雜度：O(N!)

放置第一個皇後有 N 種可能，放置兩個皇後不超過N(N-2)種可能，放置三個皇後不超過N(N - 2)(N - 4)種可能 ，以此類推。

class Solution {

/**
 * Get all distinct N-Queen solutions
 * @param n: The number of queens
 * @return: All distinct solutions
 * For example, A string '...Q' shows a queen on forth position
 */
List<List<String>> solveNQueens(int n) {
    // result用于存儲答案
    List<List<String>> results = new ArrayList<>();
    if (n <= 0) {
        return results;
    }
    
    search(results, new ArrayList<Integer>(), n);
    return results;
}

// search函數為搜尋函數，n表示已經放置了n個皇後，cols 表示每個皇後所在的列
private void search(List<List<String>> results, List<Integer> cols, int n) {
    // 若已經放置了n個皇後表示出現了一種解法，繪制後加入答案result
    if (cols.size() == n) {
        results.add(Draw(cols));
        return;
    }
    // 枚舉目前皇後放置的列，若不合法則跳過
    for (int colIndex = 0; colIndex < n; colIndex++) {
        if (!isValid(cols, colIndex)) {
            continue;
        }
        // 若合法則遞歸枚舉下一行的皇後
        cols.add(colIndex);
        search(results, cols, n);
        cols.remove(cols.size() - 1);
    }
}

// isValid函數為合法性判斷函數
private boolean isValid(List<Integer> cols, int col) {
    int row = cols.size();
    for (int rowIndex = 0; rowIndex < cols.size(); rowIndex++) {
        //若有其他皇後在同一列或同一斜線上則不合法
        if (cols.get(rowIndex) == col) {
            return false;
        }
        if (row + col == rowIndex + cols.get(rowIndex)) {
            return false;
        }
        if (row - col == rowIndex - cols.get(rowIndex)) {
            return false;
        }
    }
    return true;
}
// Draw函數為将 cols 數組轉換為答案的繪制函數
private List<String> Draw(List<Integer> cols) {
    List<String> result = new ArrayList<>();
    for (int i = 0; i < cols.size(); i++) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < cols.size(); j++) {
            sb.append(j == cols.get(i) ? 'Q' : '.');
        }
        result.add(sb.toString());
    }
    return result;
}           

}

更多題解參考：

九章算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時線上授課為你傳授面試技巧