回溯法求解八皇后问题，主要就是寻找状态空间树，然后利用判断函数剪去一些不符合的解，相比较枚举运算量更少

package com.huat.algorithm;

import java.util.Scanner;

/**
 * @author yanzz       
 * @编辑时间:2018年3月22日
 * @功能说明:N皇后，回溯法求解 
 * 
 * 	回溯法的即被概念:使用剪枝函数的深度优先方式生成的状态空间树中的结点求解方法称为回溯法
 * 
 * 回溯法: 1)显示约束，确定每个xi取值的约束条件成为显示约束。
 * 		2）隐式约束:给出判断一个候选解是否是可行解
 * 		3）代价函数:用来衡量每个可行解的优劣，使目标函数去最值的可行解为问题的最优解
 * 		4）状态空间树
 * @version:
 */
public class NQueens {
	
	//
	private static boolean place(int k,int i, int[] tail) {
		//判断两个皇后是否在同一列或在同一斜线上
		for(int j = 0; j < k; j++) {
			
			if(tail[j] == i || Math.abs(tail[j] - i) == Math.abs(j - k) ) {
				return false;
			}
		}
		return true;
	}
	
	public static void seek(int k, int n, int[] temp) {
		
		for(int i = 0; i < n; i++) {		//显示约束
			
			if(place(k,i,temp)) {			//约束函数
				temp[k] = i;
				
				if(k == n -1) {
					for(int m : temp) {
						System.out.printf("%d",m);
					}
					System.out.println();
				} else {
					seek(k+1,n,temp);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		n = sc.nextInt();
		int[] x = new int[n];	//最有解空间
		seek(0,n,x);
		sc.close();
	}
}