检查完美迷宫的输入验证

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 
       ...