问题标签 [n-queens]

我正在研究 Ivan Bratko 书上的 Prolog：人工智能编程，并且在书中我发现了这个版本的 8 Queens 问题，它使用空间状态“图”来解决问题：

它结合了基于排列的 8 个皇后问题解决方案（使用它的noattack/3关系）和我认为构建可能的后继状态状态的s/2谓词（我的图表的节点）。所以我有类似的东西：

s（实际状态，后继状态）

我认为目标/1谓词只指定我必须准确放置 8 个皇后。

在书上说我执行这个查询：solve([],Solution)它将产生一个随着皇后数量增加的棋盘位置列表，并且这个列表将以八个皇后的安全配置结束。

但是，如果我尝试执行此查询不起作用，我将获得此输出：

因为，正确地，在第 2 行中调用的noattack谓词只接受 2 个参数，但noattack谓词必须有 3 个参数……书上的 bue 是以这种错误的方式给出的，我不知道如何解决这个问题……

为什么？我错过了什么？

嗨，我刚刚参加了最后一年的编程考试，有人问我一个问题：使用什么排序和搜索算法来解决 8 个皇后问题。

如果我错了，请纠正我，但根本没有排序......我知道在放置女王和回溯期间需要基本级别的搜索，但是排序在哪里？如果有的话？

下面是我一直在看的，只是看不到它。

SICP 包含 n-queens 解决方案的部分完整示例，通过遍历最后一行中每个可能的皇后位置的树，在下一行中生成更多可能的位置以组合迄今为止的结果，过滤可能性以仅保留那些最新的女王是安全的，并且递归地重复。

这种策略在大约 n=11 后以最大递归误差崩溃。

我已经实现了一种替代策略，该策略从第一列进行更智能的树遍历，从未使用的行列表中生成可能的位置，将每个位置列表连接到尚未使用的行的更新列表中。过滤那些被认为是安全的对，并在这些对上递归映射以用于下一列。这并没有爆炸（到目前为止），但 n=12 需要一分钟， n=13 需要大约 10 分钟才能解决。

不是真的在寻找代码，而是对一个或两个策略的简单解释，它不那么天真，并且与功能性方法相得益彰。

我很难理解递归和回溯，尽管我做了一些简单的练习（例如斐波那契）。所以请允许我在这里介绍我的“脑流”：

1. 我读了教科书，知道如果前一个皇后的当前位置消除了将下一个皇后放在下一列的可能性，则可以使用回溯来删除前一个皇后。所以这似乎很容易，我需要做的就是删除它并让程序决定下一个可能的位置。

2. 过了一会儿，我发现程序停在第 6 个皇后，所以我发现如果我简单地删除第 5 个皇后，程序只需将其放回当前位置（即，给定前 4 个皇后，第 5 个皇后总是落入相同的位置）地方，这并不奇怪）。所以我认为我需要跟踪最后一个女王的位置。

3. 这是我感到困惑的时候。如果我要跟踪最后一个皇后的位置（这样当我回溯程序时不允许将皇后放在同一个地方），有两个潜在的困难：

a) 假设我移除了第 5 个皇后，我必须编写代码来决定它的下一个可能位置。这可以通过忽略其当前位置（在被移除之前）来解决，并继续在以下行中寻找可能的位置。

b) 我应该追踪所有之前的皇后吗？似乎是这样。假设实际上我必须删除的不是一个皇后，而是两个皇后（甚至更多），我当然需要跟踪它们当前的所有位置。但这比看起来要复杂得多。

1. 于是我开始在课本中寻找答案。遗憾的是它没有回溯代码，只有递归代码。然后我在这里找到了代码：

http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

这让我大吃一惊，因为它是如此简单，但它确实有效！唯一的回溯部分是删除最后一个女王！所以问题是：下面的代码如何确保当给定 4 个皇后的位置时，第 5 个不会一次又一次地落到同一个地方？我想我不明白的是你怎么能递归地回溯（比如说你需要删除更多的皇后）。递归前进时我没有问题，但是如何递归后退？

好的。现在我有一些可以工作的代码，但我主要根据上面的代码修改了我自己的代码，所以我很不稳定：

假设 numQueen 是 5，所以在 for 循环中我们将检查是否可以放置第 6 个皇后。我们知道这对所有行都是不可能的，所以该函数返回 false。我假设它然后“收缩”回它被调用的位置，即当 numQueen 为 4 时。因此调用 ClearQueen(4) 并删除最后一个皇后（第 5 个）。显然 for 循环还没有完成，所以我们将尝试下一行，看看它是否允许进一步开发。即我们检查是否可以将第 5 个皇后放在下一行，如果可以，我们将进一步检查是否可以放置第 6 个皇后，依此类推。

是的，它似乎工作，嗯，嗯，是的。

女王统治给定一个 n×n 棋盘，统治数是攻击或占领每个方格所需的女王（或其他棋子）的最小数量。当 n=8 时，皇后的支配数是 5。写一个谓词解（N），得到覆盖所有方格所需的最小皇后数。

我正在解决 Haskell 中的 8-queens 问题，只使用基本功能没什么
特别的，这是代码：

为了澄清SafeH函数检查没有皇后在同一行 H 代表 Horizantly 而SafeD应该检查对角线冲突
我确信该SafeH函数没问题SafeD
并且在编译代码时它给我没有问题但是在调用时 它给我这个错误的queens功能：

谁能帮帮我吗？？提前感谢每一件事:)

我刚开始学习编写 Haskell 代码，如果这是一个愚蠢的问题，我深表歉意。我试图通过使用[]单子来重做八皇后问题。这是代码，

当我尝试

它不起作用，但会产生以下错误：

那么我如何在这里实现我想要做的呢？

所以我这样做是为了做作业，我不知道我的错误在哪里。非常感谢任何帮助。

我的理解是这样的。

1. 初始化一个堆栈以跟踪哪一行和哪一列有皇后。
2. 在第一个方格上放置一个皇后，将其位置推入堆栈。推（0,0）；然后设置该行已被填充的变量。填充+；

3.然后循环

检查当前行或列是否与另一个皇后发生冲突。

一个。没有冲突。推入堆栈。增加填充的行变量。填充++；向上移动一排。

湾。有冲突。向右移。科尔++；

C。不能再向右移动了。弹出堆栈并设置为行和列。减去填充。然后移过去。科尔++；然后再试一次。

我一直在尝试使用回溯来解决 N 皇后问题。我在网上找到的大多数方法都涉及向量，这让我很难像互联网上的一些小程序那样将解决方案可视化。

我想出的解决方案给了我很多问题（我感觉这与使用的动态 2D 数组的索引有关）并且我无法使用 Dev-C++ 调试器解决它。任何帮助和/或建设性的批评受到高度赞赏。提前谢谢了。

这是我想出的解决方案：

我已经搜索但没有找到答案。

我正在尝试使用在 Java 中实现的模拟退火 (SA) 算法来解决 8 个皇后谜题（更具体地说是 N 个皇后谜题），但在目标函数方面我有点卡住了。我怎么知道我是否接近我的目标（最佳解决方案）？

我想出了两种方法来给尝试“积分”（积分越多越好）：

1. 有多少皇后是合法的

2. 棋盘上有多少个合法的皇后 + 下一个合法放置的皇后的可用位置数量

但我不能决定这些是否有好处。你们能给我一些提示或任何其他输入吗？:)