使用动态规划解决8皇后问题

Question

我对使用动态规划实现八皇后问题的想法感到相当困惑。似乎在某一方面，DP不可能实现这一点，“如果问题被分解为一系列子问题，并找到了每个子问题的最优解，则通过这些子问题的解决方案实现结果的问题可以得到解决。没有这种结构的问题不能用动态规划来解决”(参考文献)。考虑到这一点，7x7棋盘的最优解也可能不是8x8棋盘的最优解（甚至是不正确的）。因此，问题的结果可能无法通过子问题的最优解实现。

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

更新

有人有想法吗，八皇后或n-皇后问题是否可以通过使用动态规划来解决？如果可以，那么对上述观察结果您有什么评论？

- mqpasta

---

@mqpasta，搜索“8皇后动态规划”会得到相当多的结果。你有没有阅读过这些来源，看看它们如何为这个问题定义DP？你是否不同意？你是正确的，7皇后解决方案不是8皇后解决方案的组成部分，所以你的问题非常有趣。 - Ray Toal

嗯，我没有找到任何描述8皇后问题为DP的资源... 但我认为它一定是DP用于回溯优化... 但没有证明这一点... - mqpasta

从理论上讲，这是一个有趣的问题（尽管我不知道DP如何用于此），但我不知道为什么您想进一步优化它，一个好的回溯算法将检查少于4 * 7！即20160个位置（请记住，由于对角线的原因，其中很多将提前终止）。 - Karoly Horvath

4*7! - 当n = 8。如果n > 100会怎样？ - TheHorse

@yi_H：TheHorse说得对，“8皇后问题”只是这个问题的名称，也指代了一般的“n皇后问题”。 - ypercubeᵀᴹ

@TheHorse：我发布了一篇动态规划解决方案，可以在O(f(n)*8^n)时间复杂度内解决它。这回答了你的“如果”问题吗？ :) - Karoly Horvath

Answer 1

7x7棋盘的最优解法可能不适用于8x8（甚至是错误的）。

是的，你说得对。但这并不是一个好的问题分割方式。请查看yi_H在他的答案中发布的论文，定理2.4，并查看算法描述。他们根据封闭线（即被皇后攻击的线）的集合将解决方案划分为等价类。定理2.4保证一旦他们解决了特定封闭线集合的子问题，他们就可以单独解决其余部分，然后将结果组合起来！非常聪明。

- Tomas

Answer 2

仅提供显而易见的谷歌搜索结果：

N皇后问题的动态规划解决方案

注意：对于大的n，此方法仍然非常慢，O(f(n)*8^n)，您最好使用其他算法：

N皇后问题的多项式时间算法

- Karoly Horvath

---

你的第一篇关于“N皇后问题的动态规划解法”的文章不是很清晰。我读了那篇文章，即使作者提供了一个运行示例。至于第二个链接，它适用于排列或随机解决方案...更像是遗传算法！无论如何...我正在考虑为纠正错误的8皇后问题制定一个DP问题的计划...好主意！ - mqpasta

但是，我仍在寻找描述或评论我问题中所述观察的答案。 - mqpasta