題目描述：

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

上圖為 8 皇后問題的一種解法。
給定一個整數(shù) n，返回所有不同的 *n *皇后問題的解決方案。
每一種解法包含一個明確的 n 皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

示例：

示例:
輸入: 4
輸出: 2
解釋: 4 皇后問題存在兩個不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]

解答：回溯

// n皇后問題是典型的回溯法，即任何兩個皇后不能在同一行同一列或同一對角線
    public static int totalNQueens(int n) {
        List<List<String>> rs = new ArrayList<List<String>>();
        // 第i個位置存的數(shù)表示：row行，Q的列
        int[] queen = new int[n];
        // 在第0行放Q
        placeQueen(queen, 0, n, rs);
        for (int i = 0; i < rs.size(); i++) {
            for (int j = 0; j < rs.get(0).size(); j++) {
                System.out.print(rs.get(i).get(i) + ";");
            }
            System.out.println();
        }
        return rs.size();
    }

    private static void placeQueen(int[] queen, int row, int n, List<List<String>> rs) {
        // 如果已經(jīng)填滿Q，返回結果
        if (row == n) {
            List<String> list = new ArrayList<String>();
            for (int i = 0; i < n; i++) {
                String str = "";
                for (int col = 0; col < n; col++) {
                    if (queen[i] == col) {
                        str += "Q";
                    } else {
                        str += ".";
                    }
                }
                list.add(str);
            }
            rs.add(list);
        }
        // 第row個Q開始，從每一列開始遍歷
        for (int col = 0; col < n; col++) {
            // 當當前列不滿足條件時，查看下一列        
            // 如果在該列不沖突，就添加[滿足時才添加，或者先queen[row] = col，再valid]
            if (isValid(queen, row, col)) {
                // 數(shù)組中存放：第row個Q所在的列
                queen[row] = col;
                // 繼續(xù)放下一個Q，即下一行，row+1
                placeQueen(queen, row + 1, n, rs);
            }
        }
    }

    private static boolean isValid(int[] queen, int row, int col) {
        // 與之前已經(jīng)放好的Q一一比較
        for (int i = 0; i < row; i++) {
            // pos即之前每一Q所在的列
            int pos = queen[i];
            // 同一列／右下、左上對角線／左下、右上對角線
            /*
            if (pos==col||Math.abs(col-pos)==row-i) {
                return false;
            }
            */
            // 同一列
            if (pos == col) {
                return false;
            }
            // 右下、左上對角線
            // 上一Q的列 + 這一Q的行 - 前面所有Q個數(shù)
            if (pos + row - i == col) {
                return false;
            }
            // 左下、右上對角線
            // 上一Q的列 - 這一Q的行 + 前面所有Q個數(shù)
            if (pos - row + i == col) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        totalNQueens(4);
    }