51. N Queens N皇后问题

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(分别地).

 Example:
 
 Input: 4
 Output: [
 [".Q..",  // Solution 1
 "...Q",
 "Q...",
 "..Q."],
 
 ["..Q.",  // Solution 2
 "Q...",
 "...Q",
 ".Q.."]
 ]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

八皇后问题,同一行,同一列,左右对角线上不能排放两个皇后.

回溯算法问题

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res{};
    // 下标表示行,值表示列
    int *result = new int[n]{};
    solveNQueensCore(n, 0, res, result);
    return res;
}
    
void solveNQueensCore(int n,int row,vector<vector<string>> &res,int result[]) {
    // 输出结果
    if (row==n) {
        vector<string> sol{};
        for (int i = 0; i<n; i++) {
            string str = "";
            for (int j = 0; j<n; j++) {
                if (result[i] == j) {
                    str += 'Q';
                }else{
                    str += '.';
                }
            }
            sol.push_back(str);
        }
        res.push_back(sol);
        return ;
    }
    for (int col = 0; col < n; col++) {
        if (isOk(result, n, row, col)) {
            result[row] = col;
            solveNQueensCore(n, row+1, res, result);
        }
    }
}
    
bool isOk(int result[],int n,int row,int column){
    int leftup = column-1, rightup = column+1;
    for (int i = row-1; i>=0; i--) {
        // 第i行column有棋子
        if (result[i] == column){
            return false;
        }
        if (leftup >= 0) {
            // 左上对角线有棋子
            if (result[i] == leftup) {
                return false;
            }
        }
        if (rightup < n) {
            // 右上对角线有棋子
            if (result[i] == rightup){
                return false;
            }
        }
        --leftup;
        ++rightup;
    }
    return true;
}
 
comments powered by Disqus