利用遞歸解決八皇后問題
- 2020 年 3 月 9 日
- 筆記
1.什麼是八皇后問題？
遊戲的一種，感興趣的小夥伴可以去玩一下。規則如下： 在 8 * 8 的棋盤上，任何兩個皇后都不能處於同一行同一列或同一個斜線上。
2.什麼是遞歸？ 關於遞歸的簡單描述
3.解決方式
package xmht.datastructuresandalgorithms.datastructure; /** * @author shengjk1 * @date 2020/3/4 */ /* 8皇后問題，在 8 * 8 的棋盤上，任何兩個皇后都不能處於同一行同一列或同一個斜線上。 1.第一個皇后先放第一行第一列 2.第二個皇后放在第二行第一列，然後判斷是否ok，如果不 ok，繼續放在第二列、第三列，依次把所有列都放完，找到一個合適的 3.繼續第三個皇后，還是第一列、第二列......直到第8個皇后也能放在一個不衝突的位置，算是找到了一個正確的解。 4.當得到第一個正確解時，在棧回退到上一個棧時，就會開始回溯，即將第一個皇后，放到第一列的所有正確解全部找到。 5.然後回頭繼續第一個皇后放第二列，後面繼續循環執行1234步驟。 理論上應該創建一個二維數組來表示棋盤，但是實際上可以通過算法，用一個一維數組即可解決問題。arr[8]={0,1,2,3,4,5,6,7} 對應的 arr 下標 表示第幾行，即第幾個皇后，arr[i]=val,val表示第i+1個皇后，放在第i+1行的第val+1列。 */ public class Queue8 { //定義一個有多少個皇后 int max = 8; //定義數組 arrya,保存皇后存放位置的結果。 int[] array = new int[max]; // int[] array = {-1, -1, -1, -1, -1, -1, -1, -1}; static int count = 0; public static void main(String[] args) { Queue8 queue8 = new Queue8(); // 從第 0 行開始 queue8.check(0); System.out.println(count); } //這一塊會有遞歸會有回溯，其實還是挺巧妙的，很值得細細體會。 private void check(int n) { //相當於該放第 9 個皇后了 if (n == max) { count++; print(); return; } //依次放入皇后，並判斷是否衝突 //這個的max 其實是列數 for (int i = 0; i < max; i++) { //先把皇后 n 放到該行的第一列 array[n] = i; //判斷當放置第 n 個皇后置第 i列時，是否與之前的n-1個皇后衝突 if (judge(n)) { //不衝突，就接着放下一個皇后。 check(n + 1); } } } /* 1.arrya[i]==arrya[n]表示判斷第n個皇后是否與前面 n-1 個皇后在同一列 2.Math.abs(n - i) == Math.abs(array[n] - array[i])表示判斷第 n 個皇后是否與第 i 個皇后在同一個斜線上。(列差等於行差，肯定在同一個斜線上) 3.沒有必要判斷是否在同一行，因為 n 就是表示的第幾行，而 n 是形參，是不斷變化的 */ private boolean judge(int n) { for (int i = 0; i < n; i++) { if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { return false; } } return true; } //輸出皇后的位置 private void print() { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
4.其他 現在有點體會到，遞歸解決迷宮問題的巧妙之處了。
