Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
public class Solution {
int rec = 0;
public int totalNQueens(int n) {
if(n<=0)
return rec;
int[] num = new int[n];
for(int i=0;i<n;i++)
num[i] = i;
DFS(0,n,num);
return rec;
}
public void DFS(int start,int N,int[] num)
{
if(start == N)
{
if(isValid(num))
rec += 1;
// System.out.println(rec);
}
else
{
for(int i=start;i<N;i++)
{
int temp1=num[start];
num[start]=num[i];
num[i]=temp1;
// if(isValid(num,i));
DFS(start+1,N,num);
int temp2=num[start];
num[start]=num[i];
num[i]=temp2;
}
}
}
public boolean isValid(int[] num)
{
for(int i=0;i<num.length;i++)
for(int j=i+1;j<num.length;j++)
if(Math.abs(num[i]-num[j])==Math.abs(i-j))
return false;
return true;
}
}
