Я работаю над проблемой рыцарского тура, используя backtracking, но я не получаю желаемый результат

Question

Я пытался решить проблему Knight Tour, хотя код выглядит корректно только в том случае, если я не получаю правильный ответ, всегда возвращается -1, т. Е. Решения не существует. Я определил несколько функций, первая из которых - select, которая возвращает пару для следующего хода для рыцаря, которая затем добавляется к соответствующим значениям i и j. Затем у меня есть функция проверки, которая проверяет, является ли следующий ход правильным или нет, если не для l oop, итерирует дальше, если 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

Вам нужно сбросить i и j после if, который использует validate в вашем for l oop.