52. N Queens II 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.

这道题跟上道题一样, 只是这道题不要求输出棋子的摆放位置.只是输出有多少种摆放的解决方案个数

int totalNQueens(int n) {
    int resCount = 0;
    int *result = new int[n]{};
    totalNQueensCore(n,0,resCount,result);
    return resCount;
}
    
void totalNQueensCore(int n,int row,int &resCount, int result[]){
    if (row == n){
        resCount ++;
        return;
    }
    for (int col=0;col<n;col++){
        if (isOk(result,n,row,col)){
            result[row] = col;
            totalNQueensCore(n,row+1,resCount,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