问题标签 [n-queens]

我正在尝试编写代码来为 N-Queens 生成独特的解决方案。我能够为 N = 4 和 6（但不能为 N 的其他情况）生成正确的解决方案，并且已经消除了由于旋转 180 度和 90 度而产生非不同解决方案的情况。问题在于我对如何消除其他冗余案例的理解。

例如，对于 N = 5，我应该得到 2 个唯一的解决方案，但我正在生成 3 个。要消除的 2 个冗余解决方案是（第 3 个解决方案是正确的）：

问----问----

--Q-- ----Q-

----问 -问---

-Q--- ----Q

---Q- --Q--

对于一项任务，我的任务是使用 Matlab 和递归设计一个 NQueens 算法。所以我设置它的方式是我有 2 个辅助函数 isValid，它测试有效的放置，以及 recursiveQueen，它从 0 的 MxM 板上放置或删除一个皇后，并从每一个可能的移动中添加一个或删除一个皇后可以使。为了空间，我从 recursiveQueen 函数中删除了 add 函数，但它所做的只是在 8 个方向上加或减 1。

我遇到的主要问题是在我的 solveNQ 函数中，如果没有为前一行找到解决方案，它会转到下一列。我将步骤分解为 6 ​​件事：

1）在第一排放置一个皇后

2）在下一行的下一个有效位置放置一个皇后

3) 重复第 2 步，直到没有找到该行的有效位置

4）从最后一行删除女王

5）将皇后放在该行的下一个有效位置

6）重复步骤 1-5 直到所有行都包含一个皇后（我没有编码这一步）

我正在研究8皇后问题，我认为以下算法可以解决这个问题（但似乎不正确）

我的算法在 8X8 棋盘上以这种方式工作：

1. 一开始在棋盘的随机位置放一个皇后
2. 将当前女王的水平线、垂直线和两条对角线上的所有位置标记为无法使用。
3. 将另一个皇后放在棋盘上仍然空闲的任何位置
4. 重复这个过程（从第 2 点开始），直到板上有可用的位置

我已经在纸上尝试过这个解决方案，但通常我只能放置 7 个皇后而不是皇后......

所以我认为这个解决方案能够放置一些不能互相吃掉的皇后，但它不能确保，如果我使用 nXn 板，我总是可以放置 8 个皇后......

这是真的吗？

肿瘤坏死因子

安德烈亚

我正在为大学考试学习 Prolog，但我对以下练习有一些问题。

我有以下 8 皇后问题的经典解决方案（这对我来说不是问题），修改这个解决方案我必须为处理可变数量皇后的更通用的 n 皇后问题创建一个新的解决方案。

好的，这个程序看起来很简单：我有一个女王列表，他们不能互相攻击。

如果女王列表为空，则女王不可能攻击列表中的另一个女王，因此空列表是问题的解决方案（它是解决方案的基本情况）

*如果皇后列表不为空，我可以将其划分为 [X/Y|Others] 其中 X/Y 在列表中第一个皇后的棋盘上的位置* （位置是夫妇的 rappresentend (X,Y ) 其中 X 是列，Y 是行)

因此，如果以下关系为真，则列表 [X/Y|Others] 是问题的解决方案是真的：

1. 子列表 Others 本身就是一个解决方案（Others 不包含攻击列表中其他女王的女王）

2. Y 属于 1 到 8 之间的整数值（因为我有 8 行）

3. 列表的第一个女王不要攻击子列表中的其他女王

然后定义了noattack关系，它指定我什么时候可以说一个女王不攻击另一个女王是真的（这很简单：他们不能停留在同一行，同一列，同一对角线）

最后，我有一个解决方案模板，可以简化我的生活，将 X 值限制在 1 到 8 之间（因为我知道 2 个皇后不能留在同一列……所以解决方案中的每个皇后都留在不同的列所有其他皇后）

所以我认为最大的问题在于我指定列数的那一行：

在我定义解决方案模板的那一行：

我不知道如何扩展以前的解决方案来处理可变数量的皇后。

我正在 Prolog 学习 SWI Prolog 实施的大学考试。

我对这个版本的 8 Queen 问题如何使用排列解决问题有一些疑问：

在以前的解决方案中，我使用了这个解决方案模板： [1\Y1, 2\Y2, 3\Y3, 4\Y4, 5\Y5, 6\Y6, 7\Y7, 8\Y8] 简单地说每个女王都有要在不同的行上，X 值可能会受到限制。

这个版本的程序有很大的不同，因为我们可以观察到，为了防止垂直攻击，所有的皇后都必须在不同的行上，所以我每行都有一个皇后。

