解决 N 皇后问题...我们能走多远？

Question

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 代码）

我也有兴趣查看其他语言的替代实现（其性能比我的实现更好）或者我的算法/程序是否有改进的空间

Answer 1

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

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

这个问题最有趣的版本是计算解决方案。最先进的技术在名为整数序列百科全书的精彩参考文献中进行了总结。已计算至 N=26。我猜想这也使用了动态编程，但与列出每个解决方案的情况不同，算法问题要深入得多，并且有待进一步发展。

Answer 2

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）

我不知道 。主要记录每个解决方案需要多少处理时间，而是记录在发现每个板的算法优先解决方案之前需要多少次失败的皇后放置。当然，皇后放置率取决于 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 个算法步骤中的每一个的简单说明。

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

Answer 3

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

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

以 100 个皇后为例：

?- time((n_queens(100, Qs), labeling([ff], Qs))).
Qs = [1, 3, 5, 57, 59 | ...] .
2,984,158 inferences, 0.299 CPU in 0.299 seconds (100% CPU, 9964202 Lips)

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

下面是一个动画 GIF，展示了使用 SWI-Prolog 解决 N=40 皇后问题的完整过程：

Answer 4

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

#!/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!))

Answer 5

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

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

这些近乎完美启发式的参考文献是[Kale 90 ] 和 [圣塞贡多 2011]

Answer 6

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

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

参见维基百科：
“对于所有 n ≥ 4，存在将 n 个皇后放置在 n × n 板上的显式解决方案，不需要组合搜索任何内容。”。

Answer 7

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

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

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

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

Answer 8

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

Answer 9

如果你只想要 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 的第一个解。