Python递归深度超出限制超出,并且不知道如何删除递归

Question

也许这个问题可以通过删除所有这些功能来解决,不是吗？但是,我真的不知道如何让源工作.顺便说一句,它只是模拟一匹马在一个chesstable,周围和周围,随机,试图访问每个广场一次; 我得到一个递归深度超出错误.

import random

def main():
    global tries,moves
    tries,moves=0,0
    restart()

def restart():
    global a,indexes,x,y
    a=[[0 for y in range(8)] for x in range(8)] #Costrutto chic
    indexes=[x for x in range(8)]
    #Random part
    x=random.randint(0,7)
    y=random.randint(0,7)
    a[x][y]=1
    start()

def start():
    global i,indexes,moves,tries
    i=0
    random.shuffle(indexes) #List filled with random numbers that i'll use as indexes
    while i<=7:
        if indexes[i]==0:
            move(-2,-1)
        elif indexes[i]==1:
            move(-2,1)
        elif indexes[i]==2:
            move(-1,-2)
        elif indexes[i]==3:
            move(-1,2)
        elif indexes[i]==4:
            move(1,-2)
        elif indexes[i]==5:
            move(1,2)
        elif indexes[i]==6:
            move(2,-1)
        elif indexes[i]==7:
            move(2,1)
        i+=1
    for _ in a:
        if 0 in _:
            print "Wasted moves: %d"%(moves)
            tries+=1
            moves=0
            restart()
    print "Success obtained in %d tries"%(tries)

def move(column,row):
    global x,y,a,moves
    try: b=a[x+row][y+column]
    except IndexError: return 0
    if b==0 and 0<=x+row<=7 and 0<=y+column<=7:
        x=x+row
        y=y+column
        a[x][y]=1
        moves+=1
        start()
    else: return 0

try :main()
#except: print "I couldn't handle it" <-Row added to prevent python from returning a huge amount of errors

编辑:这是修改后的版本,仍然不起作用,但至少它是一个改进:

import random

def move((column,row),x,y):
    try: cell=squares_visited[x+row][y+column]
    except IndexError: return x,y ## NONE TYPE OBJECT
    if cell==0 and 0<=x+row<=7 and 0<=y+column<=7:
        x+=row
        y+=column
        squares_visited[x][y]=1
        return x,y ## NONE TYPE OBJECT

