問題タブ [n-queens]

このコードを実行すると、ほとんどの場合、端末がハングしますが、ときどき、必要なソリューションが出力されます。これが女王のパズルを解く最良の方法ではないことはわかっているので、コメントしないでください. 時間を割いて助けてくれた人に感謝します。

私はC＃でいくつかのコーディングを開始し、わずかな変更でn-queenの問題を試しました（queenにはknightの力もあります）。制限の後、関数を何度も呼び出すため、stackoverflowの問題が表示され始めます。

誰でも私が直面している問題を理解するのを手伝ってくれませんか.以下はn-queensの問題のコードです.

1. ここqueenPosition（関数によって返される）は、クイーンが配置されている列番号を持つ配列です。4-queen のようqueenPosition に (2->0->3->1) になります。4x4 チェス盤の位置。

2. CheckValid関数は、位置が適切かどうかを検証します。

3. 私が気付いていない概念がいくつかあり、メモリが無駄になっています。

NQueen 問題はバックトラッキングの有名な例です。ソースから読んだ後、以下のコードスニペットを試しました。

私は次のように出力を得ています：

ただし、バックトラックするステートメントにコメントすると、問題なく同じ出力が得られます。

NQueenの問題、バックトラッキングの問題を引き起こしたのは正確には何ですか?

単純な再帰的アプローチではありませんか？

最終的には名簿ソリューションを形作る必要があるため、よだれプランナーをいじっています。Drools Planner ユーザー ガイドから始めて、Eclipse でサンプルを実行することに成功しました。

シンプル スコア タイプと HardAndSoft スコア タイプの違いを理解しようとして、スコアを Simple から HardAndSoft に変更して、NQueens の例を変更しようとしています。

私は次のようにしました：

1. nqueensSolverConfig.xml で設定し<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>ます。

2. NQueens.java で:

   • 設定しましたpublic class NQueens extends AbstractPersistable implements Solution<HardAndSoftScore> {...}

   • SimpleScore 関連のプロパティとメソッドを対応する HardAndSoftScore メンバーに変更しました。

   プライベート HardAndSoftScore hsScore;

   public HardAndSoftScore getScore() { return hsScore; }

   public void setScore(HardAndSoftScore スコア) { this.hsScore = スコア; }

しかし、ソリューションを実行すると、次のメッセージが表示されます。

なにが問題ですか？

N-Queens パズルは理論的に多項式時間で解くことができますか? もしそうなら、それの最高の複雑さは何ですか? 多くのアルゴリズムを見つけましたが、時間の複雑さが正確に何であるかはわかりませんでした。その複雑さの正確な数を示している論文や文書はありますか?

(PS 明示的な解は非常に興味深いものですが、すべての解を見つけたいと言うのを忘れていました。)

この問題が研究されているかどうかはわかりませんが、一般的な N-Queens 問題を試しているときに思い浮かびました。チェス盤を考えると、N*N必要なクイーンの最小数は何ですか。戦略的に配置すると、すべてのセルが少なくとも 1 つのクイーンによって攻撃されます。

ペンと紙でN= 3,4,5 を試してみたところ、2,3,4 でした。答えはいつもN-1ですか？その証拠はありますか？次に、その構成を印刷する方法 (複数の構成が可能な場合は、すべてを印刷します)。

8x8 のチェス盤に 8 つのクイーンを配置するヒューリスティックを開発しています。各正方形には独自の除去数があり (空のチェス盤の正方形にクイーンが配置された場合に「除去される」正方形の数を示します)、各クイーンは最小の除去数を持つ正方形に配置する必要があります。

私の問題は、適切な正方形の特定の除去数を減らし続けるために何をすべきかわからないことです。別の問題、私のコードは非常に複雑だと感じているので、よりシンプルにするための注意事項はありますか?

これが私のコードです

}

私の主な方法は別のクラスです。

この重要なメソッドを備えたシングルスレッドの Python モジュール (n-Queen 問題を解決するため) があります。

9 などの定数値を指定すると、メソッドは正常に動作しますが、ランダム関数の選択を使用して、使用可能な (数値のリスト) から値を選択する場合、collision()メソッドは正しく動作しません。一部を逃すことによって。

これが役立つ場合の衝突方法は次のとおりです。

基本的に、チェスのマス「b」がクイーン「a」によって攻撃可能かどうかをチェックします

私は、phpで書かれたn-queens問題の1つの解決策を見つける基本的な力ずくの解決策を持っています。 これがデモです。n = 16で、サーバーはメモリ不足エラーのスローを開始します。

gitHubのソースコード。

より多くのクイーンのソリューションをページに表示できるようにするために、コードまたはアルゴリズムのいずれかを改善することをお勧めしますか？私はより良いコードを書く方法を学ぼうとしているので、プロセスの割り当てられたメモリを使ったモンキーは範囲外であると仮定します。

非常に高速な nqueens プログラムを作成するという課題があります。これまでのところ、ブルートフォース アルゴリズムとバックトラックは機能していますが、より高速と思われる C プログラムを見つけました。CからJavaに変換しようとしましたが、ポインターで何が起こっているのか理解していないため、ポインターを変換できません。変換する必要がある行は次のとおりです。

編集：私が理解しているものに変換を更新しました：

解決策があればいいのですが、ここで何が起こっているのか説明していただければ、自分で見つけようとします。ポインターは、私が実際に c と c++ を学んだことがない理由です。

よろしく、デニス・フィッシャー