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