使用backtracking在8x8国际象棋棋盘上执行骑士之旅

Question

这里是我在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) 

Answer 1

那一个花了我一段时间才发现。错误是你在for k in range(8)循环的每次迭代中修改了x和y，即使新位置不安全或最终不能成为成功骑士巡回演出的起始位置。 x和y表示您目前的起始位置，不应该改变！

您的评论

#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