問題タブ [n-queens]

n-queen バックトラッカーについて勉強中です。other_row_pos誰かが対角線をチェックする方法を説明できますか? なぜそれが機能するのか、どのように機能するのかわかりません。

ウィキブックから取得 - http://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens :

上記のコードは、バックトラッキングを使用して N クイーンの問題を解決するためのものです。2 つの行の最初の 2 つのクイーンをそれぞれの列に配置できると思います。3 番目の行のクイーンになると、クイーンが攻撃する必要がないため配置できません。アルゴリズム N のクイーンから単純に終了します...では、このアルゴリズムはどのようにバックトラッキングを実装しているのでしょうか?

古典的な N-Queens 問題の助けが必要です。

プログラムを実行するコマンドは次のようになります: nqueens N k - ここで、N はテーブルのサイズ (N x N)、k は解の数です。

たとえば、nqueens 4 1と入力してプログラムを実行すると、次のように出力されます。

_ Q _ _

_ _ _ Q

Q _ _ _

_ _ Q _

ただし、複数のソリューションを処理する方法がわかりませんか? この問題の複数の解決策を特定するにはどうすればよいですか?

私がこれまでに持っているものは以下の通りです：

バックトラッキングを使用して n クイーン問題をシミュレートしたい。以下のような引数としてリストを使用して、毎回この drawboard() 関数を呼び出しています

このリスト 'x' は再帰プロシージャから返されるため、各反復後に更新されます

したがって、毎回別のウィンドウに表示されます。次のウィンドウは、最初のウィンドウを閉じた後にのみ表示されます...

単一のウィンドウで物事を作成するにはどうすればよいですか、または特定の時間間隔の後にこれらのウィンドウを自動的に閉じて、これらのウィンドウが 1 つずつ表示されるようにするにはどうすればよいですか

チェス盤を描く私の機能は次のとおりです

再帰とバックトラッキングを使用して N-Queens 問題の 1 つの解決策を見つける方法を作成しました。ここでやりたいことは、このメソッドを変更して、考えられるすべてのソリューションを見つけられるようにすることです。すべての解を格納するために 2D 整数配列を使用し、解が見つかるたびにインクリメントするカウンターを追加する必要があると仮定します。しかし、解決策を見つけたらこの方法を継続し、他のすべての可能な解決策を見つけるためにバックトラックを続ける方法について頭を悩ませているようには思えません。私がしなければならないことは、「return true;」を取り除くことだと思います。解決策が見つかったときに発生しますが、解決策が見つかったかどうかをメソッドに再帰的に判断させる方法がわかりません....これが私が今持っている1つの解決策のバージョンです:

編集：方法を修正しました。結果は以下のとおりです。まだ面倒かもしれませんが、うまくいきます！見つかった各ソリューションを出力する代わりに、配列に追加しました。私がまだqueen[]変数を持っている理由は、ソリューション配列をボードの状態から独立させることができるようにするためです。そして、私がまだ board[][] 変数を持っている理由は、underAttack() メソッドを (特に勾配の計算で) 書くのがずっと簡単になるからです.... とにかく、皆さんの助けに本当に感謝しています!

n-queens 問題をスキームで解決しようとしています。私は教授から、ベクトルの i 番目の要素がボードの i 番目の列を表す単一のベクトルをチェス盤として使用するように言われました。その要素の値は、クイーンが置かれている行、または列が空の場合は -1 です。したがって、[0 1 2 -1 -1] には、クイーンのない 2 つの列と、不​​正に配置された 3 つのクイーンがあります。このコードを実行すると: (place-n-queens 0 4 #(-1 -1 -1 -1)) #(0 1 2 3) が得られます。明らかに 4 つのクイーンすべてが不正に配置されています。問題は、place-queen-on-n の cond で十分なものをチェックしていないことだと思いますが、同じ対角線上にクイーンを配置するという問題を解決するために何を追加すればよいかわかりません。

これを機能させるために、どんな助けでも大歓迎です!!

N-queens 計算用の単純な C プログラムがあります。OpenMPで並列化しました。ここで、シリアル バージョンとパラレル バージョンの両方を実行し、速度アップを計算します。ポイントは、シリアル コード用の新しいファイルを作成したくない、または OpenMP ディレクティブを使用せずにソリューションを新しい関数にコピーしたくないということです。私がやりたいことは、1 つの関数を保持し、それをいつシリアルとして実行し、いつ並列として実行するかをメインから伝えることです。私はプリプロセッサを使用することを考えていますが、それが可能かどうかは確信しています。可能であれば、どうすれば実現できますか。