這是一道很經(jīng)典的題目好唯，相信很多程序員都知道馍资。

其實(shí)解題的思路很簡(jiǎn)單筒主，就是在每行枚舉選擇每個(gè)位置，判斷選則的位置是否符合要求鸟蟹。如果符合要求乌妙，繼續(xù)在下一行按照這個(gè)方法進(jìn)行；如果不符合建钥，枚舉試驗(yàn)當(dāng)前行下一個(gè)位置藤韵，當(dāng)前行如果所有位置都有沖突，則返回上一行選擇上一行下一個(gè)合適的位置熊经。

其實(shí)就是典型的深度優(yōu)先搜索的思路泽艘。自己的解題思路，整個(gè)棋盤(pán)當(dāng)前擺放的情況通過(guò)一個(gè)二維數(shù)組int[][] chess表示镐依；判斷當(dāng)前選的位置是否合法匹涮，只需要判斷它之前的兩個(gè)斜線方向和直線方向是否已放置過(guò)皇后；用List<Integer>記錄每個(gè)方案槐壳，最后再轉(zhuǎn)為L(zhǎng)ist<List<String>>然低，可以避免搜索過(guò)程中處理字符串的復(fù)雜步驟。下面是代碼：

int n;
public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    if (n <= 0) {
        return res;
    }

    this.n = n;
    //只記錄每行存放的點(diǎn)
    List<List<Integer>> paths = new ArrayList<>();
    //用一個(gè)chess數(shù)組記錄當(dāng)前擺放的情況
    int[][] chess = new int[n][n];

    helper(0, new ArrayList<>(), paths, chess);

    return convert(paths);
}

public void helper(int row, List<Integer> path, List<List<Integer>> paths, int[][] chess) {
    if (row == n) {
        paths.add(new ArrayList<>(path));
        return;
    }

    for (int col = 0; col < n; col++) {
        if (!isValid(row, col, chess)) {
            continue;
        }
        chess[row][col] = 1;
        path.add(col);
        helper(row + 1, path, paths, chess);
        chess[row][col] = 0;
        path.remove(path.size() - 1);
    }
}

public boolean isValid(int row, int col, int[][] chess) {
    if (row < 0 || row >= chess.length || col < 0 || col >= chess.length || chess[row][col] == 1) {
        return false;
    }

    for (int i = row - 1; i >= 0; i--) {
        if (chess[i][col] == 1) {
            return false;
        }
    }

    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (chess[i][j] == 1) {
            return false;
        }
    }

    for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
        if (chess[i][j] == 1) {
            return false;
        }
    }

    return true;
}

public List<List<String>> convert(List<List<Integer>> resi) {
    List<List<String>> ress = new ArrayList<>();
    if (resi == null || resi.size() == 0) {
        return ress;
    }

    for (int i = 0; i < resi.size(); i++) {
        List<String> subres = new ArrayList<>();
        for (int j = 0; j < resi.get(i).size(); j++) {
            StringBuffer buffer = new StringBuffer();
            for (int k = 0; k < n; k++) {
                if (k == resi.get(i).get(j)) {
                    buffer.append('Q');
                } else {
                    buffer.append('.');
                }
            }
            subres.add(buffer.toString());
        }
        ress.add(subres);
    }

    return ress;
}

看了leetcode上discuss上的解法，有兩個(gè)部分處理的更優(yōu)：
1雳攘、整個(gè)棋盤(pán)的狀態(tài)通過(guò)一個(gè)char[][]數(shù)組記錄带兜，這樣最后直接把char數(shù)組轉(zhuǎn)為L(zhǎng)ist<List<String>>即可，比自己的方法節(jié)省了一個(gè)paths的空間吨灭。
2刚照、判斷每個(gè)位置是否合法的函數(shù)，巧妙的通過(guò)坐標(biāo)值的計(jì)算判斷喧兄。
第一個(gè)優(yōu)點(diǎn)體現(xiàn)的是選擇合適的數(shù)據(jù)結(jié)構(gòu)的能力无畔；第二個(gè)優(yōu)點(diǎn)體現(xiàn)的是對(duì)題目全面洞察并進(jìn)行條件轉(zhuǎn)換的能力。