解决N-皇后区的问题...我们能走多远?

Question

N-皇后问题：

这个问题的国家给予一个国际象棋棋盘的大小N N，找到不同的排列在其N皇后可以放在委员会没有任何一个威胁。

我的问题是：
什么是最大的N值对于这一程序可以计算出的答复在合理的时间?或者什么是最大的N我们迄今所看到的?

这是我的节目在CLPFD(序言):

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皇后在第2行，在Column1，行4在第2栏，第1行中的3和第3行中的4.(4通过4个国际象棋棋盘)

现在让我们看看这个程序执行(时间取在计算第一排):
N=4、5的.....10计算在一秒钟内
N=11-30中需要之间-1-3秒
N=40..50仍可计算一分钟内
在N=60它超出全球堆(搜索的空间正在极大的).

这是过去的作业问题。(原来的问题只是代码N-皇后区)

我也有兴趣看到替代实现的其他语言(它执行更好的比我的执行情况)或者如果没有改善的余地在我的算法/程序

Answer 1

在PYCON雷蒙德赫廷杰提出了一个短的解决方案：容易AI在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 2

此讨论合并了三种不同的计算问题：（1）寻找一个解决N后问题，（2）清单一些固定N的所有解决方案，以及（3）第一计数的所有解决方案的一些固定的N.问题看起来棘手在第一对尺寸板的诸如N = 8。但是，维基百科指出，在一些关键方面，它是容易当N大。上大板的皇后不沟通所有的东西。除了存储器约束，启发式算法修复具有更容易和更容易的工作作为N增加。

清单每一个解决方案是一个不同的问题。这大概可以有一个良好的动态编程代码到一个尺寸足够大，有没有点在读取输出完成。

这个问题的最有趣的版本是计数的解决方案。现有技术的状态总结于称为百科全书整数序列的。它已经计算多达N = 26。我猜想，也使用动态编程，但不像上市每一个解决方案的情况下，算法的问题是更深的，开放的进一步进展。

Answer 3

罗兰Pechtel说："现在，一些真正疯狂：29花了9秒钟。30几乎花了6分钟！"

这个迷人的缺乏可预测性回溯复杂性不同的板的尺寸是部分的这个难题，多数感兴趣我。多年来我一直在建设一个列表中的'计数'的算法的必要步骤，以找到 第一个解决方案 每个董事会的大小使用简单的和众所周知的深度-第一次算法，在递归C++的功能。

这里有一个列表中的所有那些计数'为委N=49... 减N=46和N=48仍在进行中的工作:

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

(我得到了那个中列出的百科全书的整数序列(工作，并)为 A140450)

该网页包括一个链接到一个列表中的匹配的第一个解决方案。

(我的名单 第一解决方案 是工作，并序列号 A141843)

我不主要记录多少时间处理每个解决方案的要求，而是我记录的失败女王-安置的需要之前发现每个委员会的算法-第一解决方案。当然率的王后位置上取决于CPU性，但给出一个快速测试在一个特定的CPU和一个特定的局大小，这是一个简单问题来计算多长时间来解决一些'发现'的解决方案。

例如，在英特尔奔腾D3.4GHz CPU，使用一个单一的CPU线

• N=35我的程序'放的24万皇后每秒只花了6分钟内找到第一解决方案。
• N=47我的程序'放'20.5万皇后每秒了199天了。

我当前的2.8GHz i7-860是颠簸通过关于28.6百万皇后每第二，试图找到这一解决方案N=48.到目前为止，它已经采取了超过550天(从理论上讲，如果它未曾中断)以未能成功地方1,369,331,731,000,000(和迅速的攀岩)的皇后。

我的网站没有(尚未)显示任何C++码,但是我给一个链接，该网页给我的简单的说明每一个15算法的必要步骤来解决N=5委员会。

这是个美味的难题。

Answer 4

其序言系统你们使用？例如，最近的版本SWI序言中，你可以容易地找到解决方案 N=80 和 N=100 在分一秒，使用原始代码。许多其他的序言体系将会更快。

N-皇后区的问题是，甚至刊登在一个网络的实例SWI言，可作为 CLP(FD)皇后区 在沙沙.

例 100皇后区:

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

嗖嗖声，也显示了你nices图像的解决方案。

这里是GIF动画显示出完整的解决方案的过程 N=40 王后与SWI序言:

Answer 5

至于什么是最大的N乘计算机解决有在文献中对于N约为3×10 ^ 6已使用冲突修复算法发现（即本地搜索）中的溶液的引用。参见例如经典论文[蓝宝石上硅集成电路和谷]。

至于确切与回溯解决，存在一些巧妙的分支启发式其中实现几乎没有回溯正确配置。这些启发式还可以用于找到第一-K 解决问题的方法：找到初始正确的配置搜索回溯到发现在附近的其他有效的配置后。

对于这些参考几乎完美启发式[芥兰90 ]和[圣Segundo的2011 ]

Answer 6

  

什么是针对其程序可以计算合理的时间量的答案的N的最大值？或者有什么是我们迄今见过的最大的N +

有任何限制。即，检查溶液的有效性大于构成一个溶液加七对对称那些更昂贵。

请参阅百科： “显式解用于放置上的n N皇后×n的板对所有的n≥4，不需要组合存在搜索任何。“。

Answer 7

余拖出所计数解的数目对于任何给定的电路板尺寸的老的Delphi程序，做了一个快速修改，使其一重击后停止和我看到的数据的奇数模式：

这接管1秒到解决的第一板为n = 20 21解决了62毫秒，虽然。 （注意：这是基于离现在，不是任何高精度系统）22用了10秒，不被重复，直到28

。

我不知道如何优化好是因为这本来是从后一个高度优化的程序时，优化的规则有很大不同。我做一件事比大多数实现很大的不同，虽然 - 它没有董事会。相反，我要跟踪的列和对角线进攻和增加每行一个女王。这意味着每测试的细胞3个阵列查找和根本没有乘法。 （正如我说，从当所述规则是非常不同的。）

现在对一些真正的精神错乱：29耗时9秒钟。 30了近6分钟！

Answer 8

其实约束随机游走（生成和测试）喜欢什么bakore概述是去，如果你只需要解决极少数，因为这些都可以快速产生的方式。我这样做是为了一个类时，我是20或21，并发表在Journal of帕斯卡，阿达＆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）的时间，也被蟒较慢语言任一项可以尝试在如C / C ++或Java等语言实现它。但是，即使与Python它将获得1或2秒内，n的第一个解决方案= 1000。