Pythonで迷路を解決する

Question

私はpythonで迷路のソルバーを作るのに疲れを感じませんでした。私は友達、インターネット、スタックなどのすべてのリソースを使いました。私は前に私のコードをスタック質問から多くのものに適応させましたが、完全にコードをコピーするとき（私はやりたくない）でも答えには出られません。

迷路/入力ファイル（ネストされたリスト）：

[['*', '*', '*', '*', '*'], 
    ['*', ' ', '*', ' ', '*'], 
    ['*', ' ', ' ', ' ', '*'], 
    ['*', ' ', '*', ' ', 'E'], 
    ['*', 'S', '*', '*', '*']] 

この関数は、迷路内の同じポイントをループし続けます。私の開始点「S」を出力し、（4,1）である：

(4,1) 
(4,0) 
(3,1) 

上記の出力は、私が機能をデバッグするために使用print文からです。

already_visited=[] 
def solve(x,y): 
    global already_visited 
    matrix = draw(load()) 
    print (x,y) 

    #base cases 
    if matrix[x][y] == "E": 
     for row in matrix: 
      row = str(row)[1:-1] 
      print row 
     return True 
    if matrix[x][y] == "*": 
     return False 
    if matrix[x][y] == "x": 
     return False 

    matrix[x][y] = "x" 

    #--------------------- 
    if (x,y) in already_visited: #check if we have already been here 
     return False 

    already_visited.append((x,y)) #add position to list 
    #--------------------- 


    # recursive cases (matrix traversal) 
    if (x < len(matrix)-1 and solve1(x+1,y)): 
     return True 
    elif (y > 0 and solve1(x,y-1)): 
     return True 
    elif (x > 0 and solve1(x-1,y)): 
     return True 
    elif (y < len(matrix)-1 and solve1(x,y+1)): 
     return True 
    else: 
     return False 

迷路に見られるように、私はxとyのための機能に入るのですすべては、S、インデックスを開始している：それは私の機能を解決するための再帰的limit.Belowがさ当たるまで、それはちょうどそのために、上記を印刷します上記の投稿。どんな助けもありがとうございます！

Answer 1

交換します正しい制約チェックを使用して関数を開始すると、IndexErrorに実行されなくても機能します。まず、xが行列の行数の範囲内にあることを確認する必要があります。次に列の数を確認する必要があります。ここではlen()の値が最初の範囲外です。

さらに、ソルバーのすべての呼び出しで行列を再ロードします。永続的な変更を行うには、1つのマトリックスでのみ操作する必要があります。それは、関数の引数として追加するために：

def solve2(matrix,x,y): 
    print (x,y) 
    if x >= len(matrix) or y >= len(matrix[x]): 
     return False 
    [...] 

を次に最初の実行にsolve2(draw(load()),4,1)のようにそれを呼び出すとsolve2(matrix,x,y-1))の当量を持つすべての再帰呼び出しを交換してください。 solve1()についても同様です。

Answer 2

ここでこのコードは動作しません。

if (x < len(matrix)-1 and solve1(x+1,y)): 
     return True 
    elif (y > 0 and solve1(x,y-1)): 
     return True 
    elif (x > 0 and solve1(x-1,y)): 
     return True 
    elif (y < len(matrix)-1 and solve1(x,y+1)): 
     return True 
    else: 
     return False 

問題は再帰です。 、あなたは再帰的にそれを行うので

をダウンしようとしていない場合は

を残して開始されない場合

をアップしようとしていない場合は

右に行くことができた場合

1. あなた：どのようなプログラムがないことですプログラムは壁に当たるまで右に行くでしょう。

   壁に当たるまで上がってください。

   次に、

   がダウンしています。

   これにより、円での実行が非常に簡単になります。

   だから、あなたは私の知る限り見ることができるように2つの簡単な可能性を持っている：あなたは場所を訪問し、あなたはすでにランダム

ここ
2. 実行されている場合は、常に再帰にFalseを返した場合は
   1. は覚えておいてください

   ナンバー1は次のようになります。

   already_visited=[] 
   def solve1(x,y): 
       global already_visited 
       matrix = draw(load()) 
       print (x,y) 
   
       #base cases 
       if matrix[x][y] == "E": 
        for row in matrix: 
         row = str(row)[1:-1] 
         print row 
        return True 
       if matrix[x][y] == "*": 
        return False 
       if matrix[x][y] == "x": 
        return False 
   
       matrix[x][y] = "x" 
   
       #--------------------- 
       if (x,y) in already_visited: #check if we have already been here 
        return False 
   
       already_visited.append((x,y)) #add position to list 
       #--------------------- 
   
   
       # recursive cases (matrix traversal) 
       if (x < len(matrix)-1 and solve1(x+1,y)): 
        return True 
       elif (y > 0 and solve1(x,y-1)): 
        return True 
       elif (x > 0 and solve1(x-1,y)): 
        return True 
       elif (y < len(matrix)-1 and solve1(x,y+1)): 
        return True 
       else: 
        return False 
   

Answer 3

迷路を作るのは簡単です。あなたは最初にグリッドを作る。

import networkx as nx 
import numpy as np 

G = nx.Graph() 
for i in range(5): 
    for j in range(5): 
     G.add_node((i,j)) 
     if i >0: 
      G.add_edge((i-1,j),(i,j)) 
     if j>0: 
      G.add_edge((i,j),(i,j-1)) 

次に、パスノードを離れる壁を削除します。

a = np.array([['*', '*', '*', '*', '*'], 
     ['*', ' ', '*', ' ', '*'], 
     ['*', ' ', ' ', ' ', '*'], 
     ['*', ' ', '*', ' ', 'E'], 
     ['*', 'S', '*', '*', '*']]) 

for i in range(5): 
    for j in range(5): 
     if a[i][j]=='*': 
      G.remove_node((i,j)) 

私は不正行為をしており、開始位置と終了位置を入れています。しかし、その後、NetworkXは最初から最後までのパスを見つけます。

for point in nx.algorithms.astar_path(G,(4,1),(3,4)): 
    print(point)