51. N-Queens

Then-queens puzzle is the problem of placingn_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.

Thoughts:

1. The number of columns is n, the number of 45° diagonals is2 * n - 1, the number of 135° diagonals is also 2 * n - 1. When reach[row, col], the column No. is col, the 45° diagonal No. is row + coland the 135° diagonal No. is n - 1 + col - row. We can use three arrays to indicate if the column or the diagonal had a queen before, if not, we can put a queen in this position and continue.

2. Optimization: Merge all arrays into one: only need one boo array flag for size 5*n - 1:n for col; 2n -1 for col + row -> diag; 2n - 1 for n - 1 - row + row for anti_diag.

Code: T: O(n^2) S: O(n)

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>>res;
        vector<string>nQueens(n, string(n,'.'));
        vector<int> flag_col (n , 1), flag_45(2*n -1, 1), flag_135( 2*n - 1, 1);
        dfs(res, nQueens, flag_col, flag_45, flag_135, 0, n);
        return res;
    }
private:
    void dfs(vector<vector<string>>&res, vector<string>&nQueens, vector<int> &flag_col ,vector<int> &flag_45 ,vector<int> &flag_135
            , int row, int n){
        if (row == n){
          res.push_back(nQueens);
          return;
        } 

        for (int col = 0; col < n; col++ ){
            if (flag_col[col] && flag_45[row + col] && flag_135[n - 1 - row + col]){
                flag_col[col] = flag_45[row + col] = flag_135[n - 1 - row + col] = 0;
                nQueens[row][col] = 'Q';
                dfs(res, nQueens, flag_col, flag_45, flag_135, row + 1, n);
                nQueens[row][col] = '.';
                flag_col[col] = flag_45[row + col] = flag_135[n - 1 - row + col] = 1;
            }
        }

    }
};

Code: merged T: O(n^2) S: O(n)

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>>res;
        vector<string>nQueens(n, string(n,'.'));
        vector<int> flag (5*n -2, 1); // n for col; 2n -1  for col + row -> diag; 2n - 1 for n - 1 - row + row for anti_diag
        dfs(res, nQueens, flag, 0, n);
        return res;
    }
private:
    void dfs(vector<vector<string>>&res, vector<string>&nQueens, vector<int> flag, int row, int n){
        if (row == n){
          res.push_back(nQueens);
          return;
        } 

        for (int col = 0; col < n; col++ ){
            if (flag[col] && flag[n + row + col] && flag[3*n - 1 + n - 1 - row + col]){
                flag[col] = flag[n + row + col] = flag[3*n - 1 + n - 1 - row + col] = 0;
                nQueens[row][col] = 'Q';
                dfs(res, nQueens, flag, row + 1, n);
                nQueens[row][col] = '.';
                flag[col] = flag[n + row + col] = flag[3*n - 1 + n - 1 - row + col] = 1;
            }
        }
    }
};