24

N皇后问题：

这个问题指出，给定一个大小为 N 乘 N 的棋盘，找出不同的排列方式，其中 N 个皇后可以放在棋盘上而没有任何人互相威胁。

我的问题是：
程序可以在合理的时间内计算出答案的 N 的最大值是多少？或者到目前为止我们见过的最大的 N 是多少？

这是我在 CLPFD(Prolog) 中的程序：

generate([],_).
generate([H|T],N) :-
   H in 1..N ,
   generate(T,N).

lenlist(L,N) :-
   lenlist(L,0,N).

lenlist([],N,N).
lenlist([_|T],P,N) :-
   P1 is P+1,
   lenlist(T,P1,N).

queens(N,L) :-
   generate(L,N),lenlist(L,N),
   safe(L),
   !,
   labeling([ffc],L).

notattack(X,Xs) :-
   notattack(X,Xs,1).

notattack(X,[],N).
notattack(X,[Y|Ys],N) :-
   X #\= Y,
   X #\= Y - N,
   X #\= Y + N,
   N1 is N + 1,
   notattack(X,Ys,N1).

safe([]).
safe([F|T]) :-
   notattack(F,T),
   safe(T).

这个程序工作得很好，但是它所花费的时间随着 N 的增加而不断增加。这是一个示例执行：

?- queens(4,L).

L = [2, 4, 1, 3] ;

L = [3, 1, 4, 2] ;

No

这意味着您将 4 个皇后放置在第 1 列的第 2 行、第 2 列的第 4 行、第 1 行在 3 中和第 3 行在 4 中。（在 4×4 棋盘中）

现在让我们看看这个程序是如何执行的（计算第一个排列所用的时间）：
N=4,5.....10 在一秒钟内计算
N=11-30 需要 -1-3 秒
N=40 ..50 仍然在一分钟内计算
在 N=60 它超出了全局堆栈（搜索空间巨大）。

这是过去的作业问题。（最初的问题只是编码 N-Queens）

我也有兴趣看到其他语言的替代实现（比我的实现更好）或者如果我的算法/程序有改进的空间

4

9 回答 9

12

这个讨论将三个不同的计算问题混为一谈：(1) 找到 N 个皇后问题的解决方案，(2) 列出某个固定 N 的所有解决方案，以及 (3) 计算某个固定 N 的所有解决方案。第一个问题看起来很棘手起初对于板的大小，例如 N=8。然而，正如维基百科所暗示的，在某些关键方面，当 N 很大时很容易。大棋盘上的皇后并没有那么多交流。除了内存限制之外，随着 N 的增加，启发式修复算法的工作越来越容易。

列出每个解决方案是另一回事。这可能可以通过一个良好的动态编程代码来完成，该代码的大小足够大，以至于读取输出没有意义。

这个问题最有趣的版本是计算解决方案。最先进的技术总结在一本被称为“整数序列百科全书”的绝妙参考资料中。它已被计算到 N=26。我猜这也使用了动态编程，但与列出每个解决方案的情况不同，算法问题更深入，并且可以进一步发展。

于 2009-12-08T00:40:42.460 回答
10

Loren Pechtel 说：“现在对于一些真正的精神错乱：29 花了 9 秒。30 花了将近 6 分钟！”

对于不同尺寸的电路板，回溯复杂性缺乏可预测性是这个谜题中最让我感兴趣的部分。多年来，我一直在建立一个算法步骤的“计数”列表，以找到每个板尺寸的第一个解决方案- 在递归 C++ 函数中使用简单且众所周知的深度优先算法。

以下是 N=49 ... 减去 N=46 和 N=48 的所有这些“计数”的列表，它们仍在进行中：

http://queens.cspea.co.uk/csp-q-allplaced.html

（我在整数序列百科全书（OEIS）中列为A140450）

该页面包含指向匹配的第一个解决方案列表的链接。

（我的第一个解决方案列表是 OEIS 序列号A141843）

我主要不记录每个解决方案需要多少处理时间，而是记录在发现每个板的算法优先解决方案之前需要多少次失败的后放置。当然，queen 放置率取决于 CPU 性能，但如果在特定 CPU 和特定板尺寸上进行快速测试，计算解决这些“找到”解决方案中的一个需要多长时间是一件容易的事。

例如，在 Intel Pentium D 3.4GHz CPU 上，使用单个 CPU 线程 -

  • 对于 N=35，我的程序每秒“放置”了 2400 万个皇后，并且只用了 6 分钟就找到了第一个解决方案。
  • 对于 N=47，我的程序每秒“放置”了 2050 万个皇后，耗时 199 天。

我目前的 2.8GHz i7-860 每秒通过大约 2860 万个皇后，试图找到 N=48 的第一个解决方案。到目前为止，它已经花费了 550 多天（理论上，如果它从未中断过的话）未能成功放置 1,369,331,731,000,000 个（并迅速攀升）皇后。

我的网站（还）没有显示任何 C++ 代码，但我确实在该网页上提供了一个链接，以简单说明解决 N=5 板所需的 15 个算法步骤中的每一个。

这确实是一个美味的拼图！

于 2010-08-21T19:48:05.393 回答
5

您使用的是哪个 Prolog 系统？例如，使用最新版本的 SWI-Prolog，您可以使用原始代码在几分之一秒内轻松找到N=80和N=100的解决方案。许多其他 Prolog 系统将比这快得多。

