檢查完美迷宮的輸入驗證

Question

我正在開發一個建立完美迷宮的項目。 我有一個迷宮類和一個類代表迷宮中的每個方格。在我的Cell類中，我有四個布爾變量（北，南，東，西）來表示單元格的北部還是南部有一堵牆。還有一個名爲visit的布爾變量來檢查單元是否被訪問過。這裏是我的代碼，用於Cell類的init（）。

def __init__(self): 
    self.north = True 
    self.south = True 
    self.east = True 
    self.west = True 
    self.visit = False 

而對於迷宮類，我有self.maze（一堆細胞）和self.size = N（構建一個N * N的迷宮）。 下面是類迷宮的INIT（）：

def __init__(self, N): 

    self.size = N 
    self.maze = [[i for i in range(N + 2)] for i in range(N + 2)] 

    for r in range(self.size + 2): 
     for c in range(self.size + 2): 
      self.maze[r][c] = Cell() 

雖然我更新迷宮的索引，我寫了兩個函數來檢查下一頁末和newY是否在範圍爲1 < = X < = self.size和1 < = y < = self.size，以及是否已訪問該單元格。 下面是代碼：

def in_range(self, x, y): 

    if 1 <= x <= self.size and 1 <= y <= self.size: 
     return True 
    else: 
     return False 

def is_valid(self, x, y): 

    if not self.maze[x][y].getVisit() and self.in_range(x,y): 
     return True 
    else: 
     return False 

這一切後，我寫的主要結構：

def walk(self, s, x, y): 

    neighbor = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] 


    if s.size() == self.size**2: return 

    else: 

     while True: 
      new = choice(neighbor)#choice() is import from random 
      #print(self.is_valid(new[0], new[1])) 
      if self.is_valid(new[0], new[1]):break 
      else: 
       if len(neighbor) != 0: 
        neighbor.remove(new) 
        new = choice(neighbor) 
       else: 
        temp = s.pop(s) 
        self.walk(s, temp[0], temp[1]) 

       break 
    print(new) 

但是，運行我的代碼劇照給我的指標是不是1和self.size之間。我無法弄清楚爲什麼，我認爲我的檢查算法工作正常。 這是我得到的：

>>> ================================ RESTART 

================================ 
>>> 
>>> a = Maze(5) 
>>> a.search() 
1 2 
(1, 3) 
(2, 3) 
(2, 4) 
(1, 4) 
(2, 4) 
(2, 5) 
(3, 5) 
(4, 5) 
(4, 4) 
(4, 3) 
(3, 3) 
(3, 2) 
(2, 2) 
(2, 1) 
(1, 1) 
(0, 1) 
(-1, 1) 
(0, 1) 
(1, 1) 
(0, 1) 
(-1, 1) 
(-1, 2) 
(-1, 1) 
(0, 1) 

有人可以幫我嗎？ PLZ，真的很感激！

Answer 1

在Python中range從0開始，如果你沒有指定另一個開始位置。因此，當你初始化你的迷宮，你有細胞(0, *)和(*, 0)：

for r in range(self.size + 2): 
    for c in range(self.size + 2): 
     self.maze[r][c] = Cell() 

當你計算你的鄰居，你不檢查，你不出去：

neighbor = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] 

而且它的只有在分配了new到這樣的座標之後，您才能檢查它是否有效。但是，如果它是而不是有效，並且沒有鄰居，則再次調用walk。您應該嘗試獨立於visit檢查in_range。

此外，您的循環只能運行一次，因爲任何一個new都是有效的，並且您打破了循環，或者它無效並且您跳出循環。

最後，你忘了給我們search功能，什麼s是（和s.pop(s)看起來很滑稽作爲一般的pop參數是一個索引，而不是再次的序列）。

Answer 2

您可以通過仔細查看walk()或使用print語句來追蹤事物來發現。 在網格的末端出現錯誤（當x或y == 0或N-1時）。除非你允許環繞，否則我假設你的網格初始化會在網格的北部（y == 0），南部，東部和西部放置牆。 順便說一句，你的網格有兩個不必要的行和列：如果你想要N個單元，編號爲O ..（N-1），那麼使用range(N)而不是range(N+2)，否則使用range(1,N+1)。 （你用不正確的== False填充任何不需要的單元嗎？）

無論如何，walk()首先挑選一個隨機的鄰居單元，如果它是一個有效的單元，則跳出while循環。但如果不是，它會高興地選擇任何剩餘的鄰居單元（無論是否有效）和士兵。這是你的錯誤。總是測試有效性。 如果它已經用完了有效的鄰居單元，則通過執行s.pop(s)回溯。 s.pop(s)也看起來像一個錯誤。爲什麼不是s.pop()？ 順便說一下，調用變量path而不是s。

此外，這只是檢查coords的有效性;你從來沒有真正檢查過你是否曾經訪問過這個單元，所以你的遞歸回溯沒有結束的條件;你可以很容易地進入循環。

你可以幫助自己很多，如果你重構walk()到使用單獨的發電機get_random_valid_neighbor()返回已經測試爲有效隨機選擇的鄰居（當你用完的鄰居None）。

def walk(self, s, x, y): 

... 
     while True: 
      new = choice(neighbor) 
      if self.is_valid(new[0], new[1]):break # tested for validity 
      else: 
       if len(neighbor) != 0: 
        neighbor.remove(new) 
        new = choice(neighbor) # BUG: never tested for validity 
       ...