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.

class Solution {
public:
    // bool isValid(vector<int>& pos, int row, int col) {
    //     for (int i = 0; i < row; ++i) {
    //         if (col == pos[i] || abs(row - i) == abs(col - pos[i])) return false;
    //     }
    //     return true;
    // }
    // void helper(vector<int>& pos, int row, vector<vector<string> >& res) {
    //     int n = pos.size();
    //     if (row == n) {
    //         vector<string> cur(n, string(n, '.'));
    //         for (int i = 0; i < n; ++i) {
    //             cur[i][pos[i]] = 'Q';
    //         }
    //         res.push_back(cur);
    //     } else {
    //         for (int col = 0; col < n; ++col) {
    //             if (isValid(pos, row, col)) {
    //                 pos[row] = col;
    //                 helper(pos, row + 1, res);
    //                 pos[row] = -1;
    //             }
    //         }
    //     }
    // }
    // vector<vector<string>> solveNQueens(int n) { // time: O(n^2); space: O(n^2)
    //     vector<vector<string> > res;
    //     vector<int> pos(n, -1); // the column location of queen in i row
    //     helper(pos, 0, res);
    //     return res;
    // }
    
    // bool isValid(vector<string>& cur, int row, int col) {
    //     int n = cur.size();
    //     for (int i = 0; i < row; ++i) {
    //         if (cur[i][col] == 'Q') return false;
    //     }
    //     for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
    //         if (cur[i][j] == 'Q') return false;
    //     }
    //     for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
    //         if (cur[i][j] == 'Q') return false;
    //     }
    //     return true;
    // }
    // void helper(vector<vector<string> >& res, vector<string>& cur, int row) {
    //     int n = cur.size();
    //     if (row == n) {
    //         res.push_back(cur);
    //     } else {
    //         for (int col = 0; col < n; ++col) {
    //             if (isValid(cur, row, col)) {
    //                 cur[row][col] = 'Q';
    //                 helper(res, cur, row + 1);
    //                 cur[row][col] = '.';
    //             }
    //         }
    //     }
    // }
    // vector<vector<string>> solveNQueens(int n) { // time: O(n^2); space: O(n^2)
    //     vector<vector<string> > res;
    //     vector<string> cur(n, string(n, '.'));
    //     helper(res, cur, 0);
    //     return res;
    // }
    
    // void helper(vector<vector<string> >& res, vector<string>& cur, vector<int>& flag_col, vector<int>& flag_45, vector<int>& flag_135, int row) {
    //     int n = cur.size();
    //     if (row == n) {
    //         res.push_back(cur);
    //     } else {
    //         for (int col = 0; col < n; ++col) {
    //             if (flag_col[col] && flag_45[row + col] && flag_135[n - 1 + col - row]) {
    //                 flag_col[col] = flag_45[col + row] = flag_135[n - 1 + col - row] = 0;
    //                 cur[row][col] = 'Q';
    //                 helper(res, cur, flag_col, flag_45, flag_135, row + 1);
    //                 cur[row][col] = '.';
    //                 flag_col[col] = flag_45[col + row] = flag_135[n - 1 + col - row] = 1;
    //             }
    //         }
    //     }
    // }
    // vector<vector<string>> solveNQueens(int n) { // time: O(n^2); space: O(n^2)
    //     vector<vector<string> > res;
    //     vector<string> cur(n, string(n, '.'));
    //     vector<int> flag_col(n, 1), flag_45(2 * n - 1, 1), flag_135(2 * n - 1, 1);
    //     helper(res, cur, flag_col, flag_45, flag_135, 0);
    //     return res;
    // }
    
    void helper(vector<vector<string> >& res, vector<string>& cur, vector<int>& flag, int row) {
        int n = cur.size();
        if (row == n) {
            res.push_back(cur);
        } else {
            for (int col = 0; col < n; ++col) {
                if (flag[col] && flag[n + row + col] && flag[n + 2 * n - 1 + n - 1 + col - row]) {
                    flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 0;
                    cur[row][col] = 'Q';
                    helper(res, cur, flag, row + 1);
                    cur[row][col] = '.';
                    flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 1;
                }
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) { // time: O(n!); space: O(n!)
        vector<vector<string> > res;
        vector<string> cur(n, string(n, '.'));
        vector<int> flag(5 * n - 2, 1);
        helper(res, cur, flag, 0);
        return res;
    }
};