算法与数据结构-03-八皇后问题（递归回溯）

小半 • 2023年12月18日下午3:05 • 后端开发 • 阅读 112

思路：

找出八皇后有多少种摆法，其实就是暴力穷举，思路如下：

第一个个皇后先放第一行第一列
第二个皇后放在第二行第一列，然后判断是否符合规则，如果不符合规则，则继续放在第 2 列，依次把所有列都放完，找到一个合适的列（某一遍）
继续第 3 个皇后，直到 8 个皇后都放到了棋盘上，并且没有违反规则，就算一个解答
当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后放在第一列的所有正确解全部拿到
然后回头继续第一个皇后放第二列，后面继续循环执行前面 4 步

理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}，这个是存储结果，数组下标表示第几行，对应的值则为在那一列上摆放着

代码：

 1 package sgq0321;
 2 
 3 import java.util.Arrays;
 4 
 5 /*
 6  * @Author: sgq
 7  * @Date: 2022/3/21 11:16
 8  * @Description:
 9  */
10 public class Queen8 {
11      int max=8;
12      int[] arr=new int[max];
13      int counter=0;
14 
15     public static void main(String[] args) {
16         Queen8 queen8 = new Queen8();
17         queen8.check(0);
18     }
19 
20     public void check(int n){
21         // 如果n==9 停止递归，成功生成一种方案
22         if(n==max){
23             counter++;
24             print();
25             return;
26         }
27         // 否则继续查找合理方案
28         for (int i = 0; i < max; i++) {
29             arr[n]=i;
30             if(judge(n)){
31                 check(n+1);
32             }
33         }
34 
35     }
36 
37     // 判断n行放置皇后是否合理（是否与前面n-1行冲突）
38     private boolean judge(int n) {
39         for (int i = 0; i < n; i++) {
40             if(arr[n]==arr[i] || Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
41                 return false;
42             }
43         }
44         return true;
45     }
46 
47     // 打印每次成功的方案
48     public void print(){
49         System.out.print("counter-"+counter+": ");
50         System.out.println(Arrays.toString(arr));
51     }
52 
53 
54 }

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/187631.html

算法与数据结构-03-八皇后问题（递归回溯）

相关推荐