一、 八皇后問題？

在8×8格的國際象棋上擺放8個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法？

二、思路

1.首先如何解決遞歸問題呢？

*找到遞推公式*找到遞歸出口

2.那么遞推公式是什么呢？
毫無疑問，第一個皇后在二維數組的第一行，第二個皇后在二維數組的第二行·········，那么遞推公式就肯定是n+1 了；

3.遞歸出口是什么呢？

一共8個皇后，那出口肯定就是下到第八個皇后唄

4.考慮的細節都有哪些

1.如果要計算出所有的情況，那么肯定要使用回溯算法；如果我現在皇后所下的位置是第八行的第i列，如果此時發現該位置不滿足情況，那我的i就要移動到i+1的位置，查看該位置是否符合情況；所以需要使用一個for循環對每一行進行遍歷，當該皇后在該位置不滿足情況時就向后移動一位；

2.如果我已經下到了第八個皇后，在該行遍歷結束之后，會返回到上一個皇后的調用處，然后將上一個皇后的位置進行i+1；這就是回溯的體現

3.優化，可以使用一個全局共享的一維數組用來代替二維數組，下標代表第幾行，數組數據代表皇后在每一行的第幾個位置

4.需要一個判斷函數，橫豎斜線是否相遇

三、代碼

package com.company;/*** @author:抱著魚睡覺的喵喵* @date:2021/2/22* @description:*/ public class QueenEight {private int max = 8;private int[] arr = new int[max];private static int count = 0;public static void main(String[] args) {QueenEight queenEight = new QueenEight();queenEight.check(0);System.out.printf("一共有%d解法",count);}public void check(int n) {if (n == max) {print();return;}for (int i = 0; i < max; i++) {arr[n] = i;if (judge(n)) {check(n + 1);}}}public boolean judge(int n) {for (int i = 0; i < n; i++) {if (arr[n] == arr[i] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {return false;}}return true;}public void print() {count++;for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] +" ");}System.out.println();} }

總結

以上是生活随笔為你收集整理的使用回溯算法分析八皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。