關(guān)于我的 Leetcode 題目解答预吆，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers

LeetCode題目：51. N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

N-Queens

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.."]
]</pre>

以下代碼的時間復(fù)雜度為 O(n!)： NP 問題拐叉，相當(dāng)于對n的位置求排列數(shù)胶背。

class Solution {
    private List<List<String>> result = new ArrayList<>();
    
    public List<List<String>> solveNQueens(int n) {
        // 定義一個棋盤，1代表皇后廷粒，0代表空格
        int[][] board = new int[n][n];
        
        // 從第一行開始
        travel(board, n, 0);
        
        return result;
    }
    
    // 在第rowIdx行放置皇后
    public void travel(int[][] board, int n, int rowIdx) {
        
        // 遍歷每一個可以使用的位置
        for(int colIdx = 0; colIdx < n; colIdx++) {
            if(isValidPosition(board, n, rowIdx, colIdx)) {
                
                // 放置皇后
                board[rowIdx][colIdx] = 1;
                
                // 到達(dá)最后一行红且，加入結(jié)果集
                if(rowIdx == n - 1) {
                    
                    List<String> oneSolution = new ArrayList<>();
                    
                    for(int i = 0; i < n; i++) {
                        StringBuilder sb = new StringBuilder();
                        
                        for(int j = 0; j < n; j++) {
                            if(board[i][j] == 1) {
                                sb.append("Q");
                            } else {
                                sb.append(".");
                            }
                        }
                        
                        oneSolution.add(sb.toString());
                    }
                    
                    result.add(oneSolution);
                    
                }
                // 遞歸到下一行
                else {
                    travel(board, n, rowIdx + 1);
                }

                // backtracking 回溯
                board[rowIdx][colIdx] = 0;
            }
        }
    }
    
    // 判斷在(rowIdx, colIdx) 是否可以放置皇后
    public boolean isValidPosition(int[][] board, int n, int rowIdx, int colIdx) {
        
        // 在垂直方向上已經(jīng)有皇后了
        for(int i = 0; i < rowIdx; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 1) {
                    // 在同一列上有皇后了
                    if(j == colIdx) return false;
                    
                    // 寫對角斜線上有皇后了
                    if(Math.abs(rowIdx - i) == Math.abs(colIdx - j)) return false;
                }
            }
        }
        
        return true;
    }
}