エイトクイーンパズル

八女王パズルとは、 8×8のチェス盤に8個のチェスの女王を配置し、どの女王同士も互いに攻撃し合わないようにする問題です。つまり、どの女王も同じ行、列、または対角線上に配置されてはならないという条件が満たされます。解法は92通りあります。この問題は19世紀半ばに初めて提起されました。現代では、様々なコンピュータプログラミング技術の例としてよく用いられています。

8クイーンパズルは、n × nのチェス盤にn個の攻撃しないクイーンを配置するという、より一般的なnクイーン問題の特殊なケースです。n =2とn =3を除くすべての自然数nに対して解が存在します。解の正確な数はn≤27の場合のみ知られていますが、解の数の漸近的な増加率はおよそ次のようになります。${\displaystyle (0.143n)^{n}}$。

チェスの作曲家マックス・ベッツェルは1848年に8クイーンパズルを発表した。フランツ・ナウクは1850年に最初の解法を発表した。^{[ 1 ]}ナウクはまた、 n × nマスのチェス盤にn個のクイーンを配置するnクイーン問題にパズルを拡張した。

それ以来、カール・フリードリヒ・ガウスをはじめとする多くの数学者が、8クイーン問題とその一般化されたnクイーン問題の両方に取り組んできた。1874年、S.ギュンターは行列式を用いて解を求める方法を提案した。 ^{[ 1 ]} JWLグレイシャーはギュンターのアプローチを改良した。

1972年、エドガー・ダイクストラはこの問題を用いて、彼が構造化プログラミングと呼んだものの威力を実証した。彼は深さ優先バックトラッキングアルゴリズムの非常に詳細な説明を発表した。^{[ 2 ]}

8クイーン問題のすべての解を見つける問題は、8×8の盤上に8つのクイーンを配置できる組み合わせが4,426,165,368通りあるのに対し、解は92通りしかないため、計算コストが非常に高くなる可能性が^あります。計算要件を減らすショートカットや、総当たり計算手法を避ける経験則を使用することが可能です^。たとえば、各列から1つのクイーンを選択するという単純なルールを適用することで、可能な組み合わせの数を16,777,216通り（つまり8 ⁸）に減らすことができます。順列を生成すると、可能性はさらに40,320通り（つまり8!）に減り、その後、対角線攻撃をチェックすることができます。

8クイーンパズルには92通りの異なる解があります。盤面の回転と鏡映という対称操作のみが異なる解を1つと数えると、このパズルには12通りの解が存在します。これらは基本解と呼ばれ、それぞれの代表例を以下に示します。

基本解は通常、90°、180°、または270°回転させて、4つの回転した変形を固定位置の鏡でそれぞれ反射させることで得られる8つの変形（元の形を含む）を持ちます。しかし、12の基本解のうちの1つ（下記の解12）は、180°回転した解と同一であるため、4つの変形（自身とその反射、90°回転とその反射）しかありません。^{[ b ]} したがって、異なる解の総数は11×8 + 1×4 = 92です。

基本的な解決策はすべて以下に示します。

解法10には、3つのクイーンが一直線上に並ばないという追加の性質があります。

解の数を数える総当たりアルゴリズムは、計算上管理可能であり、${\displaystyle n=8}$しかし、問題に対しては扱いにくいだろう${\displaystyle n\geq 20}$20! = 2.433 × 10 ¹⁸となる。単一の解を見つけることが目的であれば、n ≥ 4 の場合、探索を一切行わずに解が存在することを示すことができる。^{[ 3 ] [ 4 ]}これらの解は、 n = 8、9、10 の 場合の次の例のように、階段状のパターンを示す。

上記の例は、次の式で得られます。^{[ 3 ]} ( i , j ) をn × nチェス盤のi列j行目のマス目とし、kを整数とします。

一つのアプローチ^{[ 3 ]}は

