問題タブ [n-queens]

N クイーン問題:

この問題は、サイズが N × N のチェス盤が与えられたときに、互いに脅威を与えずに N 個のクイーンを盤上に配置できるさまざまな順列を見つけることを示しています。

私の質問は次のとおりです。
プログラムが妥当な時間内に答えを計算できる N の最大値は何ですか? または、これまでに見た最大の N は?

CLPFD(Prolog)での私のプログラムは次のとおりです。

このプログラムは問題なく動作しますが、所要時間は N とともに増加し続けます。実行例を次に示します。

これは、列 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 をコーディングすることだけでした)

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

How to Design Programs の拡張演習 28.2 で行き詰まっています。リストを使用する代わりに、真または偽の値のベクトルを使用してボードを表現しました。これは私が持っているもので、動作しません:

8-queensの良い/簡潔なアルゴリズムの例を知っている人はいますか? Web 検索を行いましたが、適切な例が見つかりませんでした。

main.m

sol.m

バック.m

クイーンが互いに攻撃しないように、n x n のボードに n クイーンを配置できる最大数を見つけようとしています。上記のmatlabコードの問題を理解できません.javaでこのロジックをテストしたので、ロジックの問題ではないかと思います.そこでは完全にうまく機能しているようです. コードはコンパイルされますが、生成される結果が間違っているという問題があります。

動作するJavaコード：

私は、列ごとに1つのクイーンしか存在できないという条件でN-クイーンの問題を解決しました。だから私は最初の列の正方形に女王を置き、次に次の列に移動して、船上の女王に攻撃されていない正方形に女王を置きます。このアプローチですべての解決策を見つけることができますが、n=13から長い時間がかかり始めます。また、問題の解決策のほとんどは、ごく少数の異なる解決策の回転と反射によって見つけることができることがわかりました。たとえば、8クイーン問題には合計92の解決策があり、そのうち12のみが明確です。（http://en.wikipedia.org/wiki/Eight_queens_puzzle）

だから私の質問は、ボードのこれらの状態をチェックし、明確な解決策を与えるスタックにそれらの状態のみをプッシュするにはどうすればよいですか？

これが私が今していることです。

私の宿題の 1 つは、ボードを表す 2 次元配列を使用してエイト クイーン問題を解くことです。次の場所にある「isUnderAttack」メソッドで、範囲外のインデックス エラー:8 が発生し続けます。

そして、私の「placeQueen」メソッドで：

と

どこで間違ったのでしょうか？この投稿にもっとタグを追加したかったのですが、私は新しいユーザーであり、「新しいタグ」を作成できません。ごめん！

ここに私が作成したものがあります：

これは宿題の質問です。n-QueensJavaの古典的な問題の解決策を書いています。私のプログラムは次のようになりますが、それらを出力する代わりに、すべての正当なクイーン配置のコレクションを返します。クイーンの配置を として表し、その実装として使用してint[]返します。(配置の順序は重要ではないため、ここでは適切です)。Set<int[]>HashSet<int[]>Set

問題は、Java 配列がオーバーライドhashCodeされず、同じ値を持つ異なる配列インスタンスが異なるハッシュ コードを持つことです。

QueensPlacements配列を保持し、でオーバーライドhashCodeするArrays.deepHashCodeラッパークラスを記述できますSet<QueensPlacement>。ただし、冗長でエレガントではないようです。誰でもより良い解決策を提案できますか?

Pythonでnqueenの問題を解決しました。この解は、nXn のチェス盤に n 個のクイーンを配置する解の総数を出力しますが、n=15 で試してみると、答えを得るのに 1 時間以上かかります。誰でもコードを見て、このプログラムを高速化するためのヒントを教えてもらえますか...初心者のpythonプログラマー。

山登りアルゴリズムとビーム探索アルゴリズムを使用して、nqueens パズル用に Prolog で 2 つのプログラムを作成しました。

残念ながら、プログラムが正しいかどうかを確認する経験がなく、行き詰まっています。

誰かが私を助けてくれれば幸いです。残念ながら、ヒル クライミングのプログラムは正しくありません。:( ビームサーチのプログラムは次のとおりです。

8/4 クイーンの問題を実装するにはどうすればよいですか?DFS/BFS を使用する必要がありますか?DF の方が優れていると思います。誰でもいくつかの疑似コード/ガイドラインを与えることができますか?