最近学习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) { HashSethashSet = 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("非八皇后"); } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)