解决N-Queens问题......我们能走多远？

Question

N-Queens问题:

这个问题表明,给定一个大小为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行,第3行的第1行和第4行的第3行(在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 said: "Now for some real insanity: 29 took 9 seconds. 30 took almost 6 minutes!"

This fascinating lack of predictability in backtrack-complexity for different board sizes was the part of this puzzle that most interested me. For years I've been building a list of the 'counts' of algorithm steps needed to find the first solution for each board size - using the simple and well known depth-first algorithm, in a recursive C++ function.

Here's a list of all those 'counts' for boards up to N=49 ... minus N=46 and N=48 which are still work-in-progress:

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

(我已经在整数序列百科全书(OEIS)中列为A140450)

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

(我的First Solutions列表是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

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

Answer 4

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

N-queens问题甚至出现在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个皇后的完整解决方案过程: