# 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.
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.
# Solution
Approach 1: Traceback.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
private:
vector<vector<string>> res;
vector<bool> setCol;
vector<bool> setSlash1;
vector<bool> setSlash2;
vector<string> getResult(vector<vector<char>>& chessboard, int n) {
vector<string> oneRes;
for (int row = 0; row < n; ++row)
{
ostringstream oss;
for (int col = 0; col < n; ++col)
oss << chessboard[row][col];
oneRes.push_back(oss.str());
}
return oneRes;
}
void doSolveQueens(vector<vector<char>>& chessboard, int n, int row) {
if (row == n)
{
res.push_back(getResult(chessboard, n));
return;
}
for (int col = 0; col < n; ++col)
{
if (!setCol[col] && !setSlash1[row-col+n-1] && !setSlash2[row+col])
{
setCol[col] = true;
setSlash1[row-col+n-1] = true;
setSlash2[row+col] = true;
chessboard[row][col] = 'Q';
doSolveQueens(chessboard, n, row+1);
chessboard[row][col] = '.';
setSlash2[row+col] = false;
setSlash1[row-col+n-1] = false;
setCol[col] = false;
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<char>> chessboard(n, vector<char>(n, '.'));
setCol = vector<bool>(n, false);
setSlash1 = vector<bool>(2*n-1, false);
setSlash2 = vector<bool>(2*n-1, false);
doSolveQueens(chessboard, n, 0);
return res;
}
};