1. n を6 で割った余りが 2 または 3 でない場合、リストは単純にすべての偶数と、 nより大きくないすべての奇数が続きます。
2. そうでない場合は、偶数と奇数のリストを別々に作成してください（2、4、6、8 – 1、3、5、7）。
3. 余りが2の場合は、奇数リストの1と3を交換し、5を最後に移動します（3、1、7、5 ）。
4. 余りが3の場合は、2を偶数リストの末尾に、1と3を奇数リストの末尾に移動します（4、6、8、2 – 5、7、9、1、3 ）。
5. 奇数リストを偶数リストに追加し、左から右へ (a2、b4、c6、d8、e3、f1、g7、h5) の順に、これらの番号で示される行にクイーンを配置します。

n  =  8の場合、上記の基本解 1 が得られます。以下にいくつかの例を示します。

• 14 個のクイーン (残り 2 個): 2、4、6、8、10、12、14、3、1、7、9、11、13、5。
• 15 個のクイーン (残り 3 個): 4、6、8、10、12、14、2、5、7、9、11、13、15、1、3。
• 20 個のクイーン (残り 2 個): 2、4、6、8、10、12、14、16、18、20、3、1、7、9、11、13、15、17、19、5。

高次元

nサイズのd次元チェス空間に配置できる非攻撃クイーンの数を求めます。 n個を超えるクイーンは、いくつかの高次元で配置できます (最小の例は 3×3×3 チェス空間に 4 つの非攻撃クイーンを配置することです)。実際、任意のkに対して、 n ^k個のクイーンではすべての空間を攻撃するのに十分でない高次元が存在することが知られています。 ^{[ 10 ] [ 11 ]}

クイーン以外の駒を使用する

8×8 の盤上には、どの 2 つの駒も互いに攻撃し合わないように、ナイトを32 個、ビショップを14 個、キングを16 個、またはルークを8 個配置できます。ナイトの場合、反対の色にしか移動しないので、各色のマスに 1 つずつ配置すれば簡単に解決できます。ルークとキングの場合も簡単に解決できます。キング 16 個は、盤を 2×2 のマスに分割し、各マスの同じ位置に配置することで配置できます。n × n の盤上に n 個のルークを配置すると、n次置換行列に直接対応します。

チェスのバリエーション

将棋などのチェスのバリエーションについても、同様の問題が提起されることがある。例えば、n + kドラゴンキング問題では、 n × n の将棋盤上にk個の将棋の歩兵とn + k 個の互いに攻撃しないドラゴンキングを配置することが求められる。^{[ 12 ]}

非標準ボード

ポリアは、トーラス状（「ドーナツ型」）の盤面でnクイーン問題を研究し、 n × nの盤面で解が存在するのはnが2または3で割り切れない場合のみであることを示した。 ^{[ 13 ]}

支配

n × nの盤面が与えられた場合、支配数とは、すべてのマスを攻撃または占領するために必要なクイーン (またはその他の駒) の最小数です。n = 8 の場合、クイーンの支配数は 5 です。^{[ 14 ] [ 15 ]}

クイーンとその他の駒

バリエーションとしては、クイーンと他の駒を組み合わせる方法があります。例えば、n × nの盤上にm個のクイーンとm 個のナイトを配置して、どの駒も他の駒を攻撃しないようにする^{[ 16 ]}、あるいは、クイーンとポーンを配置して、2 つのクイーンが互いに攻撃しないようにする^{[ 17 ]などです。}

魔方陣

1992年、Demirörs、Rafraf、Tanikは、いくつかの魔方陣をnクイーン解に変換する方法、およびその逆の方法を発表した。^{[ 18 ]}

ラテン方陣

n × nの行列において、1 からnまでの各数字を、同じ行または列に同じ数字が2回出現しないように、行列内のn個の場所に配置します。

正確なカバー

盤面のn個のランクそれぞれに対応する主列、 n個のファイルそれぞれに対応する主列、および盤面の4 n − 6 個の非自明な対角線それぞれに対応する副列を持つ行列を考えます。この行列はn ²行を持ち、各行は可能なクイーンの配置ごとに 1 行ずつ、各行はそのマス目のランク、ファイル、および対角線に対応する列に 1 を持ち、その他のすべての列に 0 を持ちます。すると、nクイーン問題は、この行列の行のサブセットを選択することと同等になります。つまり、すべての主列は選択された行のうちちょうど 1 つに 1 を持ち、すべての副列は選択された行のうち多くても 1 つに 1 を持ちます。これは、一般化された完全カバー問題の一例であり、数独もその例です。

