解决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的增加而增加。 b这是一个示例执行：

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行，第3列第1行和第4列第3行（在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的seconds

在一分钟内仍会计算

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

我也有兴趣看到其他语言的替代实现（其性能比我的实现更好）或如果我的算法/程序中还有改进的余地

推荐答案

raycon 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屋！