# 52. N-Queens II
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 the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
# Solution
Approach 1: Traceback.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
private:
int total;
vector<bool> setCol;
vector<bool> setSlash1;
vector<bool> setSlash2;
void doSolveQueens(vector<vector<char>>& chessboard, int n, int row) {
if (row == n)
{
total++;
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:
int totalNQueens(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 total;
}
};