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