51. N-Queens

We’ll backtrack row by row and for each row, we check column by column. Since it’s a backtracking solution, we don’t have to check rows that’ll be checked later. So for validation, we only need to check the characters in previous rows in a particular column and the 45 degree and 135 degree diagonals.

1:  class Solution {  
2:  public:  
3:    vector<vector<string>> solveNQueens(int n) {  
4:      vector<vector<string>> res;  
5:      vector<string> sol(n, string(n, '.'));  
6:      helper(res, sol, 0, n);  
7:      return res;  
8:    }  
9:    void helper(vector<vector<string>> &res, vector<string> &sol, int row, int n) {  
10:      if (n == row) {  
11:        res.push_back(sol);  
12:        return;  
13:      }  
14:      for (int j = 0; j < n; j++) {  
15:        if (valid(sol, row, j, n)) {  
16:          sol[row][j] = 'Q';  
17:          helper(res, sol, row+1, n);  
18:          sol[row][j] = '.';  
19:        }  
20:      }  
21:    }  
22:    bool valid(vector<string> &sol, int row, int col, int n) {  
23:      for (int i = 0; i < row; i++) {  
24:        if (sol[i][col] == 'Q') return false;  
25:      }  
26:      for (int i=row-1, j=col-1; i >= 0 && j >= 0; i--, j--) {  
27:        if (sol[i][j] == 'Q') return false;  
28:      }  
29:      for (int i=row-1, j=col+1; i >= 0 && j < n; i--, j++) {  
30:        if (sol[i][j] == 'Q') return false;  
31:      }  
32:      return true;  
33:    }  
34:  };