Java找八皇后问题的所有解

Java找八皇后问题的所有解 利用Java找八皇后问题的所有解

最近学习java，巩固一下递归的知识，花了俩小时找出八皇后的所有解。

import java.util.HashSet;
public class EightQueen {
	public static void main (String[] args){
		int[] arr = {0,0,0,0,0,0,0,0}; //找每个解
		int[][] queen_arr = new int[100][8];  //放所有解的二维数组
 		Queen queen = new Queen();
 		int a = 0;
 		while (a<100){
 			queen.eight(arr, 7, 7);
 			if (arr[0] == 10){
 				break;  //找完了所有的解，退出
 			}

 			for(int j = 0; j < 8; j++){
 				queen_arr[a][j] = arr[j];
 			}
 			arr[0]++; //找下一个解
 			a++;
 		}
		
		for (int k = 0; k < queen_arr.length; k++){
			for (int j = 0; j < 8; j++){
				System.out.print(queen_arr[k][j] + " ");
			}
			System.out.print("n");
		}
	}
}

class ArrayRepeat {  //判断数组中是否有重复元素
    public boolean cheakIsRepeat(int[] array, int num) {
        HashSet hashSet = new HashSet();
        for (int i = 0; i < num; i++) {
            hashSet.add(array[i]);
        }
        if (hashSet.size() == num) {
            return true;
        } else {
            return false;
        }
    }
}

class Queen{
	int count = 0;
	public void eight(int[] arr, int num, int max_num){
		int[] line = new int[max_num+1-num];
		int[] slash0 = new int[max_num+1-num];
		int[] slash1 = new int[max_num+1-num];
		if (num >= 0 && num <= max_num){
			if (arr[num] >= 0 && arr[num] <= max_num){
				for (int i = num; i < max_num+1; i++){
					line[i-num] = arr[i];
					slash0[i-num] = i + arr[i];
					slash1[i-num] = i - arr[i];
				}
				ArrayRepeat array_repeat = new ArrayRepeat();
				if (array_repeat.cheakIsRepeat(line,max_num+1-num) && array_repeat.cheakIsRepeat(slash0,max_num+1-num) 
					&& array_repeat.cheakIsRepeat(slash1,max_num+1-num)) { //判断是否符合要求
					if (num == 0){
						return;
					}else{
						eight(arr, num-1, 7);  //该列满足，找下一列解元素
					}
				}else{
					arr[num]++;
					eight(arr, num, 7);  //该列不满足，继续找
				}
			}else{
				if (num == max_num){
					arr[0] = 10;  //已无解，已找到所有解，给个标志退出循环
					return;
				}else{
					arr[num] = 0;
					arr[num+1]++;
					eight(arr, num+1, 7);  //该列没有满足的元素，开始回溯，修改上一列元素
				}
			}
		}else{
			System.out.println("非八皇后");
		}
	}
}