摘要：暴力法復雜度時間空間思路因為皇后問題中，同一列不可能有兩個皇后，所以我們可以用一個一維數(shù)組來表示二維棋盤上皇后的位置。一維數(shù)組中每一個值的下標代表著對應棋盤的列，每一個值則是那一列中皇后所在的行。

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens" placement, where "Q" and "." both indicate a queen and an empty space respectively.

For example, There exist two distinct solutions to the 4-queens puzzle:
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

時間 O(N^3) 空間 O(N)

因為n皇后問題中，同一列不可能有兩個皇后，所以我們可以用一個一維數(shù)組來表示二維棋盤上皇后的位置。一維數(shù)組中每一個值的下標代表著對應棋盤的列，每一個值則是那一列中皇后所在的行。這樣我們可以只對一個一維數(shù)組進行深度優(yōu)先搜索，來找出對于每一列，我們的皇后應該放在哪一行。在下一輪搜索之前，我們先檢查一下新構(gòu)成的數(shù)組是否是有效的，這樣可以剪掉不必要的分支。檢查的方法則是看之前排好的每一個皇后是否沖突。

public class Solution {
    
    List> res;
    
    public List> solveNQueens(int n) {
        res = new LinkedList>();
        int[] nqueens = new int[n];
        helper(nqueens, n, 0);
        return res;
    }
    
    public void helper(int[] nqueens, int n, int i){
        if(i == nqueens.length){
            List one = new LinkedList();
            // 構(gòu)成表示整個棋盤的字符串
            for(int num : nqueens){
                // 構(gòu)成一個形如....Q....的字符串
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append(".");
                }
                sb.append("Q");
                for(int j = num + 1; j < n; j++){
                    sb.append(".");
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            //選擇下一列的數(shù)字
            // 比如之前已經(jīng)選了13xxxxxx，下一列可以選6，形成136xxxxx
            for(int num = 0; num < n; num++){
                nqueens[i] = num;
                // 如果是有效的，繼續(xù)搜索
                if(isValid(nqueens, i)){
                    helper(nqueens, n, i+1);
                }
            }
        }
    }
    
    private boolean isValid(int[] nqueens, int i){
        for(int idx = 0; idx < i; idx++){
            // 檢查對角線只要判斷他們差的絕對值和坐標的差是否相等就行了
            if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) ==  i - idx){
                return false;
            }
        }
        return true;
    }
}

時間 O(N^2) 空間 O(N)

該方法的思路和暴力法一樣，區(qū)別在于，之前我們判斷一個皇后是否沖突，是遍歷一遍當前皇后排列的列表，看每一個皇后是否沖突。這里，我們用三個集合來保存之前皇后的信息，就可以O(shè)(1)時間判斷出皇后是否沖突。三個集合分別是行集合，用于存放有哪些行被占了，主對角線集合，用于存放哪個右上到左下的對角線被占了，副對角線集合，用于存放哪個左上到右下的對角線被占了。如何唯一的判斷某個點所在的主對角線和副對角線呢？我們發(fā)現(xiàn)，兩個點的行號加列號的和相同，則兩個點在同一條主對角線上。兩個點的行號減列號的差相同，則兩個點再同一條副對角線上。

主對角線row + col，副對角線row - col

public class Solution {
    
    List> res = new LinkedList>();;
    Set rowSet = new HashSet();
    Set diag1Set = new HashSet();
    Set diag2Set = new HashSet();
    
    public List> solveNQueens(int n) {
        helper(new LinkedList(), n, 0);
        return res;
    }
    
    public void helper(LinkedList tmp, int n, int col){
        if(col == n){
            List one = new LinkedList();
            for(Integer num : tmp){
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append(".");
                }
                sb.append("Q");
                for(int j = num + 1; j < n; j++){
                    sb.append(".");
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            // 對于列col，看皇后應該放在第幾行
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                // 如果三條線上已經(jīng)有占據(jù)的皇后了，則跳過該種擺法
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                // 用回溯法遞歸求解
                tmp.add(row);
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(tmp, n, col + 1);
                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
                tmp.removeLast();
            }
        }
    }
}

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

時間 O(N^3) 空間 O(N)

跟I的解法一樣，只不過把原本構(gòu)造字符串的地方換成了計數(shù)器加一。

public class Solution {
    
    List> res;
    int cnt = 0;
    
    public int totalNQueens(int n) {
        int[] nqueens = new int[n];
        helper(nqueens, n, 0);
        return cnt;
    }
    
    public void helper(int[] nqueens, int n, int i){
        if(i == nqueens.length){
            cnt++;
        } else {
            for(int num = 0; num < n; num++){
                nqueens[i] = num;
                if(isValid(nqueens, i)){
                    helper(nqueens, n, i+1);
                }
            }
        }
    }
    
    private boolean isValid(int[] nqueens, int i){
        for(int idx = 0; idx < i; idx++){
            if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) ==  i - idx){
                return false;
            }
        }
        return true;
    }
}

時間 O(N^2) 空間 O(N)

跟I的解法一樣，只不過把原本構(gòu)造字符串的地方換成了計數(shù)器加一。

public class Solution {
    
    Set rowSet = new HashSet();
    Set diag1Set = new HashSet();
    Set diag2Set = new HashSet();
    int cnt = 0;
    
    public int totalNQueens(int n) {
        helper(n, 0);
        return cnt;
    }
    
    public void helper(int n, int col){
        if(col == n){
            cnt++;
        } else {
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(n, col + 1);
                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
            }
        }
    }
}