用python解決迷宮問題

Question

我試圖做一個迷宮求解器，它的工作原理除了用「o」標記的路徑而不是用「>」，「<」，「v」 ，「^」取決於路徑的方向。這是代碼的部分，其中它解決了迷宮：

def solve(self,x,y): 
    maze = self.maze 

    #Base case 
    if y > len(maze) or x > len(maze[y]): 
     return False 

    if maze[y][x] == "E": 
     return True 

    if maze[y][x] != " ": 
     return False 


    #marking 
    maze[y][x] = "o"   

    #recursive case 
    if self.solve(x+1,y) == True : #right 
     return True 
    if self.solve(x,y+1) == True : #down 
     return True  
    if self.solve(x-1,y) == True : #left 
     return True  
    if self.solve(x,y-1) == True : #up 
     return True  

    #Backtracking 
    maze[y][x] = " " 
    return False  

這是一個未解決的迷宮的一個示例：

#################################### 
#S# ## ######## # #  #  # # 
# # #    # #  # # 
# # ##### ## ###### # ####### # # 
### # ## ##  # # #  #### # 
# # # ####### # ### #E# 
#################################### 

而這是使用上面的代碼相同的迷宮的解決版本：

#################################### 
#S# ## ######## # #oooooo# ooo# # 
#o#ooo# oooo  #o# ooooo#ooo# 
#ooo#o#####o##o######o# ####### #o# 
### #o##oooo##oooooo#o# #  ####o# 
# #oooo# #######ooo# ### #E# 
#################################### 

，我想要得到的結果是：

#################################### 
#S# ## ######## # #>>>>>v# ^>v# # 
#v#^>v# >>>v  #^# >>>>^#>>v# 
#>>^#v#####^##v######^# ####### #v# 
### #v##^>>^##>>>>>v#^# #  ####v# 
# #>>>^# #######>>^# ### #E# 
#################################### 

怎麼可能做到這一點？

Answer 1

#marking 
maze[y][x] = "o"   

#recursive case 
if self.solve(x+1,y) == True : #right 
    maze[y][x] = ">" 
    return True 
if self.solve(x,y+1) == True : #down 
    maze[y][x] = "v" 
    return True 
... 

從LIX例子。您需要取消註釋迷宮[y] [x] =「o」，您需要該行以防止節點被重訪

Answer 2

我會建議，而不是立即設置值爲'o'，並返回'真'你使用if ... elif來設置字符，然後返回。

@marqs指出我的原始答案會允許遞歸重新訪問一個已經被證明是錯誤的位置。因此，用'o'標記所有位置，以便它們不能被重新訪問，並且稍後循環並將所有'o'重置爲'''

請注意，我建議如果... elif，因爲四個單獨的if總是會檢查其他可能性，即使他們已經發現真正的道路已被證明是錯誤的。

# tag = ' ' Mistake on my part 
tag = 'o' # Mark so will not be revisited 
maze[y, x] = tag # Mark maze point as handled 
if self.solve(x+1,y) == True : #right 
    tag = '>' 
elif self.solve(x,y+1) == True : #down 
    tag = 'v'  
elif self.solve(x-1,y) == True : #left 
    tag = '<'  
elif self.solve(x,y-1) == True : #up 
    tag = '^' 
else: 
    # All possible paths from here are false, back up and clear this point. 
    tag = ' ' 
# Note that if none of the tests were true, tag is left as ' ' 
maze[y, x] = tag # Note C or C++ would use [x, y] 
return (tag != ' ') 

這將導致嘗試（false）路徑填滿'o'，然後在顯示爲不真實時備份爲空白。

或者，你可以在它的「o」把它和真實的路徑已被發現後，回去在整個迷宮並標有「O」

明確茨艾倫點。如果是這樣的話除去其他：和改變返回到

return (tag != 'o')