nqueen.java

n皇后问题:计算各种情况下的棋盘上皇后的摆放位置

/**
 * 
 * @author wangwei
 * @see This class is used to solve the <h1>N Queeen</h1>
 * @since 2007-11-29
 */
public class NQueen {
	/**
	 * @param n:int the quantity of the queen
	 * @param x:int[] the current solution
	 * @param sum:long the available method 
	 */
	static int n = 6;
	static int[] x;
	static long sum;
	public static void main(String[] args){
        long result = NQueen.nQueen(n);
        System.out.println();
		System.out.println("解的个数为：");
	    System.out.print(result);
	}
	/**
	 * 解决N皇后问题的主要函数,它调用了一个非递归迭代回溯函数{@code backtrack}来
	 * 实现回溯
	 * <p>
	 * @author wangwei
	 */
	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++;
					for(int element:x){
						if(element != 0){
							System.out.print(element + "-----");					
						}

					}
					System.out.println();
				}
				else{
					k++;
					x[k] = 0;
				}
			else{
				k--;
			}
		}
	}

}