24

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

これは、列 1 の行 2、列 2 の行 4、列 2 の行 1、行 3 の列 4 に 4 つのクイーンを配置することを意味します (4 x 4 のチェス盤で)。

次に、このプログラムがどのように実行されるかを見てみましょう (最初の順列の計算にかかる時間):
N=4,5.....10 の場合 1 秒以内に計算
N=11-30 の場合 -1-3 秒かかります
N=40 の場合..50 それでも1分以内に計算
N=60で グローバルスタックから抜けます(探索空間が膨大)。

これは過去の宿題の問題でした。(元の問題は、N-Queen をコーディングすることだけでした)

また、他の言語での代替実装 (私の実装よりもパフォーマンスが高い) を見ることにも興味があります。または、アルゴリズム/プログラムに改善の余地があるかどうか

4

9 に答える 9

12

この議論は、3 つの異なる計算問題を混同しています: (1) N クイーン問題の解を見つけること、(2) 固定された N のすべての解をリストすること、(3) 固定された N のすべての解を数えること。最初の問題はトリッキーに見えます最初は、N=8 のようなボードのサイズです。ただし、ウィキペディアが示唆しているように、いくつかの重要な点で、N が大きい場合は簡単です。大きなボード上のクイーンは、それほどコミュニケーションを取りません。メモリの制約を除いて、ヒューリスティック修復アルゴリズムは、N が増加するにつれてますます簡単になります。

すべてのソリューションをリストすることは別の問題です。これはおそらく、出力を読み取っても意味がないほど十分に大きいサイズまでの優れた動的プログラミング コードを使用して実行できます。

この質問の最も興味深いバージョンは、解を数えることです。最新技術は、The Encyclopedia of Integer Sequencesとして知られる素晴らしいリファレンスにまとめられています。N=26まで計算されています。それも動的計画法を使用していると思いますが、すべてのソリューションをリストする場合とは異なり、アルゴリズムの問​​題ははるかに深く、さらに進歩する可能性があります。

于 2009-12-08T00:40:42.460 に答える
10

Loren Pechtel は次のように述べています。

さまざまなボード サイズのバックトラックの複雑さにおけるこの魅力的な予測可能性の欠如は、このパズルの中で私が最も興味を持った部分でした。何年もの間、再帰的な C++ 関数で単純でよく知られている深さ優先アルゴリズムを使用して、各ボード サイズの最初の解を見つけるために必要なアルゴリズム ステップの「カウント」のリストを作成してきました。

以下は、N=49 までのボードのすべての「カウント」のリストです ... N=46 と N=48 を引いたもので、まだ作業中です:

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

(Encyclopedia of Integer Sequences (OEIS) にA140450としてリストされています)

そのページには、一致する最初のソリューションのリストへのリンクが含まれています。

(最初のソリューションのリストは OEIS シーケンス番号A141843 です)

各ソリューションに必要な処理時間を主に記録するのではなく、各ボードのアルゴリズム優先のソリューションを発見する前に、失敗したクイーンの配置がいくつ必要だったかを記録します。もちろん、クイーンの配置率は CPU のパフォーマンスに依存しますが、特定の CPU と特定のボード サイズで簡単にテストを実行すると、これらの「見つかった」ソリューションの 1 つを解決するのにかかった時間を簡単に計算できます。

たとえば、Intel Pentium D 3.4GHz CPU では、単一の CPU スレッドを使用します -

  • N=35 の場合、私のプログラムは毎秒 2,400 万個のクイーンを「配置」し、最初の解を見つけるのにわずか 6 分しかかかりませんでした。
  • N=47 の場合、私のプログラムは毎秒 2050 万個のクイーンを「配置」し、199 日かかりました。

私の現在の 2.8GHz i7-860 は、N=48 の最初の解を見つけようとして、毎秒約 2860 万個のクイーンをスラッシングしています。これまでのところ、1,369,331,731,000,000 個の (そして急速に上昇している) 女王の配置に成功するのに、550 日以上 (理論上、途切れることがなければ) かかりました。

私の Web サイトには (まだ) C++ コードは表示されていませんが、その Web ページに、N=5 ボードを解くために必要な 15 のアルゴリズム ステップのそれぞれの簡単な図へのリンクを掲載しています。

それは確かにおいしいパズルです！

于 2010-08-21T19:48:05.393 に答える
5

どの Prolog システムを使用していますか? たとえば、SWI-Prolog の最近のバージョンでは、元のコードを使用して、 N=80とN=100の解を数分の 1 秒以内で簡単に見つけることができます。他の多くの Prolog システムは、それよりもはるかに高速です。

N クイーン問題は、SWISH でCLP(FD) クイーンとして利用できる SWI-Prolog のオンライン例の 1 つでも取り上げられています。

100 個のクイーンの例:

?- time((n_queens(100, Qs), labeling([ff], Qs)))。
Qs = [1, 3, 5, 57, 59 | ...] .
2,984,158 の推論、0.299 秒で0.299 CPU (100% CPU、9964202 リップ)

SWISH はソリューションの素敵なイメージも表示します。

これは、 SWI-Prolog を使用したN=40のクイーンの完全なソリューション プロセスを示すアニメーション GIF です。

40 クイーンの CLP(FD) ソリューション プロセス

于 2011-01-14T08:18:51.057 に答える
4

pycon で raymond hettinger によって提示された短い解決策: 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!))

于 2009-12-07T23:12:18.907 に答える
1

任意のボードサイズのソリューションの数をカウントする古いDelphiプログラムをドラッグし、1回のヒット後に停止するようにすばやく変更しましたが、データに奇妙なパターンが表示されています。

解決に1秒以上かかった最初のボードはn=20でした。ただし、21は62ミリ秒で解決されました。（注：これはNowに基づいており、高精度システムではありません。）22は10秒かかり、28まで繰り返されませんでした。

最適化のルールが非常に異なっていたとき、これは元々高度に最適化されたルーチンだったので、最適化がどれほど優れているかはわかりません。ただし、ほとんどの実装とは非常に異なることを1つ行いました。それは、ボードがないことです。むしろ、どの列と対角線が攻撃されているかを追跡し、行ごとに1つのクイーンを追加しています。これは、テストされたセルごとに3つの配列ルックアップがあり、乗算がまったくないことを意味します。（私が言ったように、ルールが非常に異なっていたときから。）

今、いくつかの本当の狂気のために：29は9秒かかりました。30はほぼ6分かかりました！

于 2009-12-07T23:38:10.493 に答える
1

バコレが概説したような実際に制約されたランダム ウォーク (生成とテスト) は、短時間で生成できるため、ほんの一握りのソリューションが必要な場合に使用する方法です。私は 20 歳か 21 歳のときにクラスでこれを行い、1987 年 3 月の Journal of Pascal, Ada & Modula-2、「The Queens Problem Revisited」で解決策を公開しました。今日、その記事のコードをちりばめたところです (これは非常に非効率的なコードです)。いくつかの問題を修正した後、N=26 ... N=60 のソリューションが生成されました。

于 2011-01-14T03:17:54.797 に答える