Постановка задачи: дана доска N*N, на первом блоке которой находится конь. Двигающийся по правилам шахмат конь должен посетить каждое поле ровно один раз. Выведите порядок посещения каждой ячейки на шахматной доске. Если возможных решений несколько, выведите их все.
Input :
N = 8
Output:
0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
Я попробовал рекурсивное решение с использованием возврата, но не совсем понял, в чем может быть проблема с этим фрагментом кода. Может кто-нибудь помочь. Большое спасибо!
для n=2,3,4 выдается ожидаемый пустой список.
и для n=5, он выдает следующий неожиданный результат:
[[[0, '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.']], [[0, '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.']]] ..continues
для n=8 программа продолжает работать и, похоже, не выдает выходные данные в течение длительного времени
def knight(n):
xy_movements = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(-1,2),(1,-2),(-1,-2)]
board = [["."]*n for _ in range(n)]
board[0][0]=0
current_x=0
current_y=0
result=[]
def backtrack(num):
nonlocal n,current_x,current_y
if num==(n*n)-1:
result.append(board)
return
else:
for move in xy_movements:
if current_x+move[0]=n or\
current_y+move[1]=n or\
board[current_x+move[0]][current_y+move[1]] !=".":
continue
else:
current_x+=move[0]
current_y+=move[1]
board[current_x][current_y] = num+1
backtrack(num+1)
board[current_x][current_y] = "."
current_x -= move[0]
current_y -= move[1]
backtrack(0)
return result
Подробнее здесь: https://stackoverflow.com/questions/785 ... ur-problem
