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