问题标签 [n-queens]

我正在研究 n-queen 回溯器。有人可以向我解释如何other_row_pos检查对角线吗？我不确定它为什么起作用或如何起作用。

取自维基书籍 - http://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens：

我正在尝试以递归方式解决 8x8 棋盘上的 n-knights 问题。n-knights 问题是 n- queens 问题的变体，其中皇后被骑士替换。没有一块可以拿下另一块。

到目前为止我的代码：http: //pastebin.com/TVza3jVU。

输入包括必须放置在棋盘上的骑士数量。我的代码打印了很多正确的板

输出如下所示（示例）：

“1”代表骑士。

我的问题如下：

这是我的脚本将打印的最后一块板。它永远不会在 [0][0] 上放置一个骑士。我不知道为什么。它还跳过了一些配置。我的递归有问题吗？

下面是我尝试打印 8 个皇后问题的所有解决方案（将 8 个皇后放在棋盘上，这样它们都不会互相攻击）。但是，此解决方案仅打印 4 个答案，而 92 应该存在。任何人都看到有什么问题吗？

上面的代码是用于使用回溯解决 N 皇后问题。我认为它可以将两行的前 2 个皇后放在各自的列中，然后当涉及到第 3 行皇后时，它不能放置，因为没有皇后需要攻击它会简单地退出算法 N 皇后......那么这个算法是如何实现回溯的呢？

所以我需要经典的 N-Queens 问题的帮助。

运行程序的命令将是： nqueens N k - 其中 N 是表的大小 (N x N)，k 是解决方案的数量

因此，例如，如果我通过键入nqueens 4 1来运行程序，则会打印出以下内容。

_ 问 _ _

_ _ _ 问

问_ _ _

_ _ 问 _

但是，我无法弄清楚如何处理超过 1 个解决方案？对于这个问题，我如何才能确定不止一种解决方案？

到目前为止我所拥有的如下：

我想使用回溯模拟 n 个皇后问题。我每次都用一个列表作为参数调用这个 drawboard() 函数，如下所示

此列表“x”是从递归过程返回的，因此将在每次迭代后更新

所以每次它都显示在单独的窗口中。只有在关闭第一个窗口后才会显示下一个窗口，依此类推......

如何在单个窗口中制作东西，或者如何在特定时间间隔后自动关闭这些窗口，以便这些窗口一一显示

我绘制棋盘的功能如下

我编写了一种使用递归和回溯来找到 N-Queens 问题的解决方案的方法。我现在要做的是修改此方法，以便它可以找到所有可能的解决方案。我假设我需要使用 2D 整数数组来存储所有解决方案，并且还添加一个计数器，每次找到解决方案时都会递增。但是，一旦找到解决方案并继续回溯以找到所有其他可能的解决方案，我似乎无法理解如何使这种方法继续下去。我认为我要做的就是摆脱“回归真实”；找到解决方案时会发生这种情况，但是我不知道如何使该方法递归地确定是否找到解决方案....这是我现在拥有的单一解决方案版本：

编辑：修正了方法，结果如下。它仍然可能有点混乱，但它有效！我没有打印找到的每个解决方案，而是将其添加到数组中。我仍然拥有 Queen[] 变量的原因是我可以让解决方案数组独立于棋盘状态。而我仍然拥有 board[][] 变量的原因是因为它使 underAttack() 方法更容易编写（尤其是计算斜率）......无论如何，我非常感谢大家的帮助！

我正在尝试解决方案中的 n-queens 问题。我的教授告诉我使用单个向量作为棋盘，其中向量的第 i 个元素代表棋盘的第 i 列。该元素的值是皇后所在的行，如果该列为空，则为 -1。所以，[0 1 2 -1 -1] 有两列没有皇后，三个皇后被非法放置。当我运行此代码时： (place-n-queens 0 4 #(-1 -1 -1 -1)) 我得到 #(0 1 2 3) 显然所有四个皇后都是非法放置的。我认为问题在于我没有在 cond in place-queen-on-n 检查足够的东西，但我不确定要添加什么来解决在同一对角线上获得皇后的问题。

任何帮助都可以得到这个工作！

下面是我尝试解决 8 个皇后问题以打印一个解决方案。（将 8 个皇后放在棋盘上，这样它们都不会互相攻击）。然而，这个解决方案只放置了 6 个皇后。我需要另一种意见，说明我在哪里犯了错误。我更多的是采用 BFS 风格而不是回溯。

我有一个用于 N 皇后计算的简单 C 程序。我使用 OpenMP 将其并行化。现在我想同时执行串行和并行版本并计算加速。关键是我不想为串行代码创建一个新文件，或者只是将我的解决方案复制到一个没有 OpenMP 指令的新函数。我想要做的是，保留一个函数，并从主函数中告知何时将其作为串行执行，何时作为并行执行。我虽然使用预处理器，但我确定它是否可能，如果是，我该如何实现它。