nクイーン完成

完全性問題とは、既にいくつかのクイーンが配置されているn × n のチェス盤において、残りのすべての行にクイーンを配置して、どの 2 つのクイーンも互いに攻撃し合わないようにすることが可能かどうかを問う問題である。この問題および関連する問題はNP 完全かつ#P 完全である。^{[ 19 ]}最大でn /60 個のクイーンの配置は完了可能であるが、約n /4 個のクイーンの部分的な配置は完了できない。^{[ 20 ]}

コスタス配列

非攻撃クイーンコスタス配列（NAQCA）とは、 nクイーン問題の解でもあるコスタス配列のことである。既知のNAQCAは自明な1×1の場合のみであり、他には存在しないと推測されている。^{[ 21 ]}

8クイーンパズルのすべての解を見つけることは、単純でありながらも自明ではない問題の良い例です。そのため、制約プログラミング、論理プログラミング、遺伝的アルゴリズムなどの非伝統的なアプローチを含む、さまざまなプログラミング手法の例題としてよく使用されます。最もよく使用されるのは、 n×nチェス盤にn - 1個のクイーンを配置する問題の任意の解に1個のクイーンを追加するという形でnクイーン問題を帰納的に表現することにより、再帰アルゴリズムで解決できる問題の例として使用されることです。帰納法は、チェス盤に0個のクイーンを配置するという「問題」の解、つまり空のチェス盤で終わります。このプロセスは、チェス盤の各列には必ず1個のクイーンが含まれているという観察を適用し、アルゴリズムがi番目のクイーンをチェス盤のi番目の行に追加しようとする位置を、すでに他のクイーンによって攻撃されていない列に制限することにより、より効率的になります。これらの選択により、試行する必要のある配置の数が大幅に削減され、アルゴリズムがすべてのソリューションを見つけることができます。${\displaystyle 8\times 8}$チェス盤を瞬時に見えるほどの短い時間で。^{[ 22 ]}

網羅的探索の代替手段として、「反復修復」アルゴリズムがあります。これは通常、すべてのクイーンが盤上に配置されている状態から開始します。たとえば、各列にクイーンが1つずつ配置されている状態です。^{[ 23 ]}次に、衝突（攻撃）の数を数え、ヒューリスティックを使用してクイーンの配置を改善する方法を決定します。「最小衝突」ヒューリスティック（衝突の数が最も多い駒を、同じ列内で衝突の数が最も少ないマスに移動させる）は特に効果的で、1,000,000個のクイーンの問題でも簡単に解を見つけることができます。^{[ 24 ] [ 25 ]}

前述のバックトラッキング探索とは異なり、反復修復は解を保証するものではありません。すべての貪欲法と同様に、局所最適解に陥る可能性があります。（そのような場合は、異なる初期設定でアルゴリズムを再開できます。）一方で、深さ優先探索の範囲をはるかに超える規模の問題を解決できます。

バックトラッキングの代替手段として、有効な部分解を再帰的に列挙することで、一度に 1 行ずつ解をカウントすることができます。盤面全体の配置を構築する代わりに、ブロックされた対角線と列はビット演算で追跡されます。これにより、個々の解を復元することはできません。^{[ 26 ] [ 27 ]}

以下のプログラムは、ニクラウス・ヴィルトの解法をPythonプログラミング言語に翻訳したものですが、元のプログラムにあるインデックス演算は行わず、代わりにリストを使用してプログラムコードをできるだけシンプルにしています。ジェネレータ関数の形式のコルーチンを使用することで、元のプログラムの2つのバージョンを統合して、1つまたはすべての解を計算できます。15,720通りの可能なクイーン配置のみが検討されています。^{[ 28 ] [ 29 ]}

