LeetCode

N-Queens II

2014.2.13 20:01

Follow up for N-Queens problem.

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

Solution:

　　This problem is a simplification from the N-Queens. This time we only have record the number of solutions.

　　Time complexity is O(n!). Space complexity is O(n!) as well, which comes from parameters in recursive function calls.

Accepted code:

 1 // 3CE, 1AC, why so hasty?
 2 class Solution {
 3 public:
 4     int totalNQueens(int n) {
 5         a = nullptr;
 6         if (n <= 0) {
 7             return 0;
 8         }
 9         
10         res_count = 0;
11         a = new int[n];
12         solveNQueensRecursive(0, a, n);
13         delete[] a;
14         
15         return res_count;
16     }
17 private:
18     int *a;
19     int res_count;
20     
21     void solveNQueensRecursive(int idx, int a[], const int &n) {
22         if (idx == n) {
23             // one solution is found
24             ++res_count;
25             return;
26         }
27         
28         int i, j;
29         // check if the current layout is valid.
30         for (i = 0; i < n; ++i) {
31             a[idx] = i;
32             for (j = 0; j < idx; ++j) {
33                 if (a[j] == a[idx] || myabs(idx - j) == myabs(a[idx] - a[j])) {
34                     break;
35                 }
36             }
37             if (j == idx) {
38                 // valid layout.
39                 solveNQueensRecursive(idx + 1, a, n);
40             }
41         }
42     }
43     
44     int myabs(const int x) {
45         return (x >= 0 ? x : -x);
46     }
47 };