Я довольно смущен идеей реализации задачи 8-ферзя с помощью динамического программирования. Кажется, это невозможно на одном конце, как для DP ", если проблема была разбита на ряд подзадач и было найдено оптимальное решение для каждой подзадачи, то полученное решение было бы реализовано посредством решения этих подзадач. Проблема которая не имеет такой структуры, не может быть решена с помощью динамического программирования "( Reference ). Принимая это во внимание, оптимальное решение для платы 7x7 может быть неоптимальным (даже неверным) для 8x8. Таким образом, результат проблемы может не реализоваться путем оптимального решения подзадачи.
С другой стороны, DP - это оптимизация для проблем с возвратом ... если это так, то проблема с 8-ю фермами может быть решена с помощью обратного отслеживания ... означает ли это, что хранение только тупиков может преобразовать решение с обратным отслеживанием в DP? Если это так, то возможно 2,1 не выполнимо для родителя 1,1, но может быть выполнимо для 1,2.
Обновление
У кого-нибудь есть идея, можно ли решить проблему 8-ферзя или n-ферзя с помощью динамического программирования? Если да, то каковы будут ваши комментарии к приведенным выше наблюдениям?