八皇后问题递归Java实现

八皇后问题递归java实现

八皇后问题是指将八个皇后放置在8*8的国际棋盘上，使其两两之间不处于同一行同一列和同一斜线上。
递归解体思路为：

1. 首先n=0，i=0，代表初始在第0行第0列放置第1个皇后
2. 如果n=8，则八个皇后已经放完，输出当前的结果，并返回
3. 在第 n 行第 i 列放置第 n+1 个皇后（同一个n）
4. 判断该皇后是否与之前的所有皇后冲突，若冲突则列数 i + 1 重复进行第4步，若不冲突则n+1，重复进行第二步

存在问题：使用递归，算法效率低

具体实现代码如下：

public class EightQueens {
	/*  
	 * arr[n]=i 表示第i个皇后放在棋盘的第n行,第i列
	 * max代表皇后的个数8
	 * times记录解法个数
	 *  
	 */
	static int[] arr = new int[8];
	static int max = 8;
	static int times = 0;
	
	public static void main(String[] args) {
		check(0);
	}
	/*
	 * check递归进行皇后的放置参数n代表放置第n个皇后
	 */
	private static void check(int n) {
		//因为索引从0开始，所以n==max时表示八个皇后都放置完成，次数加一并打印当前的结果
		if (n == max) {
			times++;
			print();
			return;
		}
		//循环放置当前行的皇后的位置
		for (int i = 0; i < max; i++) {
			//试放一下
			arr[n] = i;
			//判断当前试放的皇后是否合理（与之前的皇后不处于同一列和同一斜线）
			if (judge(n)) {
				//若合理则可以放置下一行的下一个皇后。
				check(n+1);
			}
		}
	}
	
	//打印函数用于输出当前的结果和累计结果数
	private static void print() {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " " );
		}
		System.out.print(times);
		System.out.println();
	}
	//判断函数用于判断当前皇后位置是否合理
	private static boolean judge(int n) {
		//循环与已经放置的皇后位置进行判断
		for (int i = 0; i < n; i++) {
			//因为放置皇后时按行放置，因此不可能处于同一行，仅判断列和斜线即可
			//若列的位置相同或处于同一斜线（行距和列距相同即为处于同一斜线）则返回false
			if (arr[i] == arr[n] || Math.abs(n-i) == Math.abs(arr[n]-arr[i])) {
				return false;
			}
		}
		//不冲突则返回true
		return true;
	}
	
}