Решение TweetMazes с рекурсивным возвратом в Python — запрос на помощь по отладке

Я изучаю Python в качестве первого шага к тому, чтобы понять, хочу ли я полностью сменить профессию преподавателя на какую-то разработку программного обеспечения. Пока все идет хорошо, и я работаю над небольшими проектами, чтобы действительно расширить свои возможности. Недавно я провел несколько TweetMaze со своими учениками и понял, что создание программы на Python для решения этих лабиринтов было бы для меня отличной провокацией. TweetMazes — это одномерные лабиринты с перескакиванием чисел. Здесь они хорошо описаны. Почти сразу же я понял, что способ, которым люди решают эти лабиринты, заключается в реализации рекурсивного поиска с возвратом в их мозгу, поэтому я решил создать алгоритм рекурсивного поиска с возвратом для их решения. Я нахожу рекурсию увлекательной, а также очень трудной для понимания. Примерно через неделю возни с кодом я получил что-то, что одновременно работает и не работает, с чем я не могу совладать, поэтому я надеюсь, что кто-нибудь поможет мне понять, что происходит.

Во-первых, пример 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)