11

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

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

4

2 に答える 2

7

このリンクは、「よく知られている」明示的なソリューションを引用しています。線形時間で計算できます。

http://www.chegg.com/homework-help/questions-and-answers/poor-man-sn-queens-problemn-queens-arranged-nxn-chessboard-way-queen-checks-queen-queen-q1009394

  1. n は偶数ですが、形式 (n mod 6 = 2) ではありません。m = 1, 2, の場合、正方形 (m, 2m) と (n/2 +m, 2m-1) にクイーンを配置します。. . 、n/2

  2. n は偶数ですが、(n mod 6 = 0) の形式ではなく、正方形 (m, 1+(2(m-1)+ n/2 - 1)mod n) および (n+1-m) にクイーンを配置します。 , n-(2(m-1)+n/2 -1)mod n) for m = 1,2,...,n/2

  3. n は奇数です。(1) または (2) のいずれか適切な方を n - 1 に使用し、(n,n) のクイーンで拡張します。

すべてのソリューションを列挙すると、はるかに時間がかかることに注意してください。ソリューションの数は、ボードのサイズ ( http://oeis.org/A000170 ) に応じて超指数関数的に増加するため、時間が経ってもそれらを列挙することは不可能です2^O(x)(ただし、O(n)スペースのみが必要です)。

于 2012-10-28T14:17:07.883 に答える
1

1 つの解を見つけるということですか、それともすべての解を見つけるということですか? ウィキペディアによると、解決策を 1 つだけ見つけたい場合は、簡単に実行できます。

n × n ボードに n 個のクイーンを配置するための明示的なソリューションが存在し、組み合わせ検索はまったく必要ありません。

于 2012-10-28T14:05:39.887 に答える