解决 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

这意味着在一个4x4的棋盘上，将4个皇后放置在第2行第1列，第4行第2列，第1行第3列和第3行第4列。（即解决N皇后问题）

现在让我们看看该程序的性能（计算第一个排列所需的时间）： 对于N=4,5....10，在一秒钟内计算完成。 对于N=11-30，需要花费1-3秒钟。 对于N=40..50，仍然可以在一分钟内计算完成。 当N=60时，它会超出全局堆栈（搜索空间巨大）。

这是以前的一个作业问题。（原始问题只是编码N皇后问题）

我还想看看其他语言中的替代实现（比我的实现效果更好），或者是否有改进算法/程序的空间。

- user220751

---

维基百科有很多算法，其中至少有一个可以在约50个步骤内解决100万皇后问题。http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design - Carl Norum

我对Prolog的了解很少，而且是很久以前的事了。但我记得，尽管Prolog是一种规范性语言而不是命令式语言，但可以通过有序地设置规则等方式来引导处理过程朝着首选和希望更好的性能方向推进。虽然我不太懂，但我猜测你的解决方案可以通过这种方式进行优化，以实现更好的性能。 - Carl Smotricz

好的，50步实现并不像你的算法一样进行完整的深度优先搜索。如果你阅读文章，你会得到更多信息。特别是，它需要一个“合理好”的初始设置。 - Carl Norum

http://www.math.utah.edu/~alfeld/queens/queens.html展示了我们正在处理的实际复杂性。随着N的增加，请查看所涉及的步骤数量。 - user220751

切割位置不正确，generate/2 中的事实也是错误的。 - false

Answer 1

这篇讨论混淆了三个不同的计算问题：（1）找到N皇后问题的解，（2）列出某个固定N的所有解，以及（3）计算某个固定N的所有解。对于一个像N = 8这样的棋盘大小，第一个问题看起来很棘手。然而，正如维基百科所建议的那样，在某些关键方面，当N很大时它变得更容易。在大棋盘上的皇后之间没有太多通信。除了内存限制，启发式修复算法随着N的增加会越来越容易。

列出每个解决方案是另一回事。这可能可以通过一个良好的动态编程代码完成，直到达到一个足够大的尺寸，没有阅读输出的意义。

最有趣的问题版本是计算解决方案。现有技术总结在一个名为整数序列百科全书的精彩参考资料中。已经计算到N = 26。我猜测这也使用了动态编程，但与列出每个解决方案的情况不同，算法问题更深入，并且有进一步的提高空间。

- Greg Kuperberg

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正在尝试通过约28.6百万个皇后每秒搜索N = 48的第一个解决方案。到目前为止，它已经花费了超过550天（理论上，如果从未被中断），以不成功地放置1,369,331,731,000,000（并迅速攀升）的皇后。

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

这确实是一个美味的谜题！

- CSPea

---

也许你对于N皇后问题的“几乎完美”启发式算法研究感兴趣？http://link.springer.com/article/10.1007%2Fs10898-011-9653-x - chesslover

你是在谈论寻找一个配置，还是计算所有可能的配置？ - Beni Bogosel

我已经开发了一段代码，可以获取任意数量皇后问题的第一个解决方案！ - abhimanyue

Answer 3

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

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

使用100个皇后的示例：

?- time((n_queens(100, Qs), labeling([ff], Qs))).
Qs = [1, 3, 5, 57, 59 | ...]。
2,984,158个推理，0.299 CPU 用时0.299秒（100％CPU，9964202 Lips）

SWISH还向您显示漂亮的解决方案图像。

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

- mat

---

完整的解决方案流程是什么？我认为它只显示了第一个解决方案的标记过程。 - false

Answer 4

Raymond Hettinger在PyCon上提出了一个简短的解决方案：Python中的简单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!))

- miku

---

非常短！执行时间有什么消息吗？ - Carl Smotricz

我不懂Python，但看起来你正在使用生成和测试策略。你只是生成一个排列，并检查它是否符合限制条件。但问题在于，即使对于像N = 60这样的小数字，排列的数量也是60！非常非常大的数字。 - user220751

是的，这个解决方案不太关注可扩展性，更多地是通过几行代码来解决经典的8x8问题。 - miku

但是你可以使用约束来减少搜索空间。例如，如果您放置了一个皇后，则划掉此皇后将杀死的位置，然后以类似的方式放置其他皇后。（就像我在我的程序中所做的那样）。无论如何，这是一个惊人的简短实现 :) - user220751

选择这个作为答案的原因是它接近我所问的问题。虽然我仍然渴望看到更好的实现。 - user220751

它非常简短，因为它包括排列类。我甚至可以写得更短，只需写：打印queens（12）。那将是惊人的 ;) - Milan Babuškov

Answer 5

