public class Backtrace_NQueen
{
static int n; //皇后个数
static int[] x; //当前解
static long sum; //当前已经找到的可行方案数
public static long nQueen(int nn)
{
n=nn;
sum=0;
x=new int[n+1];
for(int i=0;i<=n;i++) x[i]=0;
backtrace(1);
return sum;
}
private static boolean place(int k)
{
for(int j=1;j<k;j++)
if((Math.abs(k-j))==Math.abs(x[j]-x[k])||(x[j]==x[k]))
return false;
return true;
}
private static void backtrace(int t)
{
if(t>n)
{
sum++;
for(int i=1;i<=n;i++)
System.out.println(" "+x[i]);
System.out.println("it is the "+sum+"th:\n");
}
else
for(int i=1;i<=n;i++)
{
x[t]=i;
if(place(t)) backtrace(t+1);
}
}
}