[Leetcode 92] 52 N-Queens II

Problem:

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Analysis:

This is the extension of the former N-Queens problem. If we use the code before directly, there will be TLE problem. After checking the code, we find the isValid() process consumes too much time. The complexity is O(n*n). So, here we provide the optimized version of the N-Queens.

The first optimizatoin is as follows: given the new pisition to place a Queen (i, j), we search along the up-left, up-right, bottom-left, bottom-right directions to see if there is collision. In the worst case, the complexity is O(2n). The code will pass the large test dataset in 1380ms.

The second optimization is as follows: we only need to check those places has Queen to see if they can attact the new place. Originally the col array only used as an indicator to show whether here is a Queen. Now if there's no Queen in this column, we set col[i] = -1 else we set it equals it's row, col[i] = r. Then in the isValid process, we then only need to check those places. The complexity is at most O(n). And for the large test dataset, the code will pass in 1252ms.

Code:

Slightly Optimized:

 1 class Solution {
 2 public:
 3     int dim, *col, cnt;
 4 
 5     int totalNQueens(int n) {
 6         // Start typing your C/C++ solution below
 7         // DO NOT write int main() function
 8         dim = n;
 9         cnt = 0;
10 
11         string s(n, '.');
12         col = new int[n];
13         vector<string> tmp;
14         for (int i=0; i<n; i++) {
15             col[i] = 0;
16             tmp.push_back(s);
17         }
18 
19         dfs(tmp, 0);
20 
21         delete [] col;
22 
23         return cnt;
24     }
25 
26 private:
27     void dfs(vector<string> &s, int r) {
28         if (r == dim) {
29             cnt++;
30             return;
31         }
32 
33         for (int i=0; i<dim; i++) {
34             if (col[i] == 0 && isValid(s, r, i)) {
35                 col[i] = 1;
36                 s[r][i] = 'Q';
37                 dfs(s, r+1);
38                 s[r][i] = '.';
39                 col[i] = 0;
40             }
41         }
42     }
43 
44     bool isValid(vector<string> &s, int r, int c) {
45         int rr, cc;
46 
47         // check up-left
48         rr = r-1, cc = c-1;
49         while (rr>=0 && cc>=0) {
50             if (s[rr][cc] == 'Q')
51                 return false;
52 
53             rr--;
54             cc--;
55         }
56 
57         // check bottom-right
58         rr = r+1, cc = c+1;
59         while (rr<dim && cc<dim) {
60             if (s[rr][cc] == 'Q')
61                 return false;
62 
63             rr++;
64             cc++;
65         }
66 
67         // check up-right
68         rr = r-1, cc = c+1;
69         while (rr>=0 && cc<dim) {
70             if (s[rr][cc] == 'Q')
71                 return false;
72 
73             rr--;
74             cc++;
75         }
76 
77         // check bottom-left
78         rr = r+1, cc = c-1;
79         while (rr<dim && cc>=0) {
80             if (s[rr][cc] == 'Q')
81                 return false;
82 
83             rr++;
84             cc--;
85         }
86 
87         return true;
88     }
89 };

View Code

Highly Optimized:

 1 class Solution {
 2 public:
 3     int dim, *col, cnt;
 4     vector<vector<string> > res;
 5 
 6     int totalNQueens(int n) {
 7         // Start typing your C/C++ solution below
 8         // DO NOT write int main() function
 9         dim = n;
10         cnt = 0;
11         
12         string s(n, '.');
13         col = new int[n];
14         vector<string> tmp;
15         for (int i=0; i<n; i++) {
16             col[i] = -1;
17             tmp.push_back(s);
18         }
19 
20         dfs(tmp, 0);
21         
22         delete [] col;
23         
24         return cnt;
25     }
26     
27 private:
28     void dfs(vector<string> &s, int r) {
29         if (r == dim) {
30             cnt++;
31             return;
32         }
33 
34         for (int i=0; i<dim; i++) {
35             if (col[i] == -1 && isValid(s, r, i)) {
36                 col[i] = r;
37                 s[r][i] = 'Q';
38                 dfs(s, r+1);
39                 s[r][i] = '.';
40                 col[i] = -1;
41             }
42         }
43     }
44 
45     bool isValid(vector<string> &s, int r, int c) {
46         for (int i=0; i<dim; i++) {
47             if ((col[i] != -1) && s[col[i]][i]=='Q' 
48                 && ((i-c == r-col[i]) || (i-c == col[i]-r)))
49                 return false;
50         }
51 
52         return true;
53     }
54 };

View Code