八皇后問題
八皇后問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即:任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
解決思路
①第一個皇后先放第一行第一列。
②第二個皇后放在第二行第一列、然后判斷是否OK，如果不0K， 繼續放在第二列、第三列、依次把所有列都放完，找到一個合適。
③繼續第三個皇后， 還是第一列、第二列…直到第8個皇后也能放在一個不沖突的位置，算是找到了一個正確解。
④當得到一個正確解時，在棧回退到上一個棧時，就會開始回溯，即將第一個皇后，放到第一列的所有正確解，全部得到。
⑤然后回頭繼續第-一個皇后放第二列，后面繼續循環執行①②③④的步驟。
代碼實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
/** * @Author: Yeman * @Date: 2021-10-31-15:48 * @Description: */public class Queue8 { int max = 8; //8個皇后 int[] arr = new int[max]; //下標為第幾個（即第幾行），值為第幾列 static int count = 0; //多少個放法 static int judgeCount = 0; //判斷了多少次 public static void main(String[] args) { Queue8 queue8 = new Queue8(); queue8.check(0); System.out.printf("一共有%d種解法\n",count); System.out.printf("一共判斷了%d次",judgeCount); } //用來放置第n個皇后 private void check(int n){ if (n == max){ //n為8相當于是第九個皇后了，說明已經全部放好了 print(); return; } for (int i = 0; i < arr.length; i++) { arr[n] = i; if (judge(n)){ //不沖突 check(n+1); } } } //用來第n個皇后判斷與前面的所有皇后是否沖突 private boolean judge(int n){ judgeCount++; for (int i = 0; i < n; i++) { //是否同列同斜線 if (arr[i] == arr[n] || Math.abs(arr[i]-arr[n]) == Math.abs(i-n)){ return false; } } return true; } //輸出每一種放法 private void print(){ count++; for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); }} |
運行結果
（截取部分）
到此這篇關于Java使用遞歸回溯完美解決八皇后的問題的文章就介紹到這了,更多相關Java 遞歸回溯內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/m0_46653805/article/details/121065552
