我正在使用回溯来解决骑士之旅的问题，但我没有得到想要的结果

Question

我尝试了knight Tour问题，尽管代码看起来只是正确的，但我仍然没有得到正确的答案，它总是返回-1，即不存在解决方案。我定义了几个函数，第一个是select，它为knight的下一步移动返回对，然后将其添加到相应的I和j值中。然后我有一个validate函数，它检查下一次移动是否正确，如果不是，则for循环会进一步迭代，否则如果为true，则会发生回溯。

def select(k):
list1=[2, 1, -1, -2, -2, -1, 1, 2]
list2=[1, 2, 2, 1, -1, -2, -2, -1]
return list1[k],list2[k]    
def validate(chessBoard,i,j):
if((i>=0)and(i<8)and (j>=0)and(j<8)and(chessBoard[i][j]==0)):
return 1
return -1   

def knightTour(chessBoard,total,i,j):
if(total==64):
for x in range(0,8):
print("n")
for y in range(0,8):
print(chessBoard[i][j],end=" ")
return 1
else:
for k in range(0,8):
row,column=select(k)
i,j=row+i,column+j
if(validate(chessBoard,i,j)==1):
total=total+1
chessBoard[i][j]=total
check=knightTour(chessBoard,total,i,j)
if(check==1):
return 1
total=total-1       
chessBoard[i][j]=0
return -1           
#main function
chessBoard=[[1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]
]
total=0
i,j=0,0
knightTour(chessBoard,total,i,j)

Answer 1

您需要在for循环中使用validate的if之后重置i和j。