目錄
1、走迷宮與回溯算法
2、迷宮設計棧扮演的角色
3、Python實作走迷宮
棧的應用有許多，本篇博文着重将棧與回溯（Backtracking）算法結合，設計走迷宮程式。其實回溯算法也是人工智能的一環，通常又稱試錯（try and error）算法，早期設計的計算機象棋遊戲、五子棋遊戲，大都是使用回溯算法。
假設一個簡單的迷宮圖形如下圖所示：
入口：迷宮的入口，筆者上圖用綠色表示。
通道：迷宮的通道，筆者上圖用黃色表示。
牆壁：迷宮的牆壁，不可通行，筆者上圖用灰色表示。
出口：迷宮的出口，筆者上圖用藍色表示。 在走迷宮時，可以上、下、左、右行走，如下圖所示：
走迷宮時每次可以走一步，如果碰到牆壁不能穿越必須走其他方向。
第1步：假設目前位置在入口處，可以參考下圖所示：
第2步：如果依照上、下、左、右原則，應該向上走，但是往上是牆壁，是以必須往下走，然後必須将走過的路标記，此例是用淺綠色标記，是以上述右圖是在迷宮中的新位置，如下圖所示：
第3步：接下來可以發現往上是走過的路，是以隻能往下發（依據上、下、左、右原則，先不考慮左、右是牆壁），下方左圖是新的迷宮位置，如下圖所示：
第4步：接下來可以發現往上是走過的路，是以隻能往下（依據上、下、左、右原則，先不考慮左、右），下方右圖是新的迷宮位置，如下圖所示：
第5步：現在下、左、右皆是牆壁，是以回到前面走過的路，這一步就是回溯的關鍵，可參考下方左圖，在此圖中筆者将造成回溯的路另外标記，以防止再次造訪，如下圖所示：
第6步：現在上、下皆是走過的路，左邊是牆壁，是以往右走，如下圖所示：
第7步：接下來上、下是牆壁，左邊是走過的路，是以往右走，如下圖所示：
第8步：由于上方有路是以往上走，如下圖所示：
第9步：由于上方有路是以往上走，如下圖所示：
第10步：由于上、左、右皆是牆壁，是以回溯到前一個位置，如下圖所示：
第11步：由于上、下是走過的路，左邊是牆壁，是以往右走，如下圖所示：
第12步：由于上、下、右是牆壁，是以回溯到先前位置，如下圖所示：
第13步：由于左邊是牆壁，是以回溯到先前走過的位置，如下圖所示：
第14步：下方有通道，是以往下走，如下圖所示：
第15步：上方是走過的位置，左方和下方是牆壁，是以往右走，如下圖所示：
上面介紹到，在第2步使用淺綠色标記走過的路，真實程式設計可以用棧存儲走過的路。
第5步使用回溯算法，所謂的回溯就是走以前走過的路，因為是将走過的路使用棧(stack)存儲，基于後進先出原則，可以pop出前一步路徑，這也是回溯的重點。當走完第4步時，
迷宮與棧圖形如下所示：
上述迷宮位置使用程式語言的(row，column)标記，是以第5步要使用回溯時，可以從棧pop出(3，1)坐标，回到(3，1)位置，結果如下所示所示：
使用Python設計走迷宮可以使用二維的清單，0代表通道、1代表牆壁，至于起點和終點也可以用0代表。
使用上述第一部分的迷宮執行個體，其中所經過的路徑用2表示，經過會造成無路可走的路徑用3表示。程式第41行前2個參數是迷宮的入口，後2個參數是迷宮的出口，實作代碼如下所示：
# ch11_1.py
from pprint import pprint
maze = [ # 迷宮地圖
[1, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 1, 1],
[1, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 1, 1],
[1, 0, 1, 0, 0, 1],
[1, 1, 1, 1, 1, 1]
]
directions = [ # 使用清單設計走迷宮方向
lambda x, y: (x-1, y), # 往上走
lambda x, y: (x+1, y), # 往下走
lambda x, y: (x, y-1), # 往左走
lambda x, y: (x, y+1), # 往右走
]
def maze_solve(x, y, goal_x, goal_y):
''' 解迷宮程式 x, y是迷宮入口, goal_x, goal_y是迷宮出口'''
maze[x][y] = 2
stack = [] # 建立路徑棧
stack.append((x, y)) # 将路徑push入棧
print('迷宮開始')
while (len(stack) > 0):
cur = stack[-1] # 目前位置
if cur[0] == goal_x and cur[1] == goal_y:
print('抵達出口')
return True # 抵達出口傳回True
for dir in directions: # 依上, 下, 左, 右優先次序走此迷宮
next = dir(cur[0], cur[1])
if maze[next[0]][next[1]] == 0: # 如果是通道可以走
stack.append(next)
maze[next[0]][next[1]] = 2 # 用2标記走過的路
break
else: # 如果進入死路, 則回溯
maze[cur[0]][cur[1]] = 3 # 标記死路
stack.pop() # 回溯
else:
print("沒有路徑")
return False
maze_solve(1, 1, 4, 4)
pprint(maze) # 跳行顯示元素 運作效果如下所示：