N-Queens II

Follow up for N-Queens problem.

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

C++:
01 void totalNQueensHelper(int n, vector<int>& cur, int& result)
02 {
03     int m=cur.size();
04     if(m==n)
05     {
06         result++;
07         return;
08     }
09     vector<int> table(n,0);
10     for(int i=0;i<m;i++)
11     {
12         int k=cur[i];
13         table[k]=1;
14         int left=km+i;
15         int right=k+mi;
16         if(left>=0)
17             table[left]=1;
18         if(right<n)
19             table[right]=1;
20     }
21     for(int i=0;i<n;i++)
22     {
23         if(table[i]==0)
24         {
25             cur.push_back(i);
26             totalNQueensHelper(n,cur,result);
27             cur.pop_back();
28         }
29     }
30 }
31 class Solution {
32 public:
33     int totalNQueens(int n) {
34         // Start typing your C/C++ solution below
35         // DO NOT write int main() function
36         int result=0;
37         vector<int> cur;
38         totalNQueensHelper(n,cur,result);
39         return result;
40     }
41 };
Advertisements
This entry was posted in Array and linked list, Backtrack. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s