回溯法解决n皇后问题

/**
 * 
 * @author chenzhuzuo	
 * @version2011.06.21
 * 回溯法求N皇后问题
 *
 */
public class NQueen {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		queen(4);

	}
	/**
	 * 
	 * @param n 有n个皇后
	 */
	private static void queen(int n){
		int result[]= new int [n+1];//result[i]=n表示第i个皇后放在第i行第n列上
		for(int i=0;i<=n;i++){
			result[i]=0;
		}
		int k=1;
		while(k>=1){
			result[k]+= 1;
			while(result[k]<=n){
				if(isOk(result,k))break;
				else result[k]+=1;
			}
			if(k==n&&result[k]<=n){
				for(int i=1;i<=n;i++){
					System.out.print(result[i]+" ");
					
				}
				System.out.println();
				//return;
			}else if(result[k]<=n){
				k=k+1;
			}else{//回溯
				result[k]=0;
				k=k-1;
				
			}
		}
	}
	//放置皇后时判断是否合法
	private static boolean isOk(int a[],int k){
		for(int i=1;i<k;i++){
			if(a[i]==a[k]||Math.abs(k-i)==Math.abs(a[k]-a[i]))return false;
		}
		return true;
	}

}