問題タブ [n-queens]

ウィキペディアのエイト クイーン パズルの記事。ソリューションセクションの最後の行には、 「ソリューション 10 には、3 つのクイーンが直線上にないという追加のプロパティがあります」と記載されています。

でも、クイーンを一直線に並べないのが使命ではないでしょうか。なぜそれが解決策 #10 にとって特別なのか、すべての解決策がステートメントに従っていることがわかります。それで、私は何を見落としていますか？

幅優先探索を使用して8 クイーン パズルを解くプログラムを作成するように言われました。これは私がこれまでに持っているものです:

これを改善する方法はありますか？

私は 8 クイーン問題のバージョンを実行していますが、バックトラッキング法は使用していません。方法の 1 つは、「正方形にスコアを付ける」必要があります。基本的には、ボックスにクイーンが配置された場合に使用できなくなるセルの数を見つける必要があります。私の問題は、コードで正方形のスコアを返すことができないことです。私の for ループか何かに何か問題がありますか?

だから私はn-queens問題を解決しようとしています。私は有効なバックトラッキングの実装を持っていると思いますが、ボードが有効かどうかをチェックする方法がオフになっていると思います (非常に非効率的です) が、その理由はわかりません。誰でもその理由を理解できますか/より良い方法を提供できますか?

n クイーンの Python でプログラムに問題があります (nxn ボードに n クイーンを配置する方法はいくつありますか)。私の再帰に問題があるようですが、私は本当に無力です。誰かが何が悪いのか理解できますか？

n クイーン アルゴリズムとも呼ばれる8 クイーン パズルを解こうとしています。

私の関数は、NxN ボードに N 個のクイーンを配置する正当な方法がいくつあるかをカウントする必要があります。

私はほとんどそれを手に入れましたが、それを機能させるためにいくつかの醜いパッチを適用する必要がありました. 直してもらえますか？

私がしたことの簡単な説明: NxN テーブルに N 個のクイーンを設定する合法的な方法がいくつあるかを調べようとして、(N-1)xN ケースで再帰を使用して解決しようとしていました (最初の列を削除) 事実については同じ列に 2 つのクイーンを配置することはできません。リストの長さ N を使用します。各セルは列を表し、各列にはクイーンが設定されている行番号を設定します。

例えば、

という意味です：

• 列 0 – 行 0 に配置されたクイーン
• 列 1 – 行 4 に配置されたクイーン
• 列 2 – 行 7 に配置されたクイーン
• 列 3 – 行 5 に配置されたクイーン
• 列 4 – 行 2 に配置されたクイーン
• 列 5 – 行 6 に配置されたクイーン
• 列 6 – 行 1 に配置されたクイーン
• 列 7 – 行 3 に配置されたクイーン

私を悩ませているのは、違法なクイーンの配置を省略する方法がわからないことです. それを機能させるために、私は という名前のグローバル変数を使用し、sum再帰が合法である完全に配置されたクイーンの配置に達した場合にのみインクリメントします。

N = 8私が得る..したがって、sum = 92それが機能することはわかっていますが、このグローバルカウンターは避けたいです。

手伝ってくれますか？

プロローグの8クイーン問題を解いています。私はプロローグの初心者です。解決策のリストを印刷したいのですが、クエリが毎回失敗します...誰でも助けてくれますか???

ここに私のプロローグコードがあります

min-conflicts アルゴリズムについて助けてください。

この時点で、

• アルゴリズムはどちらか一方を移動するためにランダムCに選択するか、またはD両方が同じ数の競合を作成するため (Cと競合しているD、Dと競合しているC)、
• それともD、移動できる最適な場所Cが 3 列目であり、1 つの競合が発生し、選択Dして 3 列目に移動すると競合が 0 になるため、選択しますか。

時間の複雑さがあると思います：O（n ^ n）、NQueen関数は再帰的に呼び出しているため、このプログラムにはより厳しい制限がありますか？最良の場合と最悪の場合の時間の複雑さはどうですか。また、O(k) である place() 関数と NQueen() からの呼び出しについても混乱しています。