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;
}
``````