【算法】回溯法四步走
- 2020 年 3 月 13 日
- 筆記
回溯法
對於回溯法，網上有很多種解釋，這裡我依照自己的（死宅）觀點做了以下三種通俗易懂的解釋：
-
正經版解釋：其實人生就像一顆充滿了分支的n叉樹，你的每一個選擇都會使你走向不同的路線，獲得不同的結局。如果能重來，我要選李白~呸！說錯了，如果能重來，我們就能回溯到以前，選擇到最美好的結局。
-
遊戲版解釋：玩過互動電影遊戲（如 行屍走肉）的都知道，你的每個選擇都會影響遊戲的結局，掌控他人的生死。每次選擇錯誤導致主角或配角死亡，我們是不是回溯讀檔，希望得到一個更好的結局。
PS：克萊曼婷天下無敵！
-
動漫版解釋：看過主角擁有死亡回歸（瘋狂暗示486）的都知道，主角的每個選擇都能影響大局，可是486直接能回溯重選，這與我們今天要講的回溯法極其相似。
PS：愛蜜莉雅、雷姆我都要！
專業名詞
- 解空間：即 所有的可能情況
概念
回溯算法：是類似於枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就「回溯」返回，嘗試別的路徑。
它是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術稱為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」（你也可以理解為存檔點）。
上圖為八皇后的解空間樹，如果當前點不符合要求就退回再走。
許多複雜的，規模較大的問題都可以使用回溯法，有「通用解題方法」的美稱。
基本思想
在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。
當探索到某一結點時，要先判斷該結點是否包含問題的解：
- 如果包含，就從該結點出發繼續探索下去；
- 如果該結點不包含問題的解，則逐層向其祖先結點回溯。（其實回溯法就是對隱式圖的深度優先搜索算法）
結束條件：
- 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。
- 若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。
網上的一般步驟
雖然我覺得網上的一般步驟太抽象了，但是還是擺在這裡供大家參考吧。。
-
針對所給問題，確定問題的解空間：
首先應明確定義問題的解空間，問題的解空間應至少包含問題的一個（最優）解。 -
確定結點的擴展搜索規則：
及時確定規則，並不是每個解空間都要走完才能發現是死路的，有時候走到一半就發現不滿足條件了。 -
以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索：
不滿足條件的路徑及時剪掉（即 剪枝），避免繼續走下去浪費時間。類比：比如說削蘋果，
我們規定：蘋果皮必須不斷，要完整地削完整個蘋果。
那麼，如果我們削到一半蘋果皮斷掉了，我們就可以直接退回去（即 回溯）換個蘋果削了，如果繼續削下去，只會浪費時間。
算法框架
問題框架：
設問題的解是一個n維向量(a1,a2,………,an)，約束條件是ai(i=1,2,3,…..,n)之間滿足某種條件，記為 f(ai)。
非遞歸回溯框架
其中，a[n]為解空間，i為搜索的深度，框架如下：
int a[n],i; //a[n]為解空間，i為深度 初始化數組 a[]; i = 1; while (i>0(有路可走) and (未達到目標)) { //還未回溯到頭 if(i > n) { //搜索到葉結點 搜索到一個解，輸出； } else { //處理第 i 個元素 a[i]第一個可能的值； while(a[i]在不滿足約束條件且在搜索空間內) { a[i]下一個可能的值； }//while if(a[i]在搜索空間內) { 標識佔用的資源； i = i+1; //擴展下一個結點 } else { 清理所佔的狀態空間； //回溯 i = i – 1; }//else }//else }//while遞歸回溯框架
回溯法是對解空間的深度優先搜索，在一般情況下使用遞歸函數來實現回溯法比較簡單。
其中，a[n]為解空間，i為搜索的深度，框架如下：
int a[n]; //a[n]為解空間 BackTrace(int i) { //嘗試函數，i為深度 if(i>n) { 輸出結果; } else { for(j = 下界; j <= 上界; j=j+1) { //枚舉 i 所有可能的路徑 if(check(j)) { //檢查滿足限界函數和約束條件 a[i] = j; ... //其他操作 BackTrace(i+1); 回溯前的清理工作（如 a[i]置空值等）; }//if }//for }//else }//BackTrace回溯四步走
由於上述網上的步驟太抽象了，所以在這裡我自己總結了回溯四步走：
-
編寫檢測函數：檢測函數用來檢測此路徑是否滿足題目條件，是否能通過。
這步不做硬性要求。。不一定需要
-
明確函數功能：要清楚你寫這個函數是想要做什麼；
-
尋找遞歸出口：一般為某深度，或葉子節點。
-
明確所有路徑（選擇）：這個構思路徑最好用樹形圖表示。
例如：走迷宮有上下左右四個方向，也就是說我們站在一個點處有四種選擇，我們可以畫成無限向下延伸的四叉樹。
直到向下延伸到葉子節點，那裡便是出口；
從根節點到葉子節點沿途所經過的節點就是我們滿足題目條件的選擇。 -
回溯還原現場：若該節點所有選擇已做完卻仍然沒有找到出口，那麼我們需要回溯還原現場，將該節點重置為初始狀態，回溯到一切都沒有發生的時候，再退回去。
注意：回溯還原現場是必要的，如果不還原現場，那你的回溯有什麼意義呢。。
類比：大雄出意外了，哆啦A夢坐時空機回到過去想要改變這一切，結果過去的一切都沒有被重置到初始狀態，回到過去大雄還是現在這種受傷的樣子沒有改變，那麼回到過去有什麼意義呢。
編寫檢測函數（非必須）
第一步，寫出檢測函數，來檢測這個路徑是否滿足條件，是否能通過。
這個函數依據題目要求來編寫，當然，如果要求不止一個，可能需要編寫多個檢測函數。
例如：湊算式
這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。
比如：
6+8/3+952/714 就是一種解法，
5+3/1+972/486 是另一種解法。
這個算式一共有多少種解法？
要做出這個題，
第一步，要寫出檢測函數
public static int sum = 0; // 用來存放總共的解法數 public static double[] a = new double[10]; // 判斷數組裡前j個元素是否與t相同 /** * @param a 傳入一個數組a * @param j 判斷前j個元素 * @param t 是否與t相同 * @return */ public static boolean same(double[] a, int j, int t) { for (int i = 1; i < j; i++) { if (a[i] == t) { return true; } } return false; } /** * @param a 判斷a數組是否滿足表達式 * @return 如果滿足就true，不滿足就false */ public static boolean expression(double[] a) { if ((a[1] + a[2] / a[3] + (a[4] * 100 + a[5] * 10 + a[6]) / (a[7] * 100 + a[8] * 10 + a[9]) == 10)) return true; else return false; }明確函數功能
由於此題要填數字，所以我們定義choose(i)的含義為：在算式中自動填入數字 i 。
尋找遞歸出口
第二步，要尋找遞歸出口，當1~9均已填入後，判斷表達式是否成立，若成立，則輸出。
// 如果選擇的數字大於9，則代表1~9均已選完，判斷是否滿足表達式，輸出選擇的表達式 if (i > 9) { if (expression(a)) { for (int x = 1; x < 10; x++) { System.out.print(a[x] + " "); } System.out.println(); sum++; } return; }明確所有路徑
第三步，要知道這個遞歸是幾個選擇，即 幾叉樹。
此題為1~9九個選擇，九條路，九叉樹。
for (int j = 1; j <= 9; j++) { // 如果將要填入的數與前面不衝突，則填入 if (!same(a, i, j)) { a[i] = j; choose(i + 1); } }回溯還原現場
第四步，若該節點沒有找到出口，則將當前位置回溯，還原現場，重新選擇
在本題中，還原現場即 重置為0（表示還未填入1~9的數字）
for (int j = 1; j <= 9; j++) { // 如果將要填入的數與前面不衝突，則填入 if (!same(a, i, j)) { a[i] = j; choose(i + 1); //若沒有找到出口，則將當前位置重置為0，回溯，還原現場 a[i] = 0; } }實例
湊算式
這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。
比如：
6+8/3+952/714 就是一種解法，
5+3/1+972/486 是另一種解法。
這個算式一共有多少種解法？
答案：
// 湊算式 public class Sy1 { public static void main(String[] args) { // TODO Auto-generated method stub choose(1); System.out.println("一共"+sum+"種解法"); } public static int sum = 0; // 用來存放總共的解法數 public static double[] a = new double[10]; // 判斷數組裡前j個元素是否與t相同 /** * @param a 傳入一個數組a * @param j 判斷前j個元素 * @param t 是否與t相同 * @return */ public static boolean same(double[] a, int j, int t) { for (int i = 1; i < j; i++) { if (a[i] == t) { return true; } } return false; } /** * @param a 判斷a數組是否滿足表達式 * @return 如果滿足就true，不滿足就false */ public static boolean expression(double[] a) { if ((a[1] + a[2] / a[3] + (a[4] * 100 + a[5] * 10 + a[6]) / (a[7] * 100 + a[8] * 10 + a[9]) == 10)) return true; else return false; } /** * @param i 選擇第i個數字 遞歸 */ public static void choose(int i) { // 如果選擇的數字大於9，則代表1~9均已選完，輸出選擇的表達式 if (i > 9) { if (expression(a)) { for (int x = 1; x < 10; x++) { System.out.print(a[x] + " "); } System.out.println(); sum++; } return; } for (int j = 1; j <= 9; j++) { // 如果將要填入的數與前面不衝突，則填入 if (!same(a, i, j)) { a[i] = j; choose(i + 1); //若沒有找到出口，則將當前位置重置為0，回溯，還原現場 a[i] = 0; } } } }程序運行結果：
3.0 5.0 1.0 9.0 7.0 2.0 4.0 8.0 6.0 4.0 9.0 3.0 5.0 2.0 8.0 1.0 7.0 6.0 5.0 3.0 1.0 9.0 7.0 2.0 4.0 8.0 6.0 5.0 4.0 3.0 7.0 2.0 6.0 1.0 9.0 8.0 5.0 4.0 9.0 7.0 3.0 8.0 1.0 6.0 2.0 5.0 8.0 6.0 4.0 7.0 3.0 1.0 2.0 9.0 6.0 4.0 2.0 3.0 5.0 8.0 1.0 7.0 9.0 6.0 4.0 2.0 7.0 1.0 8.0 3.0 5.0 9.0 6.0 7.0 3.0 4.0 8.0 5.0 2.0 9.0 1.0 6.0 8.0 3.0 9.0 5.0 2.0 7.0 1.0 4.0 6.0 9.0 8.0 4.0 3.0 7.0 1.0 5.0 2.0 7.0 1.0 4.0 9.0 6.0 8.0 3.0 5.0 2.0 7.0 3.0 2.0 8.0 1.0 9.0 5.0 4.0 6.0 7.0 3.0 2.0 9.0 8.0 1.0 6.0 5.0 4.0 7.0 5.0 3.0 2.0 6.0 4.0 1.0 9.0 8.0 7.0 5.0 3.0 9.0 1.0 2.0 6.0 8.0 4.0 7.0 9.0 6.0 3.0 8.0 1.0 2.0 5.0 4.0 7.0 9.0 6.0 8.0 1.0 3.0 5.0 4.0 2.0 8.0 1.0 3.0 4.0 6.0 5.0 2.0 7.0 9.0 8.0 6.0 9.0 7.0 1.0 2.0 5.0 3.0 4.0 8.0 7.0 6.0 1.0 9.0 5.0 2.0 3.0 4.0 9.0 1.0 3.0 4.0 5.0 2.0 6.0 7.0 8.0 9.0 1.0 3.0 5.0 2.0 4.0 7.0 8.0 6.0 9.0 2.0 4.0 1.0 7.0 8.0 3.0 5.0 6.0 9.0 2.0 4.0 3.0 5.0 8.0 7.0 1.0 6.0 9.0 3.0 4.0 1.0 5.0 7.0 6.0 2.0 8.0 9.0 4.0 8.0 1.0 7.0 6.0 3.0 5.0 2.0 9.0 4.0 8.0 3.0 5.0 6.0 7.0 1.0 2.0 9.0 6.0 8.0 1.0 4.0 3.0 5.0 7.0 2.0 一共29種解法方格填數
如下的10個格子填入0~9的數字。
- 要求：連續的兩個數字不能相鄰。（左右、上下、對角都算相鄰）
一共有多少種可能的填數方案？
答案：
// 方格填數 public class Sy2 { public static void main(String[] args) { // TODO Auto-generated method stub Block bk = new Block(); bk.init(); bk.addNum(0);// , 0, 0); System.out.println("一共"+Block.sum+"種方案"); } } class Block { public int[][] b = new int[3][4]; public static int sum; /** * 初始化整個數組 */ public void init() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { b[i][j] = -2; } } } /** * @param y y行 * @param x x列 * @param n 填數n * @return 返回此方格是否能填數 */ public boolean isAble(int y, int x, int n) { // y行 x列 填數n if (b[y][x] != -2) return false; for (int j = y - 1; j <= y + 1; j++) { for (int i = x - 1; i <= x + 1; i++) { if (j < 3 && j >= 0 && i < 4 && i >= 0) { if (b[j][i] == n - 1 || b[j][i] == n + 1) { return false; } } } } return true; } /** * @param n 填入數字n */ public void addNum(int n) { if (n > 9) { sum++; return; } for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { if ((i == 0 && j == 0) || (i == 2 && j == 3)) continue; // 如果此方格能填數，則填入數字 if (this.isAble(i, j, n)) { b[i][j] = n; this.addNum(n + 1);// , y, x+1); b[i][j] = -2; // 當加入下一個不行返回後，還原現在方塊，繼續循環 } } } } }程序運行結果：
一共1580種方案蛙跳河
在一個 5*5 的地圖上，一隻蛙欲從起點跳到目的地。中間有一條河（如圖），但這隻蛙不會游泳，並且每次跳只能橫着跳一格或者豎著跳一格。（聰明的蛙不會跳已經跳過的路）
- 總共有多少種跳法。
- 給出路徑最短的跳法。
答案：
- 明確函數功能：jump(m, n)為跳到(m, n)位置。
- 尋找遞歸出口：不在邊界之內 或 已走過。
- 明確所有路徑：右跳、左跳、下跳、上跳
- 回溯還原現場：
path–; // 回溯法關鍵步驟
a[m][n] = 0;
//青蛙跳 public class Sy1 { static int count = 0; // 跳法種類計數 static int x = 4, y = 4; // 目的坐標 static int step = 0; // 記錄步數 // 地圖，0代表沒有走過，1 代表已經走過 static int[][] map = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 1, 1, 0, 1, 1 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } }; static int min = 25; // 用來記錄最小步數 static int sx[] = new int[25], sy[] = new int[25]; // 記錄坐標 // 求解總共跳法，並求出最短步數，方便下面列出路徑 static void jump(int m, int n) { if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { // 該點在地圖邊界之內並且未走過 return; } map[m][n] = 1; // 走到此節點 step++; if (m == x && n == y) { // 如果到達目的地 if (step < min)// 更新最短步數 min = step; count++; } // 所有路徑 jump(m + 1, n); // 右跳 jump(m - 1, n); // 左跳 jump(m, n + 1); // 下跳 jump(m, n - 1); // 上跳 step--; // 回溯法關鍵步驟 map[m][n] = 0; } // 列出最短步數的路徑 static void find(int m, int n) { if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { // 該點在地圖邊界之內並且未走過 return; } // 記錄坐標 sx[step] = m; sy[step] = n; // 走到此節點 map[m][n] = 1; step++; if (m == x && n == y && step == min) { // 到達目的且為最短路徑 int p = min - 1; System.out.print("最短 path:" + p + "步"); for (int i = 0; i < min; i++) System.out.print("(" + sx[i] + "," + sy[i] + ")"); System.out.println(); } find(m + 1, n); find(m - 1, n); find(m, n + 1); find(m, n - 1); step--; map[m][n] = 0; } public static void main(String[] args) { jump(0, 0); step = 0; System.out.println("總共" + count + "種解法"); find(0, 0); } }程序運行結果：
走迷宮
以一個 M×N 的長方陣表示迷宮，0 和 1 分別表示迷宮中的通路和障礙。
設計一個程序，對任意輸入的迷宮，輸出一條從入口到出口的通路，或得出沒有通路的結論。
例：
輸入：
請輸入迷宮的行數 9
請輸入迷宮的列數 8
請輸入 9 行 8 列的迷宮
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
為了方便大家觀看，我換成了矩陣：
[ begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \ end{matrix} ]
輸出：
有路徑
路徑如下：
# # 1 0 0 0 1 0
0 # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
為了方便大家觀看，我換成了矩陣：
[ begin{matrix} # & # & 1 & 0 & 0 & 0 & 1 & 0 \ 0 & # & 1 & 0 & 0 & 0 & 1 & 0 \ # & # & 1 & 0 & 1 & 1 & 0 & 1 \ # & 1 & 1 & 1 & 0 & 0 & 1 & 0 \ # & # & # & 1 & # & # & # & 0 \ 0 & 1 & # & # & # & 1 & # & 1 \ 0 & 1 & 1 & 1 & 1 & 0 & # & 1 \ 1 & 1 & 0 & 0 & 0 & 1 & # & 1 \ 1 & 1 & 0 & 0 & 0 & 0 & # & # \ end{matrix} ]
答案：這裡用棧來實現的遞歸，算是一個新思路。
//迷宮 /*位置類*/ class Position { int row; int col; public Position() { } public Position(int row, int col) { this.col = col; this.row = row; } public String toString() { return "(" + row + " ," + col + ")"; } } /*地圖類*/ class Maze { int maze[][]; private int row = 9; private int col = 8; Stack<Position> stack; boolean p[][] = null; public Maze() { maze = new int[15][15]; stack = new Stack<Position>(); p = new boolean[15][15]; } /* * 構造迷宮 */ public void init() { Scanner scanner = new Scanner(System.in); System.out.println("請輸入迷宮的行數"); row = scanner.nextInt(); System.out.println("請輸入迷宮的列數"); col = scanner.nextInt(); System.out.println("請輸入" + row + "行" + col + "列的迷宮"); int temp = 0; for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp = scanner.nextInt(); maze[i][j] = temp; p[i][j] = false; } } } /* * 回溯迷宮，查看是否有出路 */ public void findPath() { // 給原始迷宮的周圍加一圈圍牆 int temp[][] = new int[row + 2][col + 2]; for(int i = 0; i < row + 2; ++i) { for(int j = 0; j < col + 2; ++j) { temp[0][j] = 1; temp[row + 1][j] = 1; temp[i][0] = temp[i][col + 1] = 1; } } // 將原始迷宮複製到新的迷宮中 for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp[i + 1][j + 1] = maze[i][j]; } } // 從左上角開始按照順時針開始查詢 int i = 1; int j = 1; p[i][j] = true; stack.push(new Position(i, j)); while (!stack.empty() && (!(i == (row) && (j == col)))) { if ((temp[i][j + 1] == 0) && (p[i][j + 1] == false)) { p[i][j + 1] = true; stack.push(new Position(i, j + 1)); j++; } else if ((temp[i + 1][j] == 0) && (p[i + 1][j] == false)) { p[i + 1][j] = true; stack.push(new Position(i + 1, j)); i++; } else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) { p[i][j - 1] = true; stack.push(new Position(i, j - 1)); j--; } else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) { p[i - 1][j] = true; stack.push(new Position(i - 1, j)); i--; } else { stack.pop(); if(stack.empty()) { break; } i = stack.peek().row; j = stack.peek().col; } } Stack<Position> newPos = new Stack<Position>(); if (stack.empty()) { System.out.println("沒有路徑"); } else { System.out.println("有路徑"); System.out.println("路徑如下："); while (!stack.empty()) { Position pos = new Position(); pos = stack.pop(); newPos.push(pos); } } /* * 圖形化輸出路徑 * */ String resault[][]=new String[row+1][col+1]; for(int k=0; k<row; ++k) { for(int t=0; t<col; ++t) { resault[k][t]=(maze[k][t])+""; } } while (!newPos.empty()) { Position p1=newPos.pop(); resault[p1.row-1][p1.col-1]="#"; } for(int k=0; k<row; ++k) { for(int t=0; t<col; ++t) { System.out.print(resault[k][t]+"t"); } System.out.println(); } } } /*主類*/ class Sy4 { public static void main(String[] args) { Maze demo = new Maze(); demo.init(); demo.findPath(); } }程序運行結果：
嘿嘿，上面的那種用棧來實現遞歸的方法是不是看完了呢！把它放在第一個就是為了讓大家以為沒有遞歸回溯的答案，好認認真真的看完。。。（別打我）
貼心的我當然準備了用遞歸回溯方法的代碼：
// 迷宮 class Sy4 { public static void main(String[] args) { Demo demo = new Demo(); demo.init(); demo.find(0, 0); } } class Demo { int m, n; // 類在實例化時分配空間，但是只是邏輯上連續的空間，而不一定是物理上，畢竟有靜態變量，不可能完全連續。 String[][] maze; //不能用char，掃描器Scanner不能掃描。 //這裡只是聲明，後面輸入m、n時才能確定分配空間的大小 //初始化迷宮 public void init() { Scanner scanner = new Scanner(System.in); System.out.println("請輸入迷宮的行數"); m = scanner.nextInt(); System.out.println("請輸入迷宮的列數"); n = scanner.nextInt(); maze = new String[m][n]; System.out.println("請輸入" + m + "行" + n + "列的迷宮"); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { maze[i][j] = scanner.next(); } } System.out.println("--------------------------------------------------------"); System.out.println("迷宮如下："); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { System.out.print(maze[i][j] + " "); } System.out.println(); } System.out.println("--------------------------------------------------------"); } //走到(x, y)點，找找路徑 public void find(int x, int y) { if (x < 0 || y < 0 || x >= m || y >= n || !maze[x][y].equals("0")) { // 注意字符串要用equals return; } maze[x][y] = "#"; // 走到此節點 if (x == m - 1 && y == n - 1) { for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { System.out.print(maze[i][j] + " "); } System.out.println(); } System.out.println("--------------------------------------------------------"); } find(x + 1, y); //下移 find(x - 1, y); //上移 find(x, y + 1); //右移 find(x, y - 1); //左移 maze[x][y] = "0"; } }程序運行結果：
-------------------------------------------------------- 迷宮如下： 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 -------------------------------------------------------- # 0 1 0 0 0 1 0 # 0 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 # # 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # 0 1 0 0 0 1 0 # 0 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 0 0 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # 0 1 0 0 0 1 0 # # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 # # 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # 0 1 0 0 0 1 0 # # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 0 0 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # # 1 0 0 0 1 0 0 # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 # # 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # # 1 0 0 0 1 0 0 # 1 0 0 0 1 0 # # 1 0 1 1 0 1 # 1 1 1 0 0 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # # 1 0 0 0 1 0 # # 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 # # 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # -------------------------------------------------------- # # 1 0 0 0 1 0 # # 1 0 0 0 1 0 # 0 1 0 1 1 0 1 # 1 1 1 0 0 1 0 # # # 1 # # # 0 0 1 # # # 1 # 1 0 1 1 1 1 0 # 1 1 1 0 0 0 1 # 1 1 1 0 0 0 0 # # --------------------------------------------------------馬走日
假設國際象棋棋盤有 5*5 共 25 個格子。
設計一個程序，使棋子從初始位置（棋盤編號為 1 的位）開始跳馬，能夠把棋盤的格子全部都走一遍，每個格子只允許走一次。
- 輸出一個如圖 2 的解，左上角為第一步起點。
- 總共有多少解。
PS：國際象棋的棋子是在格子中間的。國際象棋中的「馬走日」，如下圖所示，第一步為[1,1],
第二步為[2,8]或[2,12]，第三步可以是[3,5]或[3,21]等，以此類推。
答案：
- 明確函數功能：jump(m, n)為跳到(m, n)位置。
- 尋找遞歸出口：不在邊界之內 或 已走過。
-
明確所有路徑：8個方位，
技巧：這裡可以用一個數組存入八個方位的變化，再用循環依次取出，比寫八個方位要聰明許多。
-
回溯還原現場：
path–; // 回溯法關鍵步驟
a[m][n] = 0;
//馬走日 class Sy2 { private static int[][] next = { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 } }; // 馬的跳躍路徑（技巧） private static int[][] map; // 地圖 private static int m, n; private static int count = 0;// 統計有多少種走法 private static int step = 0; public static void main(String[] args) { m = 5; n = 5; int x = 0; int y = 0; map = new int[m][n]; jump(x, y); System.out.println("---------"); System.out.println(count); } private static void jump(int x, int y) { // 如果超出界限，那就繼續下一輪 if (x < 0 || x >= m || y < 0 || y >= n || map[x][y] != 0) { return; } // 立足此節點 step++; map[x][y] = step; if (step == m * n) { if (count == 0) // 如果是第一次，那就輸出一個 show(map); count++; } // 寫出所有路徑（技巧） int tx = 0, ty = 0; for (int i = 0; i < 8; i++) { tx = x + next[i][0]; // 技巧 ty = y + next[i][1]; jump(tx, ty); } // 還原 step--; map[x][y] = 0; } // 顯示數組 private static void show(int[][] arr) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { System.out.print(arr[i][j] + " t"); } System.out.println(); } } }程序運行結果：
八皇后
編程解決「八皇后問題」：即 在一個 8*8 的矩形格子中排放 8 個皇后。
要滿足的條件包括：任意兩個皇后不能在同一行，同一列，也不能在同一條對角線上。
要求編程給出解的個數。
答案：
算法原理：回溯法
首先，可歸納問題的條件為，8 皇后之間需滿足：
- 不在同一行上
- 不在同一列上
- 不在同一斜線上
- 不在同一反斜線上
這為我們提供一種遍歷的思路，我們可以逐行或者逐列來進行可行擺放方案的遍歷，每一行（列）遍歷出一個符合條件的位置，接着就到下一行（列）遍歷下一個棋子的合適位置，這種遍歷思路可以保證我們遍歷過程中有一個條件是絕對符合的——就是下一個棋子的擺放位置與前面的棋子不在同一行（列）。
這裡我們逐列擺放，數組下標代表列號，用數組元素存放行號。
把當前列 N 的前面的某一列設為 m,則 m 的所有取值為｛m>=0,m<N｝的集合,故又可在上面式子的基礎，歸納為如下：
從這個圖可以看出，m和N若在同一斜線上，那麼行差Am和列差AN應該相等。
所以，在點m存在的情況下，與點m列差為d的點，若行差也為±d，那麼就在一條斜線上，不合法。
- cols[N] != cols[m]（與第 m 列的棋子不在同一行）
- cols[N] != cols[m] – (N-m) （>=0 ,與第 m 列的棋子不在同一斜線上）
- cols[N] != cols[m] + (N-m) （<=8-1,與第 m 列的棋子不在同一反斜線上）
我們規定當 row[i]=true 時，表示該列第 i 行不能放棋子。
總結：
- 編寫檢測函數：正如上面的分析，每擺一個，將不合法的位置用數組標識，就不涉足了。當然，也可以寫成函數，不過沒有數組快。
- 明確函數功能：put(n)為擺第n個皇后。
- 尋找遞歸出口：當前列為最後一列；不同行、不同斜線、不同反斜線。
- 明確所有路徑：八行。
- 回溯還原現場：不需要還原，沒有破壞現場，因為檢測的時候提前用數組標識了，所以不合法的現場都沒涉足。
這樣我們就能寫成下列程序段了：
// 八皇后 class Sy6 { public static int num = 0; // 累計方案總數 public static final int MAXQUEEN = 8;// 皇后個數，同時也是棋盤行列總數 public static int[] cols = new int[MAXQUEEN]; // 定義cols數組，表示8列棋子擺放情況，數組元素存放行號 public Sy6() { // 核心函數 put(0); System.out.println(MAXQUEEN + "皇后問題有" + num + "種擺放方法。"); } public void put(int n) { // 當前列為最後一列時 if (n > MAXQUEEN - 1) { // 累計方案個數 num++; return; } // 遍歷該列所有不合法的行，並用 rows 數組記錄，不合法即 rows[i]=true boolean[] rows = new boolean[MAXQUEEN]; for (int i = 0; i < n; i++) { rows[cols[i]] = true; // 同行不合法 int d = n - i; // 列差 if (cols[i] - d >= 0) // 判斷是否超界 // 行差為-d的斜線點，不合法 rows[cols[i] - d] = true; if (cols[i] + d <= MAXQUEEN - 1)// 判斷是否超界 // 行差為d的斜線點，不合法 rows[cols[i] + d] = true; } // 所有路徑：八行都能擺 for (int i = 0; i < MAXQUEEN; i++) { // 判斷該行是否合法，如果不合法，那就繼續下一輪 if (rows[i]) continue; // 設置當前列合法棋子所在行數 cols[n] = i; // 擺放下一個 put(n + 1); } } public static void main(String args[]) { Sy6 queen = new Sy6(); } }程序運行結果：
