問題タブ [n-queens]

動的計画法を使用して 8-queen 問題を実装するという考えにかなり混乱しています。問題が一連の部分問題に分割され、各部分問題の最適解が見つかった場合、結果として得られる解は、これらの部分問題の解によって実現されます。この構造を持たないものは、動的計画法では解くことができません」(リファレンス)。これを考慮すると、7x7 ボードの最適なソリューションは、8x8 ボードには最適ではない (正しくない) 場合もあります。そのため、サブ問題の最適解によって問題の結果が実現しない場合があります。

一方、DP はバックトラッキング問題の最適化です... もしそうなら、8-queen 問題はバックトラッキングで解決できます... 行き止まりだけを保存することで、バックトラッキング解を DP に変換できるということですか? その場合、2,1 は親 1,1 には実行可能ではありませんが、1,2 には実行可能である可能性があります。

アップデート

動的計画法を使用して 8-queen または n-queen の問題を解決できるかどうか、誰もが考えていますか? もしそうなら、上記の観察に対するあなたのコメントは何ですか?

タスクは、N個のクイーンをNxNボードに配置するソリューションの数を数えることです。パフォーマンスを向上させるために考えられるすべてのケースを考えようとしましたが、N=15で実行するにはほぼ50秒かかります。これが私が行ったことです。

可能かどうか教えてください（私の先生は正確な時間を教えてくれなかったので、「許容時間」とだけ言っています。可能であれば、方法を教えてください。または、手がかりを教えてください。

n-Queen問題のすべての可能な解決策に対してアルゴリズムを実装すると、多くのブランチで同じ解決策に到達することがわかりました。n-Queens問題に対するすべてのユニークなソリューションを生成する良い方法はありますか？異なるブランチ（保存と比較を除く）によって生成された重複ソリューションを回避するにはどうすればよいですか？

これが私が最初の解決策として試したことです： http ：//www.ideone.com/hDpr3

コード：

考えられるすべてのソリューションを生成するために、同じコードnqdfs_all ()関数を使用しましたが、コントロールを親に返さず、代わりに列挙とチェックを続けました。この関数を呼び出すと、さまざまなブランチが到達した重複した結果が表示されます。

http://www.apl.jhu.edu/~hall/java/NQueens.javaで入手可能な実装を実行しました。 これは、O（n）時間計算量のN-queen問題を解決します。それは驚くほど高速で、検索せずに1つの解決策を見つけるのに役立ちます。ただし、背後にあるロジックについてはよくわかりません。なぜ彼らは問題を3に分割するのですか？奇数、偶数（ただし、フォーム6kではない）、偶数（ただし、フォーム6k + 2ではない）。誰かがコードをチェックして、私のためにもっと詳細に説明できますか（ロジックのみ）？

N-クイーンの問題に取り組んでいます。スタックを正しく埋めるのが難しい。誰かが私にどんな指針も与えてくれることを望んでいました。

現在、私の出力は奇妙です。ノードは7つしかありませんが、「成功」ブール値が真になるには8が必要です。そして、列を増やすので、ヘッドノードは1.2になるはずだと思ったときは2,1です。

対角線もチェックする必要があることはわかっていますが、段階的に進めています。

私のconflictCheckメソッドの場合、最初に解決する必要があります。trueを返すことはありません（はい、競合があります）。何かわかったらすぐに更新します。

編集：

より再帰的な試みのために、コードにいくつかの変更を加えました。私の新しい出力はこれです：

これは進行中のコード/作業の一部です。現在、それは永遠のループに陥っています。おそらくそれから（conflictCheck）

}

私は n-queens 問題に取り組んでおり、これまでのことをテストして、私の論理が正しいかどうかを確認しています。競合がないように2番目のクイーンピースを調整した後、私のループ停止は出力を停止し、無限ループに入ります。

私のロジックで無限ループが発生するとは思いませんでした。これは基本的に次のとおりです。 Push (1,1)

競合をチェックする

競合する場合はトップ クイーンを調整し、調整できない場合はポップオフし、新しいトップを調整します

競合がなく、サイズが 8 未満の場合は、(size+1, 1) をプッシュします。これは明らかに競合です。

競合などのチェック

}

私の出力は次のとおりです。

私はJavaでいくつかのプログラミング演習を解いていました。N Queensのエクササイズで私の心が少し凍るまで、すべてが完璧でした.

バックトラッキングを使用して、N クイーン問題の解決策を実装しました。すべてのクイーンの位置が安全かどうかを、左上、右上、上を確認してから列に配置することで確認しています。そうでない場合はバックトラックします。

4 や 8 などの N の一部の値については正しい解を示していますが、6 などの他の値については正しくありません。

何が欠けているのかわからない。どんな助けでも大歓迎です。

コードは次のとおりです。

I'm having trouble understanding backtracking, I can conceptually understand that we make a move, then if no solutions can be found out of it we try the next solution.

With this in mind I'm trying to solve the N Queens problem, I'm finding out all the possible candidates that can be placed in the next row and then trying them one by one, if a candidate doesn't yield a solution, I pop it off and go with the next one.

This is core of the code that I have come up with :

It doesn't print anything for any input that I give it. I tried running it through gdb but with no success, I think that is because there is a problem with my fundamental understanding of backtracking.

I have read up about backtracking in a couple of books and also an online tutorial and I still feel hazy, it'd be nice if someone could give me ideas to approach this and help me understand this slightly unintuitive concept.

The entire compilable source code is :