Breadth-first search algorithm running an infinite loop in Python

Question

I am trying to create a maze with the breadth-first search algorithm in python. However, my program is going into an infinite loop. It should check each space, up, down, left, and to the right of it. Then, that space gets put in the visited list. After the algorithm checks every space and puts them into the visited list, it should backtrack to find the shortest route to the start. It should put 1's in the shortest route when it backtracks.

import queue
import re

def maze_3():
    maze3 = [
        '00000S000000000000000000000000000000000000000000000000000000000',
        '00000  000000000                                               ',
        '00000  000000000  000000000000000000  000000000000000  00000000',
        '000000            00000000    000000                      00000',
        '   00000000  000000000000         000000000000000000     000000',
        '00000000         000000000000000000000000000000   0000   000000',
        '000000        000      000000000      000     000000       0000',
        '000000  000     000000000        00000000    000000          00',
        '00  000    0  0000000000  000  000   0000  00  00 00000     000',
        '000000    000000         000000000     000  0000          00000',
        '0000000000000000            0000000  0000000   000  00000000000',
        '000000        000  0000000    0000   00000000000000    00000000',
        '0000000000000000E                                       0000000',
    ]
    return maze3


def finished_maze(maze, solution=''):
    global starting_point
    starting_point = 0
    for position in range(len(maze[0])):
        if position == 'S':
            starting_point = maze[i]
            break

    j = starting_point
    k = 0
    position = set()

    for move in solution:
        if move == 'Up':
            k -= 1
            print(move)
        elif move == 'Down':
            k += 1
            print(move)
        elif move == 'Left':
            j -= 1
            print(move)
        elif move == 'Right':
            j += 1
            print(move)

    for row in range(len(maze)):
        for column in range(len(maze[0])):
            if (maze[row], maze[column]) in position:
                print('1 ', end='')
            else:
                print(column + '', end='')
        print()


def is_valid(maze, moves):
    global starting_point
    a = True
    for position in range(len(maze[0])):
        if position == 'S':
            starting_point = maze[position]

    j = starting_point
    k = 0

    for move in re.findall('[A-Z][a-z]*', moves):
        if move == 'Up':
            k -= 1
        elif move == 'Down':
            k += 1
        elif move == 'Left':
            j -= 1
        elif move == 'Right':
            j += 1

        if not ((j >= 0 and j < len(maze[0])) and (k >= 0 and k < len(maze[0]))):
            return not a
        elif maze[k][j] == '0':
            return not a
    return a


def find_solution(maze, moves):
    global starting_point
    starting_point = 0
    global visited
    visited = []
    global move
    move = 0
    a = True

    for position in range(len(maze[0])):
        if position == 'S':
            starting_point = maze[position]

    j = starting_point
    k = 0
    if moves in visited:
        return not a
    for move in re.findall('[A-Z][a-z]*', moves):
        if move == 'Up':
            k -= 1
        elif move == 'Down':
            k += 1
        elif move == 'Left':
            j -= 1
        elif move == 'Right':
            j += 1

        if maze[k][j] == 'E':
            print(moves)
            print(finished_maze(maze, moves))
            return a
    visited.append(move)
    return not a


space = queue.Queue()
space.put('')
put = ''
maze = maze_3()


while not find_solution(maze, put):
    put = space.get()
    for i in ['Up', 'Down', 'Left', 'Right']:
        piece = put + i
        if is_valid(maze, piece):
            space.put(piece)

Answer 1

等待大神答复