使用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