八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

1.方案1：用二维数组表示棋盘，回溯搜索

/**
 * 回溯，深度优先搜索，递归
 * @author LENOVO
 *
 */
public class 八皇后问题 {
	public static boolean visit[][]=new boolean[8][8];//标记棋盘数组
	public static int c=0;//记录答案
	public static void main(String[] args) {//主函数
		dfs(0);
		System.out.println("答案："+c);
	}
	public static void dfs(int y) {//y表示放第y个皇后，dfs搜索
		if(y>=8) {//如果八个皇后已放满
			c++;
			System.out.println("--------------------------第"+c+"个答案----------------------");
			System.out.println();
			for(int i=0;i<8;i++) {
				for(int j=0;j<8;j++) {
					System.out.print((visit[i][j]?"1":"0")+"\t");
				}
				System.out.println();
			}
			return;
		}
		for(int i=0;i<=7;i++) {//循环遍历8列
		        //可以放否，可以，继续递归搜索，否则回归
			if(hang(i)&&lie(y)&&xiangxian1(i,y)&&xiangxian4(i,y)) {
				visit[i][y]=true;
				dfs(y+1);
				visit[i][y]=false;
			}
		}
	}
	public static boolean hang(int x) {//判断行
		for(int i=0;i<8;i++) {
			if(visit[x][i]) {
				return false;
			}
		}
		return true;
	}
	public static boolean lie(int y) {//判断列
		for(int i=0;i<8;i++) {
			if(visit[i][y]) {
				return false;
			}
		}
		return true;
	}
	public static boolean xiangxian1(int x,int y) {//    \ 二四象限
		if(x>y) {
			x=x-y;y=0;
		}else if(x<y) {
			y=y-x;x=0;
		}else {
			x=0;y=0;
		}
		for(;x<8&&y<8;) {
			if(visit[x++][y++]) {
				return false;
			}
		}
		return true;
	}
	public static boolean xiangxian4(int x,int y) {//   / 一三象限
		int i=x,j=y;
		while(i<8&&j>=0) {
			if(visit[i++][j--]) {
				return false;
			}
		}
		while(x>0&&y<8) {
			if(visit[x--][y++]) {
				return false;
			}
		}
		return true;
	}
}

2.方案2，用一维数组代表二维数组的棋盘，一维数组的下表代表行，一维数组的值代表列，然后回溯搜索

public class Queen {	
	static int chessboard[];
	static int count=0;
	public static void main(String[] args) {
		chessboard =new int[]{-1,-1,-1,-1,-1,-1,-1,-1,-1};
		change(1);
		System.out.println(count);
	}
	public static boolean judge(int pointi,int pointj){//判断某个皇后是否与已有皇后冲突
		System.out.println(pointi+"  "+pointj);
	    for(int i=1;i<pointi;i++){
	    	System.out.println("    "+(pointi-i)+":"+(pointj-chessboard[i]));
	        if(pointj==chessboard[i])return false;//同一列
	        if((pointi-i)==(pointj-chessboard[i]))return false;//同一主对角线
	        if((pointi-i)+(pointj-chessboard[i])==0)return false;//同一副对角线
	    }
	    return true;
	}
	public static void change(int row){//在第row行找能放皇后的位置
	    for(int i=1;i<9;i++){//从1~8遍历这一行的八个空位
	        if(judge(row,i)){ //如果可以放这个位置就记录下第row个皇后的位置
	            chessboard[row]=i;
	            if(row==8){//如果八个皇后都放满了统计一下
	                count++;
	                return;
	            }
	            change(row+1);//还有皇后没放递归放下一个皇后
	        }
	    }
	    chessboard[--row]=-1;//如果这一行没有可放的位置说明上一行皇后放的位置不行，
	                        //要为上一个皇后寻找新的可放位置
	    return;
	}
}