Link to Question

HARD

N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

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:

n = 4

Output:

[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation:
There exist two distinct solutions to the 4-queens puzzle.

---

Constraints

• 1 ≤ n ≤ 9

---

Solution: Backtracking

• Time Complexity: O(n!)
• Space Complexity: O(n^2)

C++

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));
        vector<bool> col(n, false), diag1(2*n-1, false), diag2(2*n-1, false);
        function<void(int)> dfs = [&](int row) {
            if (row == n) {
                res.push_back(board);
                return;
            }
            for (int c = 0; c < n; ++c) {
                if (col[c] || diag1[row+c] || diag2[row-c+n-1]) continue;
                board[row][c] = 'Q';
                col[c] = diag1[row+c] = diag2[row-c+n-1] = true;
                dfs(row+1);
                board[row][c] = '.';
                col[c] = diag1[row+c] = diag2[row-c+n-1] = false;
            }
        };
        dfs(0);
        return res;
    }
};