python - 在 Python 中使用递归回溯解决 TweetMazes

问题描述

我一直在自学 Python 作为第一步，看看我是否想将职业从教学完全转变为某种软件开发。到目前为止，一切进展顺利，我一直在做一些小项目来真正扩展我的能力。我最近和我的学生做了一些 TweetMazes，并意识到制作一个 Python 程序来解决这些迷宫对我来说是一个很好的挑衅。TweetMaze 是一维数字跳跃迷宫。他们在这里得到了很好的描述。几乎立即我意识到人们解决这些迷宫的方法是在他们的大脑中实现递归回溯，所以我决定制作一个递归回溯算法来解决这些问题。我发现递归很有趣，也很难理解。在花了大约一周的时间处理代码之后，

首先，一个 TweetMaze 的例子。这是我编写的一个简短的代码，用作我的代码的测试用例。这是一个包含 6 个数字的列表：

[4, 2, 2, 2, 3, 0]

你从索引 0 开始，它的值为 4。你试图到达列表中的最后一个元素，这是唯一一个值为 0 的元素。列表中每个元素的值告诉你有多少您可以向左或向右跳跃的空间。所以你会像这样解决迷宫：

1. starting at index 0, there's a value of 4: I can't move left, so I have to jump 4 spaces right to index 4.
2. Index 4 has a value of 3. I can't jump right, that's outside the puzzle, so I have to go left 3 spaces to index 1.
3. Again, I can only go right, so I move 2 spaces right to index 3.
4. Index 3 has a value of 2, and I can jump left or right. Pretty obviously, I jump right 2 spaces to index 5, 
   solving the puzzle. If I had instead gone left, I would have entered a loop.

我可能将此解决方案表示为另一个列表，指示解决方案中采用的索引位置。所以对于上面的谜题，我在我的 python 程序中调用的解决方案堆栈将是：

Solution = [0, 4, 1, 3, 5]

我还制作了一个函数，将解决方案显示为迷宫下方的一系列“#”符号，以显示所采取的步骤。上面的迷宫应该是这样的：

    [4, 2, 2, 2, 3, 0]
     #
                 #
        #
              #
                    #

所以这就是事情变得奇怪的地方。如果我通过我的代码运行示例迷宫，一切正常，我得到预期的输出。然而，这是一个非常短的迷宫并且很容易解决，所以为了进一步测试我的代码，我制作了包含 7 个元素而不是 6 个元素的新迷宫。我运行了下面的迷宫，代码终止并且表现得好像它有一个解决方案，但它完全不是一个有效的解决方案：

    Maze: [3, 5, 3, 1, 4, 4, 0]        Solution: [0, 3, 4, 2, 5, 1, 6]
           #
                    #
                       #
                 #
                          #
              #
                             #

我希望到目前为止一切都清楚。该算法很早就出错了。

1. It starts at index 0, and moves right by 3 to index 3. That's correct.
2. It moves right by 1 to index 4. That's a valid move, but that's not how the solution should go. As 
   far as I can tell, there's only one solution, and it moves left by 1 to index 2 at this point. 
   However, the move the program made is at least valid still, so I'll move on to its next step.
3. It's at index 4, which as a value of 4. That means it should move left or right by 4, but it doesn't. 
   It moves left by 2 to index 2. It's totally broken down at this point, and has made an invalid move 
   of the wrong step size. I'm absolutely baffled as to how it does this at all. 
   I just don't see in my code how it could move with the wrong step size.
4. From this point, however, it's weirdly back on track and finishes the rest of the maze, 
   making moves of the correct step size to get to the end. It's like it just inserted a wrong step
   and then carried on from the correct point. So basically, what on Earth is happening?

为清楚起见，解决方案应如下所示：

    Maze: [3, 5, 3, 1, 4, 4, 0]        Solution: [0, 3, 2, 5, 1, 6]
           #
                    #
                 #
                          #
              #
                             #

在这一点上事情变得更加奇怪，因为我决定添加一个解决方案步骤列表，它将以文本格式输出算法在每一层递归中所做的事情，这样我就可以尝试看看它在做什么，而这些解决方案步骤实际上是正确的！它们与解决方案列表的输出或“#”解决方案显示不匹配！我将复制并粘贴输出：

    Current position: 0. Stepping right by 3 to index 3.
    Current position: 3. Stepping left by 1 to index 2.
    Current position: 2. Stepping right by 3 to index 5.
    Current position: 5. Stepping left by 4 to index 1.
    Current position: 1. Stepping right by 5 to index 6.

    Solution stack shows these positions: [0, 3, 4, 2, 5, 1, 6]

    [3, 5, 3, 1, 4, 4, 0]
     #
              #
                 #
           #
                    #
        #
                       #

如果您按照写出的步骤进行操作，那么这是正确的解决方案！但是解决方案堆栈和#显示都不正确，显示了奇怪的额外步骤和错误的移动。这不是发生这种情况的唯一谜题，因为我已经在其他包含 7 个元素或更长的谜题中对其进行了测试。我花了大约一周的时间通过递归回溯将我的方式调整为某种可行的方法，最终我无法判断到底发生了什么，所以我希望有人能解释这种奇怪的行为。坦率地说，我为它取得的进展感到非常自豪，因为我一直遇到超过最大递归深度的奇怪问题，并设法克服了这些问题。不过，我想让这个功能完全正常，并理解它为什么会出错。更何况，我喜欢了解您如何准确找出问题所在。我对调试工具和方法仍然很陌生，而且我在理解如何通过递归迭代遵循程序流程时遇到了一些麻烦。我已经在 GitHub 上发布了我的代码，但是因为我对使用 Github 还是很陌生，所以我也会在下面发布我的代码。太感谢了！

maze_string = '3531440'

'''Copy and paste maze strings into the above to change which maze is being run.
Other maze strings to play with:
422230
313210
313110
7347737258493420
'''

maze = [int(i) for i in maze_string]

solution = [0]  #this is the solution stack. append to put on new steps, 
    #pop() to backtrack.
    #algorithm doesn't work if I don't initialize the solution list with the 0 position. Hits max recursion depth.

solution_steps = []

def valid(position, direction):
    #pass in the current position, desired direction of move
    global maze
    if direction == 'right':
        return True if position + maze[position] < len(maze) else False
    elif direction == 'left':
        return True if position - maze[position] >= 0 else False
    
def solve(position):
    global solution
    global maze
    
    #if maze is solved, return True
    if maze[position] == 0:
        return True
    
    #try branches  
    if valid(position, 'right') and (position + maze[position] not in solution):
        new = position + maze[position]
        solution.append(new)
        if solve(new):
            solution_steps.append(f'Current position: {position}. Stepping right by {maze[position]} to index {new}.')
            return True
        solution.pop()
        
    if valid(position, 'left') and (position - maze[position] not in solution):
        new = position - maze[position]
        solution.append(new)
        if solve(new):
            solution_steps.append(f'Current position: {position}. Stepping left by {maze[position]} to index {new}.')
            return True
        solution.pop()
    
    solution.append('no solution')
    return False

def display_solution():
    global maze
    global solution
    print(maze)
    for i in solution:
        point = ' ' + 3*i*' ' + '#'
        print(point)
        
if __name__ == "__main__":
    
    solve(0)
    
    if solution != 'no solution':
        for step in reversed(solution_steps):
            print(step)
        print(f'\nSolution stack shows these positions: {solution}\n')   
        display_solution()
    else:
        print(solution)

标签： pythonrecursionrecursive-backtracking

python - 在 Python 中使用递归回溯解决 TweetMazes - 调试帮助请求

问题描述

解决方案

推荐阅读