解决 N 皇后问题……我们能走多远? [英] Solving N-Queens Problem... How far can we go?

问题描述

N皇后问题:

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

This problem states that given a chess board of size N by N, find the different permutations in which N queens can be placed on the board without any one threatening each other.

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

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

Here is my program in 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 的增加而不断增加.这是一个示例执行:

This program works just fine, but the the time it takes keeps on increasing with N. Here is a sample execution:

?- 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 棋盘中)

This means you place the 4 queens at Row 2 in Column1, Row 4 in Column 2, Row 1 in 3 and Row 3 in 4.(In a 4 By 4 chess board)

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

Now lets see how this program performs(Time taken in calculating the first permutation):
For N=4,5.....10 Computes within a second
For N=11-30 Takes between -1-3 seconds
For N=40..50 Still calculates within a minute
At N=60 It goes out of Global stack(Search space being enormous).

这是过去的家庭作业问题.(最初的问题只是编码 N-Queens)

This was a past Homework problem. (The original problem was just to code N-Queens)

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

推荐答案

raymond hettinger 在 pycon 上提出的简短解决方案:python 中的简单人工智能

a short solution presented by raymond hettinger at 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!))

computing all permutations is not scalable, though (O(n!))

这篇关于解决 N 皇后问题……我们能走多远?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！