问题标签 [n-queens]

我一直在研究 8 个皇后问题，但我被卡住了。我不想要代码。我希望得到指导和指导，以便了解如何使用回溯递归自己解决这个问题。

该程序应该通过在 ASCII 中绘制皇后的位置来枚举 N 皇后问题的所有解决方案，就像这里的两个解决方案一样。

到目前为止，我的伪代码是：

我的伪代码中没有任何回溯递归，因为我不知道该怎么做。

非常感谢任何帮助。请不要代码。

（响应 Nemo 的更新）：

这是正确的吗？

（更新 2）：

依此类推，直到

更新 3（已编辑）：

我对使用动态编程实现 8-queen 问题的想法感到非常困惑。对于 DP 来说，这似乎是不可能的“如果将问题分解为一系列子问题并找到每个子问题的最佳解决方案，那么最终的解决方案将通过这些子问题的解决方案来实现。一个问题没有这种结构的问题不能用动态规划来解决”（参考）。考虑到这一点，7x7 电路板的最佳解决方案可能不是 8x8 的最佳解决方案（甚至不正确）。因此，问题的结果可能无法通过子问题的最优解来实现。

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

更新

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

任务是计算将 N 个皇后放在 NxN 板上的解决方案的数量。我试图考虑所有可能的情况来提高性能，但是在 N = 15 的情况下运行几乎需要 50 秒。这是我所做的：

请告诉我是否可能（我的老师没有给出确切的时间，他只是告诉“可接受的时间”。如果可能，请告诉我如何，或者只是给我一个线索！

在为 n-Queen 问题的所有可能解决方案实施算法时，我发现许多分支都达到了相同的解决方案。有没有什么好方法可以为 n-Queens 问题生成每个独特的解决方案？如何避免不同分支产生的重复解决方案（存储和比较除外）？

这是我尝试过的第一个解决方案： http ://www.ideone.com/hDpr3

代码：

为了生成所有可能的解决方案，我使用了相同的代码nqdfs_all ()函数，但没有将控件返回给父级，而是继续枚举和检查。调用此函数会显示不同分支达到的重复结果。

我已经在以下位置运行了实现：http: //www.apl.jhu.edu/~hall/java/NQueens.java，它解决了具有 O(n) 时间复杂度的 N-queen 问题。它速度惊人，无需搜索即可帮助找到一种解决方案。但是，我不太清楚背后的逻辑。他们为什么把问题分成3个：奇数、偶数（但不是6k形式）、偶数（但不是6k+2形式）。任何人都可以检查代码并为我更详细地解释（仅逻辑）吗？

研究 N 皇后问题。正确填充堆栈有些困难。希望任何人都可以给我任何指示。

现在我的输出很奇怪..只有 7 个节点，但我的“成功”布尔值需要 8 个才能实现。当我认为它应该是 1,2 时，头节点是 2,1，因为我会增加列。

我知道我也需要检查对角线，但我正在一步一步地进行。

如果我的冲突检查方法，我需要解决的第一件事。它永远不会返回 true（因为，是的，存在冲突）。如果我弄清楚了什么，我会尽快更新。

编辑：

我对代码进行了一些更改，以进行更递归的尝试。我的新输出是这样的：

这是正在进行的代码/工作的一部分。现在，它正在进入一个永恒的循环，很可能是从那个时候开始的（conflictCheck）

}

我正在研究 n-queens 问题，并且正在测试我目前所拥有的东西，看看我的逻辑是否正确。我的循环停止输出并在调整第二个皇后块后进入无限循环，以免发生冲突。

我不认为我的逻辑会陷入无限循环，基本上是：Push (1,1)

检查冲突

如果冲突，调整顶部皇后，如果无法调整，弹出，调整新顶部

如果没有冲突并且大小 < 8，则 push (size+1, 1) -这显然是一个冲突

检查冲突等

}

我的输出是：

我正在用java解决一些编程练习。一切都很好，直到我的大脑在 N Queens 练习中有点僵硬。

我已经通过使用回溯实现了 N 个皇后问题的解决方案。我正在检查每个皇后的位置是否安全，方法是检查它的左上角、右上角和顶部，然后将其放在行中，否则我会回溯。

它为 N 的某些值（例如 4 和 8）提供了正确的解决方案，但对于其他值（例如 6）则不正确。

我不知道我错过了什么。任何帮助将不胜感激。

这是代码：

我无法理解回溯，我可以从概念上理解我们采取了行动，然后如果无法从中找到解决方案，我们会尝试下一个解决方案。

考虑到这一点，我正在尝试解决 N Queens 问题，我正在找出可以放置在下一行中的所有可能的候选人，然后一个一个地尝试它们，如果候选人没有产生解决方案，我弹出它并与下一个一起去。

这是我提出的代码的核心：

它不会为我提供的任何输入打印任何内容。我尝试运行它gdb但没有成功，我认为这是因为我对回溯的基本理解存在问题。

我已经在几本书和一个在线教程中阅读了关于回溯的内容，但我仍然感到朦胧，如果有人能给我一些想法来解决这个问题并帮助我理解这个有点不直观的概念，那就太好了。

整个可编译的源代码是：