algorithm - N-Queens アルゴリズムのバリアント

Question

この問題が研究されているかどうかはわかりませんが、一般的な N-Queens 問題を試しているときに思い浮かびました。チェス盤を考えると、N*N必要なクイーンの最小数は何ですか。戦略的に配置すると、すべてのセルが少なくとも 1 つのクイーンによって攻撃されます。

ペンと紙でN= 3,4,5 を試してみたところ、2,3,4 でした。答えはいつもN-1ですか？その証拠はありますか？次に、その構成を印刷する方法 (複数の構成が可能な場合は、すべてを印刷します)。

Answer 1

この問題は研究されており、クイーンがxグリッドをkカバーする最小数は支配数として知られています。nn

k最初のものnは

1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9

OEISによって与えられたように。これは、8x8ボードの場合、5つのクイーンで十分であることを意味します。

n=4m+1（5,9,13 ...など）を満たすすべてのnについては、2m+1女王で十分であると推測されています。これとはるかに高度なアルゴリズムは、MatthewD.KearseとPeterB.Gibbonsの「チェス盤問題の計算方法と新しい結果」に示されています。

Answer 2

これは N-2 ではありません。11x11 のグリッドでは最大で 8 個のクイーンが必要になるためです (おそらくそれよりも少なくなります。これは私が手で見つけた単なる例です)。