算法概念

• 回溯算法是類似枚舉的深度優先搜索嘗試過程，主要是再搜索嘗試中尋找問題的解，當發生不滿足求解條件時，就會”回溯“返回（也就是遞歸返回），嘗試別的路徑求解。

經典例子 - N皇后問題

什么是N皇后問題？

N皇后問題研究的是：如何將ｎ個皇后放在n * n的棋盤上，并且使皇后彼此之間不能相遇，也就是一個皇后的上下左右、以及斜著對角線上都不能有另外一個皇后，也就是一個皇后在 ”米“ 的視線中不能遇到另外一個皇后。

實現思路

如上圖，我們可以把這個問題劃分成8個階段，依次將8個棋子放到第一行、第二行…第八行。在放置的過程中，我們不停的檢查當前的方法是否滿足要求。如果滿足，繼續下一行放置，如果不滿足，就再換一種方法，繼續嘗試。

實現代碼：

package com.xxliao.algorithms.backtrack;/*** @author xxliao* @description: N皇后問題 求解* @date 2024/6/1 0:14*/
public class NQueens {public static void main(String[] args) {NQueens queens=new NQueens();queens.setQueens(0);queens.printQueens();}// 皇后數量static int queens_count = 8;// 定義數組來存在皇后，索引表示行，值表示皇后存在改行的那一列中int[] array = new int[queens_count];/*** @description  根據行號，設置該行的皇后位置* @author  xxliao* @date  2024/6/1 0:17*/public void setQueens(int row) {if(row == queens_count) {// 遞歸結束條件return;}// 嘗試每一列放置，如果沒有合適的，就返回上一層for(int column = 0; column <queens_count; column++) {if(isOk(row,column)) {// 符合條件，放置array[row] = column;// 然后設置下一行setQueens(++row);}}}/*** @description  判斷改行該列是否 符合條件* @author  xxliao* @date  2024/6/1 0:23*/private boolean isOk(int row, int column) {// 定義左上角、右上角 列索引標記int leftup = column - 1;int rightup = column + 1;// 然后從當前行逐行向上遍歷，看當前row、column是否滿足條件for(int i = row-1; i >= 0; i--) {if(array[i] == column){// 如果該位置已經有了皇后了，不滿足return false;}if(leftup >=0 && array[i] == leftup) {//左上對角線存在queen,第一次執行是當前行，肯定不滿足條件，i--，leftup--之后就是當前點的左上角位置return false;}if(rightup < queens_count && array[i] == rightup) {//右下對角線存在queen，同上理由return false;}leftup--;rightup++;}return true;}/*** @description  打印N皇后棋盤* @author  xxliao* @date  2024/6/1 0:34*/private void printQueens() {for (int i = 0; i < queens_count; i++) {for (int j = 0; j < queens_count; j++) {if (array[i] == j) {System.out.print("Q| ");}else {System.out.print("*| ");}}System.out.println();}System.out.println("-----------------------");}
}

演示結果：