N-queens 问题甚至出现在 SWI-Prolog 的在线示例之一中，可作为SWISH中的CLP(FD) Queens 获得。

100 个皇后的例子：

?-时间（（n_queens（100，Qs），标签（[ff]，Qs）））。
Qs = [1, 3, 5, 57, 59 | ...] 。
2,984,158 次推理，0.299 CPU在 0.299 秒内（100% CPU，9964202 唇）

SWISH 还向您展示了解决方案的精美图像。

这是一个动画 GIF，显示了使用 SWI-Prolog对N=40 个皇后的完整解决过程：

40皇后的CLP(FD)求解过程

于 2011-01-14T08:18:51.057 回答
4

raymond hettinger 在 pycon 上提出的一个简短的解决方案：python 中的easy ai

#!/usr/bin/env python
from itertools import permutations
n = 12
cols = range(n)
for vec in permutations(cols):
    if (n == len(set(vec[i] + i for i in cols))
          == len(set(vec[i] - i for i in cols))):
        print vec

计算所有排列是不可扩展的，虽然 ( O(n!))

于 2009-12-07T23:12:18.907 回答
4

至于计算机解决的最大 N 是多少，在文献中有参考文献，其中使用冲突修复算法（即本地搜索）找到了 N 约为 3*10^6 的解决方案。例如参见[ Sosic and Gu ]的经典论文。

对于回溯的精确求解，存在一些巧妙的分支启发式算法，可以在几乎没有回溯的情况下实现正确的配置。这些启发式方法也可用于找到问题的前 k 个解决方案：在找到初始正确配置后，搜索回溯以查找附近的其他有效配置。

这些几乎完美 的启发式方法的参考文献是 [ Kale 90 ] 和 [ San Segundo 2011 ]

于 2014-07-31T14:56:56.163 回答
4

程序可以在合理的时间内计算出答案的 N 的最大值是多少？或者到目前为止我们见过的最大的 N 是多少？

没有限制。也就是说，检查解决方案的有效性比构建一个解决方案加上七个对称解决方案的成本更高。

请参阅 Wikipedia： “对于所有 n ≥ 4，将 n 个皇后放置在 n × n 板上存在显式解决方案，不需要任何组合搜索。” .

于 2014-08-01T08:50:10.367 回答
1

我拖出一个旧的 Delphi 程序，该程序计算任何给定电路板尺寸的解决方案数量，进行了快速修改以使其在一次点击后停止，我在数据中看到了一个奇怪的模式：

第一个需要 1 秒才能解决的板是 n = 20。不过，21 在 62 毫秒内解决。（注意：这是基于现在，不是任何高精度系统。）22 花了 10 秒，直到 28 才重复。

我不知道优化有多好，因为这最初是一个高度优化的例程，当时优化规则非常不同。不过，我确实做了一件与大多数实现截然不同的事情——它没有板子。相反，我正在跟踪哪些列和对角线受到攻击，并每行添加一个皇后。这意味着每个测试的单元格需要 3 次数组查找，并且根本没有乘法。（正如我所说，从那时起规则就大不相同了。）

现在来看一些真正的疯狂：29 花了 9 秒。30 花了将近 6 分钟！

于 2009-12-07T23:38:10.493 回答
1

如果您只需要少数解决方案，那么实际上受约束的随机游走（生成和测试）就像 bakore 概述的那样，因为这些解决方案可以快速生成。我在 20 或 21 岁时为一堂课这样​​做，并在 1987 年 3 月的 Pascal、Ada 和 Modula-2 杂志上发表了解决方案，“重访皇后区问题”。我今天刚刚从那篇文章中清除了代码（这是非常低效的代码），在修复了几个问题之后，生成了 N=26 ... N=60 解决方案。

于 2011-01-14T03:17:54.797 回答
0

如果您只想要 1 个解决方案，那么可以在线性时间 O(N) 中贪婪地找到它。我在python中的代码：

import numpy as np

n = int(raw_input("Enter n: "))

rs = np.zeros(n,dtype=np.int64)
board=np.zeros((n,n),dtype=np.int64)

k=0

if n%6==2 :

    for i in range(2,n+1,2) :
        #print i,
        rs[k]=i-1
        k+=1

    rs[k]=3-1
    k+=1
    rs[k]=1-1
    k+=1

    for i in range(7,n+1,2) :
        rs[k]=i-1
        k+=1

    rs[k]=5-1

elif n%6==3 :

    rs[k]=4-1
    k+=1

    for i in range(6,n+1,2) :
        rs[k]=i-1
        k+=1

    rs[k]=2-1
    k+=1

    for i in range(5,n+1,2) :

        rs[k]=i-1
        k+=1

    rs[k]=1-1
    k+=1
    rs[k]=3-1

else :

    for i in range(2,n+1,2) :

        rs[k]=i-1
        k+=1

    for i in range(1,n+1,2) :

        rs[k]=i-1
        k+=1

for i in range(n) :
    board[rs[i]][i]=1

print "\n"

for i in range(n) :

    for j in range(n) :

        print board[i][j],

    print

然而，在这里打印需要 O(N^2) 时间，而且 python 是一种速度较慢的语言，任何人都可以尝试用其他语言（如 C/C++ 或 Java）来实现它。但即使使用 python，它也会在 1 或 2 秒内获得 n=1000 的第一个解决方案。

于 2018-09-20T21:23:16.067 回答