Java回溯完成八皇后问题

八皇后问题

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

这里我们创建一个一维数组map来代表棋盘并约定如下
map[x]代表第几列,x代表第几行，下标都是从零开始
完成这个问题需要创建一个方法用来检查，当前棋子是否和它后面的每一个棋子都无法攻击
如果能够相互攻击会满足以下两个条件：
1.map[x] = map[y] 表示两个棋子在同一个纵列上面
2.x-y == Math.abs(map[x]-map[y]) 这个条件看上图的坐标很容易理解，对角的坐标都会满足这个条件
下面开始完整的代码

public class EightQueen {
	// 创建一个一维数组用来存储每一种方案Result[]
	private int[] Result; 
	// 现在做出如下约定Result[x]的结果代表棋子在纵列的坐标，x代表棋盘的横列坐标
	// 定义成园变量Max表示有多少个皇后
	private int Max;
	private int count = 0; // 用来统计有多少种方法
	
	public int getCount() {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}

	public int[] getResult() {
		return Result;
	}

	public int getMax() {
		return Max;
	}

	public void setResult(int[] result) {
		Result = result;
	}

	public void setMax(int max) {
		Max = max;
	}
	
	// 定义构造方法
	
	public EightQueen(int max) {
		this.Max = max;
		Result = new int [max];
	}
	// 定义方法检查当前皇后所在位置是否符合要求
	public boolean check(int n) {
		// 检查的方法就是检查当前棋子与上一列到第一列的任意一个棋子是否能够相互攻击
		// 循环的次数为n-1
		for (int i = 0; i < n; i++) {
			// 如果两个皇后能够相互攻击必然满足两个条件之一
			// 1.在同一纵列 即Result[n] == Result[i]
			// 2.在相同的对角线上即n - i  = Math.abs(Result[n] - Result[i])这个条件不好直观，通过画图观察坐标很容易理解
			if(Result[n] == Result[i] || n - i  == Math.abs(Result[n] - Result[i])) {
				return false;
			}
		}
		return true;
	}
	
	// 定义主方法 主方法的功能是检查当前一横列从左到右的每一个位置是否能满足各个皇后不攻击的条件
	// 如果有满足，记录当前位置检查下一列 形成递归
	// 设置出口为检查到第n行结束，即有几个皇后就检查几行
	public void recall(int n) {
		if(n == Max) { // 从第0行开始到Max-1行结束，此处使用Max做判断，是因为最后一行检查完后行数还会加1
			show();
			count ++;
			return;
		}else {
			for (int i = 0; i < Max; i++) {
				Result[n] = i;
				if(check(n)) {
					recall(n + 1);
				}
			}
			
		}
	}
	
	// 创建方法用于打印每一种方案
	public void show() {
		for (int i = 0; i < Max; i++) {
			System.out.print(Result[i]);
		}
		System.out.println();
	}

	public int getCount1() {
		// TODO Auto-generated method stub
		return this.count;
	}
}

然后编写一个测试类用来测试

public class EightQueensTest {
	public static void main(String[] args) {
		EightQueen eq = new EightQueen(8);
		eq.recall(0);
		System.out.println(eq.getCount());
	}	
}

这里可以把8替换成任意的数字即代表n皇后问题