[LeetCode] NQueens II

Follow up for N-Queens problem.

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

DFS

 1 class Solution {
 2 private:
 3     int ret;
 4     int a[100];
 5     bool canUse[100];
 6 public:
 7     bool check(int y, int n)
 8     {
 9         for(int i = 0; i < n; i++)
10             if (abs(i - n) == abs(y - a[i]))
11                 return false;
12         return true;
13     }
14     
15     void solve(int dep, int maxDep)
16     {
17         if (dep == maxDep)
18         {
19             ret++;            
20             return;
21         }
22         
23         for(int i = 0; i < maxDep; i++)
24             if (canUse[i] && check(i, dep))
25             {
26                 canUse[i] = false;
27                 a[dep] = i;
28                 solve(dep + 1, maxDep);
29                 canUse[i] = true;             
30             }
31     }
32     
33     int totalNQueens(int n) {
34         // Start typing your C/C++ solution below
35         // DO NOT write int main() function
36         ret = 0;
37         memset(canUse, true, sizeof(canUse));
38         solve(0, n);
39         return ret;
40     }
41 };