3

这是我在 python 中的代码，调用knightsTour(0,0,1,sol,xMove,yMove)应该返回True，但我得到False. 我无法找到这个错误。

def safe(x,y,sol):
    return x >= 0 and x < 8 and y >= 0 and y < 8 and sol[x][y] == -1

def knightsTour(x,y,move,sol,xMove, yMove):
    if move == 8*8 :
        return True
    #trying all moves from the current coordinate
    for k in range(8):
        x = x+xMove[k]
        y = y+yMove[k]

        if safe(x,y,sol):
            sol[x][y] = move
            if knightsTour(x,y,move+1,sol,xMove,yMove): #calling recursively
                return True
            else :
                sol[x][y] = -1 #backtracking
    return False


sol = [[-1 for i in range(8)]for j in range(8)]
sol[0][0] = 0
xMove = [2,1,-1,-2,-2,-1,1,2]
yMove = [1,2,2,1,-1,-2,-2,-1]
print knightsTour(0,0,1,sol,xMove,yMove)
4

1 回答 1

4

那是我花了一段时间才发现的。错误在于，即使新位置不安全或最终不能作为成功骑士之旅的起始位置，您也会在循环的每次迭代中修改x和。并指出您当前的起始位置，不应更改！yfor k in range(8)xy

你的评论

#trying all moves from the current coordinate

显示了您想要做的事情，但您实际上所做的是尝试移动，如果新位置未保存或不能作为成功骑士之旅的起始位置，请从新位置尝试另一个移动，而不是当前位置坐标（即调用函数的x和y值）。

您的代码需要一个简单的修复（注意注释）：

def knightsTour(x,y,move,sol,xMove, yMove):
    if move == 8*8 :
        return True
    #trying all moves from the current coordinate
    for k in range(8):
        new_x = x+xMove[k] # don't modify x!
        new_y = y+yMove[k] # don't modify y!

        if safe(new_x,new_y,sol): # call with candidate values
            sol[new_x][new_y] = move # mark candidate values on board
            if knightsTour(new_x,new_y,move+1,sol,xMove,yMove): # call with candidate values
                return True
            else :
                sol[new_x][new_y] = -1 # reset candidate values
    return False
于 2015-12-30T12:02:27.713 回答