迴溯法II-迷宮問題

 解決迷宮問題，並展示了如何使用迴溯法來找出從起點到終點的可行路徑。這裡逐步解釋程式的運作方式。

程式碼逐步解釋

1. is_safe 函式：

   def is_safe(maze, row, column):
       # 檢查是否在迷宮範圍內且該位置為可通行（1）
       return 0 <= row < len(maze) and 0 <= column < len(maze[0]) and maze[row][column] == 1
   

   • 這個函式用來檢查當前的位置 (row, column) 是否可以通行。
   • 位置必須在迷宮的範圍內，且該格子必須是 1 才表示可以通行。
   • 若位置符合條件，返回 True，否則返回 False。

2. solve_maze 函式：

   def solve_maze(maze, row, column, path):
       if row == len(maze) - 1 and column == len(maze[0]) - 1:  # 到達終點
           path.append((row, column))
           print(path)
           return True
       
       if is_safe(maze, row, column):
           path.append((row, column))  # 將當前位置加入路徑
           
           # 移動到下一個位置（向下或向右）
           if solve_maze(maze, row + 1, column, path):  # 向下
               return True
           if solve_maze(maze, row, column + 1, path):  # 向右
               return True
           
           # 回溯：如果無法前進，移除當前位置
           path.pop()
       
       return False
   

   • 目標： 嘗試從起點 (0,0) 移動到終點 (n-1, m-1)。
   • 流程：
     1. 如果到達終點 (n-1, m-1)，表示找到路徑，將終點加入 path，並印出完整路徑。
     2. 使用 is_safe 檢查當前位置 (row, column) 是否可通行。
     3. 若可通行，將位置加入 path，然後嘗試向下 (row + 1) 或向右 (column + 1) 移動。
     4. 如果兩個方向都無法繼續，則從 path 中移除當前位置，這就是「回溯」的動作。
     5. 如果最終無法找到任何可行路徑，返回 False。

3. 測試迷宮 mazes：

   mazes = [
       [
           [1, 0, 0, 0, 0],
           [1, 1, 0, 1, 1],
           [0, 1, 0, 0, 0],
           [1, 1, 1, 0, 0],
           [1, 0, 1, 1, 1],
           [1, 1, 1, 0, 1]
       ],
       [
           [1, 0, 0, 0, 0],
           [1, 1, 0, 1, 1],
           [0, 0, 0, 0, 0],
           [1, 1, 1, 0, 0],
           [1, 0, 1, 1, 1],
           [1, 1, 1, 0, 1]
       ],
       [
           [1, 1, 0, 0, 0],
           [0, 1, 1, 1, 1],
           [0, 0, 1, 0, 0],
           [1, 1, 1, 1, 0],
           [1, 0, 0, 1, 0],
           [1, 1, 1, 1, 1]
       ]
   ]
   

   • mazes 是一個包含多個迷宮的列表，每個迷宮都是一個 2D 的列表。
   • 1 表示可以通行的路徑，0 表示障礙。

4. 執行每個迷宮測試：

   for maze in mazes:
       if not solve_maze(maze, 0, 0, []):
           print("No solution found")
   

   • 針對每個迷宮，嘗試從 (0, 0) 開始找到通往終點的路徑。
   • 如果無法找到路徑，印出 "No solution found"。

範例輸出說明：

1. 第一個迷宮：
   • 有通路，會印出路徑，如：

     [(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (5, 4)]
     

2. 第二個迷宮：
   • 無通路，會輸出：

     No solution found
     

3. 第三個迷宮：
   • 有通路，會印出路徑，如：

     [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4)]
     

總結：

• 回溯法： 利用逐步探索與回退機制來嘗試找到一條可行的解。
• 應用情境： 試探各種可能的路徑，一旦遇到死路，就會回到上一層，嘗試其他方向。
• 靈活性： 可以處理不同大小、不同形狀的迷宮。