algorithm - バックトラックなしの nqueen

Question

n クイーン問題は後戻りせずに解決できますか?

n クイーンの問題に対する多くの種類の回答に遭遇しましたが、それらはすべて後戻りが必要です。後戻りせずに解決する方法はありますか？

Answer 1

はい。可能性のあるすべてのボードを生成してから、それぞれをテストすることで、総当たり攻撃を行うことができます。

ただし、このアプローチはうまく拡張できません;)

ウィキペディアの記事には、「反復修復」を含む多くの解決策がリストされていることにも注意してください。

Answer 2

最良の解決策を進化させる遺伝的アルゴリズムはバックトラックを必要としませんが、それはあなたの質問が暗示しているように見える状態空間グラフをトラバースするアルゴリズムとは異なる問題へのアプローチ方法です

Answer 3

はい。ウィキペディアでは、決定要因に基づいたものを含め、いくつか言及しています (私は今興味がありますが、追跡していません)。一言一句コピペさせてください：

上記の例は、次の式で取得できます。(i, j) を n × n チェス盤の列 i、行 j の正方形、k を整数とします。

1. n が偶数で n ≠ 6k + 2 の場合、i = 1,2,...,n/2 に対して (i, 2i) および (n/2 + i, 2i - 1) にクイーンを配置します。
2. n が偶数で n ≠ 6k の場合、クイーンを (i, 1 + (2i + n/2 - 3 (mod n))) および (n + 1 - i, n - (2i + n/2 - 3) に配置します。 (mod n))) for i = 1,2,...,n/2.
3. n が奇数の場合、(n - 1) に対して上記のパターンのいずれかを使用し、(n, n) にクイーンを追加します。