遞回之八皇后問題
1、問題描述
在國際象棋棋盤，每行棋盤放置一個皇后，使得所有皇后均不在一條直線或者對角線上，
2、解決思路
- 將第一個皇后放在第一行第一列
- 第二個皇后放在第二行第一列，判斷是否與上面放置的皇后沖突，沖突則繼續放在第二列，第三列
- 重復放置直到第八個皇后
- 會有回溯的產生，即找到第一個皇后放在第一行第一列的初始條件解法后，會將第一個皇后放在第一行第二列（實際上，在第一種初始下，2 3…皇后都會有回溯，詳情見代碼）
- 第一個皇后放在第一行第二列，重復上述，然后第一個皇后放在第一行第三列，，，繼續重復，遍歷解決
3、Java代碼實作
package test.recursion;
/**
* @author shkstart
* @create 2021-01-08 11:41
*/
//用一維陣列代替二維陣列 arr[8]={0 4 7 5 2 6 1 3] 0代表第一個皇后放在第一行第一列 4代表第二個皇后放在第二行第5列
//7代表第三個放在第三行第8列 .....省去判斷不同皇后同行的可能
public class queue8 {
int max = 8; //皇后個數
static int count = 0; //判斷有幾種解法
static int num = 0; //判斷檢測沖突次數
int[] arr = new int[max];
public static void main(String[] args) {
queue8 queue8 = new queue8();
queue8.check(0);
System.out.println(count);
System.out.println(num);
}
//遞回
private void check(int n) {//n 為0-7，代表第n+1個皇后
if (n == max) {
print(); //n=8 退出
return;
}
//依次放，并判斷OK?
for (int i = 0; i < max; i++) {
arr[n] = i;
if (adjust(n)) {
check(n + 1); //如果不沖突，接著放n+1
} else {//關鍵
//adjust(4)在i=0時不沖突，進入adjust（5），如果沖突了，即adjust（5）=i(i=0)沖突了，將不執行adjust（6），而是進行for回圈，adjust（5）=i（i=1），繼續判斷沖突...
//如果adjust（5）=i遍歷全部仍然沖突，將回溯到adjust(4)，進行遍歷，即adjust(4)在i=1時
//包含了多層嵌套
}
}
}
//檢測是否沖突
private boolean adjust(int n) {
num++;
for (int i = 0; i < n; i++) {
if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) //同一列或者||斜線 類似斜率 arr[i]代表的是第i+1個的所在列數+1
return false;
}
return true;
}
//列印輸出 ，每輸出一次，即為一種解法，參考check（）的該方法的使用
private void print() {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
count++;
System.out.println();
}
}
上述共92種解法
關于上述遞回的程序，下面給個簡單的例子幫助
public static void test(int n) {
if (n > 2) {
test(n - 1);
} //else {
System.out.println("n=" + n);
//}
}
輸入n=4時，將進入test(3), test（3）進入test（2），test（2）不滿足If 直接輸出n=2，此時程式并沒有結束，因為test（3）后還有一個輸出陳述句，即test（3）{
test（2）;sysout();}
同理test（4），最后答案為 n=2 n=3 n=4 ，
PS：學自尚硅谷的總結，打call!
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/246828.html
標籤：java
上一篇：Spring boot小白第一天 spring概述和簡述
下一篇：藍橋杯第十二屆第二期模擬賽