def queens ( n : int , i : int , a : list , b : list , c : list ): if i < n : for j in range ( n ): if j not in a and i + j not in b and i - j not in c : yield from queens ( n , i + 1 , a + [ j ], b + [ i + j ], c + [ i - j ]) else : yield afor solution in queens ( 8 , 0 , [], [], []): print ( solution )

以下のプログラムは、ドナルド・クヌースが『コンピュータプログラミングの技法』第4B巻の31ページ、7.2.2節「バックトラックプログラミング」で説明した非公式な解決策をPythonプログラミング言語で実装したものです。^{[ 30 ]}

def property ( perm : list ) -> bool : for k in range ( 0 , len ( perm )): for j in range ( 0 , len ( perm )): if j < k : if perm [ k ] == perm [ j ]: return False elif abs ( perm [ k ] - perm [ j ]) == k - j : return False return Truedef extend ( perm : list , n : int ): new_perm = [ ] for p in perm : for i in range ( 0 , n ): new_perm.append ( p + [ i ] ) return new_permdef n_queens ( n : int ) -> int : domain = list ( range ( 0 , n )) perm = [[]] for i in range ( n ): new_perm = list ( filter ( property , extend ( perm , n ))) perm = new_perm return len ( perm )

• ゲーム『セブンス・ゲスト』では、スタウフ邸のゲームルームにある第8のパズル「女王のジレンマ」が、^事実上の8クイーンパズルである。^{[ 31 ]： 48-49、289-290}
• ゲーム「レイトン教授と不思議な村」の130 番目のパズル「Too Many Queens 5」 (クイーンの問題 5 ) は 8 つのクイーンのパズルです。^{[ 32 ]}

• コスタス配列
• 数学ゲーム
• 数学パズル
• 3つ並びの問題なし
• ルーク多項式

• Bell, Jordan; Stevens, Brett (2009). " n-クイーン問題に関する既知の結果と研究分野の概観" . Discrete Mathematics . 309 (1): 1– 31. doi : 10.1016/j.disc.2007.12.043 .
• ワトキンス、ジョン・J. (2004). 『チェス問題の数学：チェス問題のすべて』プリンストン：プリンストン大学出版局。ISBN 978-0-691-11503-0。
• Allison, L.; Yee, CN; McGaughey, M. (1988). 「3次元NxNクイーン問題」 . オーストラリア、モナシュ大学コンピュータサイエンス学部。
• Nudelman, S. (1995). "高次元におけるモジュラーNクイーン問題" . Discrete Mathematics . 146 ( 1–3 ): 159–167 . doi : 10.1016/0012-365X(94)00161-5 .
• エンゲルハルト、M. (2010 年 8 月)。「Der Stammbaum der Lösungen des Damenproblems (ドイツ語で、8 クイーン問題の解決策の系統図を意味します)」 . Spektrum der Wissenschaft : 68–71 .
• 「高次元におけるモジュラー N クイーン問題について」、Ricardo Gomez、Juan Jose Montellano、Ricardo Strausz (2004)、Instituto de Matematicas、Area de la Investigacion Centifica、Circuito Exterior、Ciudad Universitaria、メキシコ。
• バッド、ティモシー（2002）。「ケーススタディ：8クイーンパズル」（PDF）。オブジェクト指向プログラミング入門（第3 版）。アディソン・ウェズリー・ロングマン。125 ～ 145ページ。ISBN  0-201-76031-2。
• Wirth, Niklaus (2004) [2012年更新]. 「8クイーン問題」.アルゴリズムとデータ構造(PDF) . Oberon版、修正および承認された変更あり。pp. 114–118 . 

• ワイススタイン、エリック・W. 「クイーンズ問題」 . MathWorld .
• queens-cpm on GitHub CP/M 用 Turbo Pascal による 8 クイーンパズル
• eight-queens.py （GitHub）エイトクイーンズパズルのPythonによる一行解法
• 100種類以上のプログラミング言語による解答（Rosetta Codeにて）