nqueen2.java

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

//n后问题 P166 迭代回溯

public class NQueen2 {
        
    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();
    	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()
    {
    	x[1]=0;
    	int k=1;
    	while(k>0){
    		x[k]+=1;
    		while((x[k]<=n)&&!(place(k)))x[k]+=1;
    		if(x[k]<=n)
    			if(k==n)sum++;
    			else{
    				k++;
    				x[k]=0;
    			}
    		else k--;
    	}
    }

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