Бесконечный цикл и рекурсия в Python

Я работаю над реализацией итеративного поиска с углублением в глубину, чтобы найти решения для проблемы-головоломки 8 . Я не заинтересован в поиске самих фактических путей поиска, а просто в том, чтобы определить, сколько времени требуется для запуска программы. (Я еще не реализовал функцию синхронизации).

Тем не менее, у меня возникли некоторые проблемы при попытке реализовать настоящую функцию поиска (прокрутите вниз, чтобы увидеть). Я вставил весь код, который у меня был до сих пор, поэтому, если вы скопируете и вставите его, вы также сможете его запустить. Это может быть лучший способ описать проблемы, с которыми я сталкиваюсь... Я просто не понимаю, почему я получаю бесконечные циклы во время рекурсии, например. в тесте для головоломки 2 (p2), где первое расширение должно дать решение. Я подумал, что это может быть как-то связано с тем, что не добавлено «Возврат» перед одной из строк кода (это прокомментировано ниже). Когда я добавляю возврат, я могу пройти тест для головоломки 2, но что-то более сложное, например головоломка 3, терпит неудачу, поскольку кажется, что теперь код расширяет только самую левую ветвь...

Был в этом в течение нескольких часов, и отказ от надежды. Я был бы очень признателен за еще один взгляд на это, и если бы вы могли указать на мои ошибки. Благодарю вас!

#Classic 8 puzzle game
#Data Structure: [0,1,2,3,4,5,6,7,8], which is the goal state. 0 represents the blank
#We also want to ignore "backward" moves (reversing the previous action)

p1 = [0,1,2,3,4,5,6,7,8]
p2 = [3,1,2,0,4,5,6,7,8]
p3 = [3,1,2,4,5,8,6,0,7]

def z(p):   #returns the location of the blank cell, which is represented by 0
    return p.index(0)

def left(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc-1]
    p[zeroLoc-1] = 0
    return p

def up(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc-3]
    p[zeroLoc-3] = 0
    return p

def right(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc+1]
    p[zeroLoc+1] = 0
    return p

def down(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc+3]
    p[zeroLoc+3] = 0
    return p

def expand1(p):   #version 1, which generates all successors at once by copying parent
    x = z(p)
    #p[:] will make a copy of parent puzzle
    s = []  #set s of successors

    if x == 0:
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 1:
        s.append(left(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 2:
        s.append(left(p[:]))
        s.append(down(p[:]))
    elif x == 3:
        s.append(up(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 4:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 5:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(down(p[:]))   
    elif x == 6:
        s.append(up(p[:]))
        s.append(right(p[:]))
    elif x == 7:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(right(p[:]))
    else:   #x == 8
        s.append(left(p[:]))
        s.append(up(p[:]))

    #returns set of all possible successors
    return s

goal = [0,1,2,3,4,5,6,7,8]

def DFS(root, goal):    #iterative deepening DFS
    limit = 0
    while True:
        result = DLS(root, goal, limit)
        if result == goal:
            return result
        limit = limit + 1

visited = []

def DLS(node, goal, limit):    #limited DFS
    if limit == 0 and node == goal:
        print "hi"
        return node
    elif limit > 0:
        visited.append(node)
        children = [x for x in expand1(node) if x not in visited]
        print "\n limit =", limit, "---",children   #for testing purposes only
        for child in children:
            DLS(child, goal, limit - 1)     #if I add "return" in front of this line, p2 passes the test below, but p3 will fail (only the leftmost branch of the tree is getting expanded...)
    else:
        return "No Solution"

#Below are tests

print "\ninput: ",p1
print "output: ",DFS(p1, goal)

print "\ninput: ",p2
print "output: ",DLS(p2, goal, 1)
#print "output: ",DFS(p2, goal)

print "\ninput: ",p3
print "output: ",DLS(p3, goal, 2)
#print "output: ",DFS(p2, goal)