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 . 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 found24             ++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 };