squares_visited=[[0] * 8 for _ in range(8)]
x=random.randint(0,7)
y=random.randint(0,7)
squares_visited[x][y]=1
moves=[(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]
indexes=list(range(8))
tries=0
print "The horse starts in position %d,%d"%(x,y)

while True:
    random.shuffle(indexes)
    for _ in indexes:
        cells=move(moves[indexes[_]],x,y) ##Passing as arguments x and y looks weird
        x=cells[0]
        y=cells[1]
    #If you out this for cicle, there are no legal moves anymore(due to full completion with 1, or to lack of legit moves)
    for _ in squares_visited:
        if 0 in _:
            squares_visited=[[0] * 8 for _ in range(8)]
            tries+=1
    else:
        print "You managed to do it in %d tries."%(tries)

Answer 1

这段代码有很多问题 - 足够值得完全重复:

import random

def main():
    global tries,moves

过度使用全局变量的许多例子中的第一个.如果可能,传递参数; 或创建一个类.这是一个通用策略,可以帮助您构建更易于理解(因此更可调试)的算法; 从一般意义上讲,这是您的代码失败的部分原因 - 不是因为任何特定的错误,而是因为代码的复杂性使得很难找到错误.

    tries,moves=0,0
    restart()

def restart():
    global a,indexes,x,y

你为什么要命名你的电路板a？这是一个可怕的名字!使用描述性的东西squares_visited.

    a=[[0 for y in range(8)] for x in range(8)] #Costrutto chic
    indexes=[x for x in range(8)]

Minor:在python 2中,[x for x in range(8)] == range(8)- 它们完全相同,所以列表理解是不必要的.在3中,它的工作方式略有不同,但如果你想要一个列表(而不是一个range对象),只需将其传递给list(list(range(8))).

    #Random part
    x=random.randint(0,7)
    y=random.randint(0,7)
    a[x][y]=1
    start()

所以到目前为止我对代码的理解a是板子,x它y是起始坐标,你已经标记了第一个访问过的点1.到现在为止还挺好.但事情开始变得毛茸茸,因为你start最后restart调用而不是从顶级控制函数调用它.这在理论上是可以的,但它使递归比必要的更复杂; 这是你问题的另一部分.

def start():
    global i,indexes,moves,tries

更多全局...

    i=0
    random.shuffle(indexes) #List filled with random numbers that i'll use as indexes
    while i<=7:
        if indexes[i]==0:
            move(-2,-1)
        elif indexes[i]==1:
            move(-2,1)
        elif indexes[i]==2:
            move(-1,-2)
        elif indexes[i]==3:
            move(-1,2)
        elif indexes[i]==4:
            move(1,-2)
        elif indexes[i]==5:
            move(1,2)
        elif indexes[i]==6:
            move(2,-1)
        elif indexes[i]==7:
            move(2,1)
        i+=1

好的,所以你要做的就是indexes按顺序遍历每个索引.你为什么用while？为什么i全球？我不认为它在其他任何地方使用过.这样做过于复杂.只需使用for循环indexes直接迭代,如

    for index in indexes: 
        if index==0:
            ...

好的,现在针对具体问题......

    for _ in a:
        if 0 in _:
            print "Wasted moves: %d"%(moves)
            tries+=1
            moves=0
            restart()
    print "Success obtained in %d tries"%(tries)

我不明白你在这里要做什么.看起来你restart每次0在电路板上找到一个(即一个未访问的地点)时都会打电话.但是将restart所有电路板值重置为0,所以除非1在达到此点之前还有其他方法用s 填充电路板,否则将导致无限递归.事实上,之间的相互递归move,并start 可能能够实现,在原则上,但因为它是,它的方式太复杂了!问题是没有明确的递归终止条件.

def move(column,row):
    global x,y,a,moves
    try: b=a[x+row][y+column]
    except IndexError: return 0
    if b==0 and 0<=x+row<=7 and 0<=y+column<=7:
        x=x+row
        y=y+column
        a[x][y]=1
        moves+=1
        start()
    else: return 0

原则上,这个想法似乎是,如果你的移动击中1或离开了板,那么递归的当前分支终止.但是因为i并且indexes在全球范围之内start,当start被重新调用时,它会重新洗牌indexes并重置i为0!结果是纯粹的混乱!我甚至无法理解这将如何影响递归; 似乎因为每次i开始都会重置start,并且因为每次成功调用都会move导致调用start,while启动循环将永远不会终止!

我想最终这个过程可能会设法访问每个方块,此时事情可能会按预期工作,但事实上,即使预测也是如此.

try :main()
#except: print "I couldn't handle it" <-Row added to prevent python from returning a huge amount of errors

不确定你最后一行是什么意思,但这听起来不是一个好兆头 - 你是在写错误而不是找到根本原因.

我将稍微使用这个代码,看看我是否可以通过对其某些状态进行去全球化来使其表现得更好......将很快报告.

更新:

好的,我indexes如上所述去全球化了.然后我用一个无限循环替换了start/ restartrecursion,一个调用过去restart的return语句,以及一个结束时的语句(在成功时突破无限循环).结果表现得更像预期.这仍然是糟糕的设计,但它现在有效,因为它递归地尝试了一堆随机路径,直到每个本地位置都被访问过.startrestartsys.exit()start

当然它仍然没有成功; 它只是保持循环.实际上找到一个解决方案可能需要更多地重新思考这个算法!但遵循我的上述建议至少应该有所帮助.