Возврат в Python — проблема тура рыцаря
Постановка задачи: дана доска 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]<0 or current_x+move[0]>=n or\
current_y+move[1]<0 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
@LukeWoodward Готово. Отредактировал мой код и включил вывод, который я получаю.
Не работает. Попробуйте скопировать код в файл и запустить его. Также см. минимальный воспроизводимый пример. Кстати: взгляните на PEP 8, он требует отступа в четыре пробела. Соблюдение этих стандартов поможет другим быстро и правильно прочитать и понять ваш код.
Для тестирования я бы начал с шахматных досок с длиной сторон 1 (тривиально решаемая), 2, 3 (обе неразрешимые) и меньшей, большей, которая разрешима. Это облегчит понимание и отладку.
@trincot n=4, похоже, не имеет решения. n=1 имеет один; исправил это
Хорошо! И почему result список? Вы хотите найти все возможные туры?
@trincot Поскольку функция возврата работает рекурсивно, она предназначена для добавления всех тех конфигураций платы, конечный номер которых равен (n*n)-1.
функция возврата рекурсивно вызывается в блоке else как backtrack(num+1)
Но в задании это не указано. Я думаю, вас путает то, что один тур состоит из n*n позиций, а это всего лишь одна доска. Вы не должны хранить в результате n*n досок (и ваш код этого не делает), а только окончательную доску после расчета этих n*n позиций. И тогда вам следует остановиться. Задача не требует альтернативных досок.
@trincot Аа, ладно, вообще-то да! Я просто попробовал произвести все возможные результаты.
Хорошо, но тогда отредактируйте свой вопрос, так как тогда вы решаете другую задачу.
сделанный! включена строка, включающая все возможные решения
Хорошо, но теперь пример ввода/вывода не является полным (да и не может быть таковым с практической точки зрения): он просто перечисляет одно решение.
Ответы 1
Проблема в том, что result.append(board) добавит единственную имеющуюся у вас доску, в то время как ваш алгоритм возврата будет продолжать обновлять эту доску, и в самом конце алгоритм заберет все сделанные им ходы. Итак, board пуст, за исключением первого 0, который был помещен и никогда не удалялся. Это означает, что в result вы теперь ссылаетесь на почти пустую доску, хотя решения были найдены.
Решение простое: возьмите копию доски и добавьте ее в список result:
result.append([row[:] for row in board])
Это решит проблему, о которой вы упомянули при звонке knight(5). Для плат размером более 6 у вас просто возникнет слишком серьезная проблема: существует 19 591 828 170 979 904 решений для платы 8x8, поэтому не надейтесь получить ее за несколько секунд. На вашем компьютере, вероятно, не хватит памяти, чтобы собрать такое количество плат, пусть вы подождите.
Извините, у меня был вопрос. Разве результат не добавляет все те доски, конечный номер которых равен n*n-1? Не могли бы вы уточнить немного больше, пожалуйста
Да, подтверждаю. Это то же самое, что сказать, что результат добавляет все завершенные доски. Какое уточнение необходимо? Если вы не копируете доску, вы добавляете ссылку на одну и ту же доску снова и снова, так что все элементы в result на самом деле представляют собой одну и ту же доску, которую вы постоянно обновляете в ходе алгоритма.
Был бы очень признателен за дополнительные разъяснения о том, почему result.append(board) не работает должным образом. Спасибо за ответ выше!
Но это работает так, как задумано. По крайней мере так, как предусмотрено спецификацией. Просто спросите себя: сколько досок выделено в вашей программе? Ответ: 1. Добавление одной доски в список каким-то образом не создает новую доску. Это все еще та единственная плата.
Разве алгоритм возврата не редактирует доску на каждом этапе? Когда он получает 24 для n=5, он должен также отображать все остальные числа.
Представьте, что у вас есть настоящая шахматная доска, и вы физически размещаете на доске нового коня на каждой клетке (и каждый конь имеет уникальный номер). В какой-то момент вы обнаружите, что заполнили всю доску. Вы помещаете шахматную доску со всеми фигурами в коробку, думая, что «спасли» доску. Но затем вы продолжаете удалять коней с этой шахматной доски и пробуете разные расстановки, а затем убираете с нее все фигуры. Что такое шахматная доска в коробке? Он пуст. Тот факт, что вы поместили плату в коробку, не сделал для платы ничего существенного. То же самое с result.append(board)
«должно было отобразить все остальные числа»: Но в тот момент вы его не отобразили. Вы отложили показ до конца, когда уже снова убрали фигуры с этой доски.
Большое спасибо за ваши идеи. Я понимаю!
Вы упоминаете, что с этим кодом есть проблема, но не объясняете, в чем проблема. Пожалуйста, отредактируйте свой вопрос, чтобы объяснить, почему этот код не делает то, что вы от него ожидаете. Например. это вызывает исключение? Кажется, что он работает вечно и не генерирует никаких результатов? Создает ли он неправильный вывод?