使用动态规划的 8 皇后问题
我对使用动态规划实现 8 皇后问题的想法感到非常困惑。对于DP来说，似乎在一端是不可能的“如果将问题分解为一系列子问题，并找到每个子问题的最优解，那么最终的解决方案将通过这些子问题的解决方案来实现。一个问题没有这种结构的问题无法用动态规划来解决”（参考）。考虑到这一点，7x7 板的最佳解决方案对于 8x8 板可能不是最佳的（甚至是错误的）。因此，问题的结果可能无法通过子问题的最优解来实现。
另一方面，DP是针对回溯问题的优化...如果是这样，那么8皇后问题可以通过回溯来解决...这是否意味着通过仅存储死胡同可以将回溯解决方案转换为DP？如果是这样，那么 2,1 对于父级 1,1 可能不可行，但对于 1,2 可能可行。
更新
有人知道8皇后问题还是n皇后问题可以通过动态规划来解决吗？如果是这样，那么您对上述观察有何评论？
I am quite confused with idea of implementing 8-queen problem using dynamic programming. It seems it is not possible at one end as for DP " if the problem was broken up into a series of subproblems and the optimal solution for each subproblem was found, then the resulting solution would be realized through the solution to these subproblems. A problem that does not have this structure cannot be solved with dynamic programming" (Reference). By taking this in account, the optimal solution for 7x7 board might not optimal as well (even incorrect) for 8x8. So, the result of problem might not realize through optimal solution of sub-problem.
At the other hand, DP is optimization for backtracking problems... if so then 8-queen problem can be solved by backtracking... does it mean that by storing only dead-ends can convert backtracking solution into DP? If so, then might 2,1 is not feasible for parent 1,1 but might feasible for 1,2.
Update
anyone have idea that whether 8-queen or n-queen problem can be solved by using dynamic programming? If so then what will be your comments on observations given above?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
7x7 板的最佳解决方案对于 8x8 板可能不是最佳的（甚至不正确）。
是的，您是对的。但这并不是一个分解问题的好方法。看看论文yi_H在他的答案中发布，定理2.4 ，并查看算法描述。他们根据封闭线（即受到皇后威胁的线）的集合将解划分为等价类。定理 2.4 保证一旦他们解决了特定封闭线上的子问题，他们就可以单独解决其余问题，然后组合结果！非常聪明。
optimal solution for 7x7 board might not optimal as well (even incorrect) for 8x8.
Yes, you are correct. But this is not a good way to split the problem. Look into paper yi_H posted in his answer, theorem 2.4, and look at the algorithm description. They divide the solutions into equivalence classes according to the sets of closed lines (i.e. lines which are threatened by queens). The theorem 2.4 guarantees that once they solve the sub-problem on the particular set of closed lines, they can solve the rest separately and then combine the result! Very clever.
只是发布明显的谷歌点击：
A Dynamic Planning Solution to the n-皇后问题
注意：对于大 n，这仍然非常慢，O ( f(n)*8^n)，你最好使用其他算法：
N 皇后问题的多项式时间算法
Just posting the obvious google hit:
A dynamic programming solution to the n-queens problem
Note: this is still very slow for large n's, O ( f(n)*8^n), you better use some other algorithm:
A Polynomial Time Algorithm for the N-Queens Problem