nqueen1.java

,《算法设计与分析》王晓东编著

//n后问题 P165

public class NQueen1 {
        
    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;
    	backtrack(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 backtrack(int t)
    {
    	if(t>n)sum++;
    	else
    		for(int i=1;i<=n;i++){
    			x[t]=i;
    			if(place(t))backtrack(t+1);
    		}
    }

    public static void main(String[] args) {
        // TODO code application logic here
        
        System.out.println(nQueen(4));
    }
}