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