关于计算机能解决的最大N值，文献中提到使用冲突修复算法（即局部搜索）已经找到了约为3*10^6的解。例如可以参见 [Sosic和Gu] 的经典论文。

关于采用回溯方法精确求解，存在一些巧妙的分支启发式方法，几乎不需要回溯即可获得正确的配置。这些启发式方法也可以用于查找该问题的前k个解：在找到初始正确的配置后，搜索会回溯以找到附近的其他有效配置。

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

- chesslover

---

不是完全无需回溯，但几乎可以做到。例如，在[San Segundo 2011]中，对于从4到1000的997个可能的N值中的992个情况，找到第一个有效配置不需要进行回溯。对于N=15，需要6次回溯，N=14需要8次回溯，而对于N={8,11,13}的值总共需要7次回溯。 - chesslover

是的，我也在提到第一个解决方案。分支启发式算法对于997个N值（N从4到1000）中的992个情况都非常完美（不需要回溯，这就回答了你的问题）。但是对于N={8, 11, 13, 14 , 15}，需要进行一些小的回溯。我不知道是否有任何分支启发式算法适用于所有N。 - chesslover

“对于所有n≥4的情况，放置n个皇后在一个n×n的棋盘上存在明确的解决方案，无需进行任何组合搜索”（http://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions）。因此：只需按顺序排列变量，第一次尝试即可得到解决方案。然而，如果这些变量受到额外约束，以排除该解决方案，则会导致非常糟糕的性能。 - false

正是出于这个原因，k > 1 的前k个解可能更为有趣。 - false

同意，但是你的问题与CONSTRUCTIVE算法的第一种解决方案有关。至于前k个解决方案（其中没有已知的闭合形式解决方案，正如你所指出的），San Segundo论文中也有有趣的信息。特别是对于k=100，大多数回溯只需约200次。对于较小的N值，它会增加到约1200次。 - chesslover

这不是更多关于“建设性”究竟意味着什么吗？对于每个显式的解，都存在一个平凡的建设性算法。 - false

Answer 6

程序在合理的时间内能计算出答案的最大N值是多少？或者我们迄今为止见过的最大N是多少？

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

参见维基百科： "对于所有n≥4，在n×n的棋盘上放置n个皇后的显式解决方案都存在，无需进行组合搜索。"。

- false

---

@SterlingVix：这是你的误解：一旦你能够构建出一个单一的解决方案，只需按照那个顺序对变量进行标记。因此，找到所有解决方案的相应方法非常接近。 - false

Answer 7

我找出了一个旧的 Delphi 程序，用于计算任何给定棋盘大小的解决方案数量，做了一个快速修改使其在一次命中后停止，并且我在数据中看到了一个奇怪的模式：

第一个需要超过 1 秒才能解决的棋盘是 n = 20。然而，21 在 62 毫秒内解决了。（注意：这是基于现在的时间，而不是任何高精度系统。）22 花费了 10 秒钟，直到 28 才再次出现。

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

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

- Loren Pechtel

---

实际上，这似乎并不是很有趣。这与您的遍历模式需要多少回溯才能到达第一个解有关。我敢打赌，如果他调整了遍历顺序，那些数字会再次改变。 - Mike

Answer 8

如果您只需要少量的解决方案，那么像bakore所概述的实际受限随机游走（生成和测试）是可行的方法，因为这些可以快速生成。我在20或21岁时为一个班级做了这件事，并在1987年3月的Pascal、Ada和Modula-2杂志上发表了《女王问题再访》的解决方案。今天我从那篇文章中整理出了代码（这是非常低效的代码），并且在修复了一些问题后已经生成了N=26...N=60的解决方案。

- Kirt Undercoffer

---

这是一个生成N=60解决方案的链接：http://www.kirtundercoffer.com/publications/q60-1.txt。这是一个60 x 60的文本文件，空白处（用1表示）和皇后（用9表示）之间没有空格。虽然我没有详尽地检查过这个结果，但根据以往所有结果，我有信心认为它是正确的。 - Kirt Undercoffer

这是一个N=80的解决方案：http://www.kirtundercoffer.com/publications/q80.txt，也是使用随机游走生成的。 - Kirt Undercoffer

我昨晚也生成了一个N=100皇后问题的解决方案 - 您可以在kirtundercoffer.com/publications/q100.txt上查看。这个解决方案也是使用随机漫步生成的 - 人们可以在网络上阅读并在讲座中听到，这种方法甚至无法为小N生成解决方案。但这是不正确的。当然，它不会生成所有的解决方案，但实际上，在N很大时，随机漫步方法甚至可能比回溯更可取，因为回溯将占用大量内存。 - Kirt Undercoffer

Answer 9

如果您只需要一种解决方案，那么可以使用贪心算法在线性时间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的第一个解决方案。

- Saket Detroja