按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

n皇后問題研究的是如何將n個皇后放置在n×n的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個整數(shù)n，返回所有不同的n皇后問題的解決方案。

每一種解法包含一個不同的n皇后問題的棋子放置方案，該方案中'Q'和'.'分別代表了皇后和空位。

示例 1：

輸入：n = 4

輸出：

[[".Q..","...Q","Q...","..Q."],

["..Q.","Q...","...Q",".Q.."]]

解釋：如上圖所示，4 皇后問題存在兩個不同的解法。

輸入：n = 1

輸出：[["Q"]]

前面我們剛講過解數(shù)獨-回溯算法解決，這題和數(shù)獨都是使用回溯算法解決的，回溯算法就是不斷嘗試，關(guān)于回溯算法我們講過很多，回溯算法有一個經(jīng)典的模板，具體也可以看下450，什么叫回溯算法，一看就會，一寫就廢。這里我們就以n等于4為例來畫個圖看下

public List<List<String>> solveNQueens(int n) {
    char[][] chess = new char[n][n];
    // 初始化棋盤
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            chess[i][j] = '.';
    List<List<String>> res = new ArrayList<>();
    // 回溯算法
    backtrack(res, chess, 0);
    return res;
}

private void backtrack(List<List<String>> res, char[][] chess, int row) {
    // 棋盤所有的行都遍歷完了，說明找到一個可行的解，把它加入到集合res中
    if (row == chess.length) {
        res.add(construct(chess));
        return;
    }
    // 相當(dāng)于一顆n叉樹
    for (int col = 0; col < chess.length; col++) {
        // 判斷當(dāng)前位置是否可以放皇后
        if (valid(chess, row, col)) {
            // 如果在當(dāng)前位置放皇后不發(fā)生攻擊，就在當(dāng)前位置放個皇后
            chess[row][col] = 'Q';
            // 遞歸，下一行
            backtrack(res, chess, row + 1);
            // 撤銷選擇
            chess[row][col] = '.';
        }
    }
}

//row表示第幾行，col表示第幾列
private boolean valid(char[][] chess, int row, int col) {
    //判斷當(dāng)前列有沒有皇后,因為他是一行一行往下走的，
    //我們只需要檢查走過的行數(shù)即可，通俗一點就是判斷當(dāng)前
    //坐標(biāo)位置的上面有沒有皇后
    for (int i = 0; i < row; i++) {
        if (chess[i][col] == 'Q') {
            return false;
        }
    }
    //判斷當(dāng)前坐標(biāo)的右上角有沒有皇后
    for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
        if (chess[i][j] == 'Q') {
            return false;
        }
    }
    //判斷當(dāng)前坐標(biāo)的左上角有沒有皇后
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (chess[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

//把數(shù)組轉(zhuǎn)為list
private List<String> construct(char[][] chess) {
    List<String> path = new ArrayList<>();
    for (int i = 0; i < chess.length; i++) {
        path.add(new String(chess[i]));
    }
    return path;
}