因此，在不丢失信息的情况下，我可以说解决方案将是列表的排列：[1,2,3,4,5,6,7,8]，其中每个元素都表示女王的 Y 坐标。

所以在这种情况下，我只通过它的 Y 坐标（它的行索引）来表示一个皇后位置

所以我有解决方案的关系，而不是说如果皇后是[1,2,3,4,5,6,7,8]原始列表的前排列并且如果这个排列是安全的（每个皇后在这个排列列表不攻击其他女王）。

好的，这很清楚......现在它定义了安全关系。

有一个基本情况说，如果列表为空，那么这是安全的，因为没有攻击。

并且有一个一般情况，列表不为空。如果列表不为空，我可以将其划分为[Queen|Others]，其中Queen是列表中的第一个皇后， Others是剩余的子列表......所以如果子列表 Others 它，原始列表[Queen|Others]是安全的本身就是一个解决方案（如果是安全的，如果Others中没有攻击的话）并且如果第一项Queen没有攻击其他子列表中的另一个Queen...

好的......直到现在我认为这对我来说很清楚......

现在我对noattack关系的定义有一些问题！

问题是我只通过它的 Y 坐标和 X 坐标来表示一个皇后位置，它没有明确存在。

我知道为了规避这种表示的限制，有以下概括（我希望能很好地理解......我不太确定......）：**我也知道每列必须有一个女王棋盘的，所以与列表中的第一个皇后（Queen）和子列表Others的X距离必须为1**

第一项Queen和子列表Others的距离是第一项Queen和最接近它的Queen的X距离，我的推理是否正确？

因此，如果女王在不同的列上，则noattack关系为 TRUE（对于构造总是正确的），我可以表示必须在不同的行上，说从女王和其他子列表中最近的女王的 X 距离为 1。

但是，如果我的推理是正确的，我会发现很多麻烦试图理解这部分代码中这个东西是多么的好：

我在序言中实现随机搜索。

代码是

但它返回错误。我不能很好地理解序言，但我必须实现它。我找不到哪里错了。

我希望提高算法的速度，以计​​算 N+1 皇后问题的解决方案数量（将N+1皇后放在NxN棋盘上，有 1 个棋子）。我基本上使用蛮力与回溯相结合，我首先将棋子放在棋盘上的随机位置（没有没有边缘的正方形的边缘和角落），然后我才开始使用回溯放置皇后。这种方法很容易，但也很慢。什么算法会更快？

我正在考虑首先在棋子的每一侧放置一个棋子和 4 个皇后，但我不确定这会提高计算速度。

我有以下代码用于使用 pthreads 计算 n-queen 谜题。但是当我尝试编译该代码时，我收到以下错误消息：

wikithread.c:7:5：错误：在文件范围内可变地修改了“hist”

如果我更改上部，并为数组动态分配内存，则会收到以下错误：

然后我收到以下错误：

wikithread.c:8:1：警告：数据定义没有类型或存储类[默认启用] wikithread.c:8:1：错误：'hist' wikithread.c:7:6 的类型冲突：注意：以前'hist' 的声明在这里 wikithread.c:8:1: 错误: 初始化元素不是常量 wikithread.c: 在函数'solve'中: wikithread.c:23:27: 错误: 下标值既不是数组也不是指针也不是向量wikithread.c:23:27：错误：下标值既不是数组也不是指针也不是向量wikithread.c:26:7：错误：下标值既不是数组也不是指针也不是向量

任何人都可以帮我解决问题吗？

我有以下用于 n-queen 谜题的 Pthreads 代码。它编译成功，但我得到错误的答案。无论我输入什么值，我都会得到答案为零。我想我的代码中有某种逻辑错误。我猜这个问题发生在回溯/递归部分的某个地方。如果有人可以建议我一个解决方案，我会很高兴。

请注意：我被要求以任何我喜欢的方式修改 NQueens 问题。我已经想到了这种方式，并想实现它。这不是一个直接的家庭作业问题，而是一个我如何实施自己的修改的问题。

我在下面编写了一个解决 4 个皇后的代码。所以根据这段代码，没有两个皇后可以在同一行、同一列、同一对角线上，从而不被攻击。我正在尝试修改它，如果我放置一个皇后，那么它可以放在同一列但跳过两行，它可以放在同一行跳过两列，同样它可以放在同一个对角线上跳过两个行和两列。

所以基本上，简单来说，女王可以放置在同一行，同一列和同一对角线上，跳过两个块。

对于 4 个皇后输出当前如下所示：

和

但是也应该给出以下输出：

所以在这里，女王每两个街区后被放置，水平，垂直和对角线。

代码：

我究竟做错了什么？如何更改我的代码以使其适用于修改？