algorithm - 使用动态规划的 8 皇后问题

Question

我对使用动态规划实现 8 皇后问题的想法感到很困惑。对于DP来说，似乎不可能在一端将问题分解成一系列子问题，并找到每个子问题的最优解，然后通过对这些子问题的解来实现最终的解决方案。一个问题没有这种结构的问题不能用动态规划解决”(Reference)。考虑到这一点，7x7 板的最佳解决方案对于 8x8 板可能不是最佳的(甚至不正确)。因此，问题的结果可能无法通过子问题的最优解来实现。

另一方面，DP 是回溯问题的优化...如果是这样，那么 8 皇后问题可以通过回溯来解决...这是否意味着通过仅存储死胡同可以将回溯解决方案转换为 DP？如果是这样，那么可能 2,1 对于父 1,1 不可行，但对于 1,2 可能可行。

更新

任何人都知道 8 皇后或 n 皇后问题是否可以使用动态规划来解决？如果是这样，那么您对上述观察有何评论？

Answer 1

7x7 板的最佳解决方案对于 8x8 可能不是最佳的(甚至不正确)。

是的，你是对的。但这不是拆分问题的好方法。查看paper yi_H posted in his answer ，定理 2.4，并查看算法描述。他们根据闭合线集(即受到皇后威胁的线)将解决方案划分为等价类。定理 2.4 保证一旦他们解决了特定闭合线上的子问题，他们就可以单独解决其余问题，然后合并结果!非常聪明。