8つのクイーンのパズル

8 つのクイーンのパズルに対する唯一の対称的な解 (回転と反射まで )

8 つのクイーンパズルは、 8 ×8 のチェス盤に 8 つのチェスのクイーンを配置し、2 つのクイーンが互いに脅威にならないようにする問題です。したがって、解決するには、2 つのクイーンが同じ行、列、または対角線を共有しないようにする必要があります。解決法は 92 通りあります。この問題は、19 世紀半ばに初めて提起されました。現代では、さまざまなコンピュータプログラミング手法の例題としてよく使用されます。

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

歴史

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

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

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

解の構築と数え方ん= 8

8 クイーン問題のすべての解法を見つける問題は、計算コストがかなり高くなる可能性があります。8×8 の盤面には 8 つのクイーンの配置が 4,426,165,368 通りありますが、^{[a]解法は 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 つのクイーンが一直線上に並んでいないという追加の特性があります。

解決策の存在

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

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

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

n を6 で割った余りが 2 でも 3 でもない場合には、リストは単にすべての偶数の後にn以下のすべての奇数が続くものになります。
それ以外の場合は、偶数と奇数のリストを別々に書きます (2、4、6、8 - 1、3、5、7)。
余りが 2 の場合、奇数リストの 1 と 3 を入れ替え、5 を末尾に移動します( 3、1、7、5 )。
余りが 3 の場合、 2を偶数リストの末尾に移動し、1、3を奇数リストの末尾に移動します (4、6、8、2 – 5、7、9、1、3 )。
奇数リストを偶数リストに追加し、これらの番号で指定された行に左から右にクイーンを配置します (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$ $\times$ $n$ のボードにn 個のクイーンを配置する解の正確な数、つまり $n$ $\times$ $n$ クイーンのグラフにおけるサイズnの独立セットの数を求める公式は知られていない。27×27 のボードは、完全に列挙された最高次のボードである。^{[5]次の表は、}nクイーン問題に対する解の数を、すべての既知のケースについて、基本的な解（OEISのシーケンスA002562）とすべての解（OEISのシーケンスA000170）の両方で示している。

さらに、どの直線上にも 3 つのクイーンが存在しない配置の数が知られています( OEISのシーケンスA365437 )。 $n\leq 25$

漸近列挙

2021年にマイケル・シムキンは、大きな数nに対して、 nクイーン問題の解の数はおよそであることを証明しました。^[6] より正確には、解の数は漸近的に増加します。ここで、は1.939から1.945の間の定数です。^[7]（ここでo (1) は小さなo表記を表します。） $(0.143n)^{n}$ ${\mathcal {Q}}(n)$ ${\mathcal {Q}}(n)=((1\pm o(1))ne^{-\alpha })^{n}$ $\alpha$

代わりにドーナツ型のチェス盤（対角線が上端から下端、左端から右端に「巻き付く」もの）を考えると、n個のクイーンを盤上に配置できるのは次の場合のみである。この場合、漸近解の数は^[8]^{[9]である。} $n\times n$ $n\equiv 1,5\mod 6.$ $T(n)=((1+o(1))ne^{-3})^{n}.$

アルゴリズム設計の演習

8 個のクイーンパズルのすべての解を見つけることは、単純だが重要な問題の良い例です。このため、制約プログラミング、論理プログラミング、遺伝的アルゴリズムなどの非伝統的なアプローチを含むさまざまなプログラミング手法の例としてよく使用されます。ほとんどの場合、これは再帰アルゴリズムで解決できる問題の例として使用され、nクイーン問題を、 n × n のチェス盤にn −1 個のクイーンを配置する問題の任意の解に 1 個のクイーンを追加するという帰納的に表現します。帰納は、チェス盤に 0 個のクイーンを配置するという「問題」、つまり空のチェス盤の解で終わります。

このテクニックは、単純なブルートフォース検索アルゴリズムよりもはるかに効率的に使用できます。このアルゴリズムでは、8 個のクイーンの 64 ⁸ = 2 ⁴⁸ = 281,474,976,710,656 通りのブラインド配置をすべて検討し、これらをフィルタリングして、2 個のクイーンが同じマス目 (64!/56! = 178,462,987,637,760 通りの配置のみ残る) または相互に攻撃する位置に置かれる配置をすべて削除します。この非常に貧弱なアルゴリズムでは、とりわけ、8 個のクイーンの割り当てのさまざまな順列すべてで同じ結果が何度も生成され、各ソリューションのさまざまなサブセットに対して同じ計算が何度も繰り返されます。より優れたブルートフォースアルゴリズムでは、各行に 1 個のクイーンが配置されるため、ブラインド配置は 8 ⁸ = 2 ²⁴ = 16,777,216 通りのみになります。

これよりはるかに良い方法があります。あるアルゴリズムは、1 から 8 までの数字の順列 (8! = 40,320 通りあります) を生成して 8 つのルークのパズルを解き、各順列の要素をインデックスとして使用して各列にクイーンを配置します。次に、斜めの攻撃位置にあるボードを拒否します。

このアニメーションは、問題を解決するためのバックトラッキングを示しています。クイーンは、競合が発生しないことがわかっている列に配置されます。列が見つからない場合、プログラムは最後の正常な状態に戻り、別の列を試します。

バックトラッキング深さ優先探索プログラムは、順列法をわずかに改良したもので、一度に盤の 1 行を検討して探索木を構築し、構築の非常に早い段階でほとんどの非解決盤の位置を排除します。不完全な盤でもルークと対角攻撃を拒否するため、15,720 個のクイーン配置の可能性のみを調べます。さらに改良されたのは、順列ベースの方法と早期剪定方法を組み合わせることです。この方法では、5,508 個のクイーン配置の可能性のみを調べます。つまり、順列は深さ優先で生成され、部分的な順列によって対角攻撃が発生する場合は、探索空間が剪定されます。制約プログラミングも、この問題に非常に効果的です。

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

上で概説したバックトラック検索とは異なり、反復修復では解決策が保証されません。すべての貪欲な手順と同様に、局所最適値で行き詰まる可能性があります。(このような場合、アルゴリズムは異なる初期構成で再開される可能性があります。) 一方、深さ優先検索の範囲を数桁超える規模の問題を解決できます。

バックトラックの代わりに、有効な部分解を1行ずつ再帰的に列挙することで解を数えることができる。ボード全体の位置を構築するのではなく、ブロックされた対角線と列をビット演算で追跡する。これでは個々の解を復元することはできない。^[24]^[25]

サンプルプログラム

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

def  queens ( n :  int ,  i :  int ,  a :  list ,  b :  list ,  c :  list ): 
    if  i  <  n : 
        for  j  in  range ( n ): 
            if  j が aに含まれず 、i + jがbに含まれず、i - j がcに含まれない場合: yield from queens ( n , i + 1 , a + [ j ], b + [ i + j ], c + [ i - j ]) else : yield a               
                                 
    
         


 クイーンズ( 8,0 , [ ], [], [ ])の解 の場合: print (解)

大衆文化では

ゲーム「第7の客」では、スタウフ邸のゲームルームにある「第8のパズル：女王のジレンマ」が事実上の8人の女王のパズルである。^[28]^{: 48–49, 289–290}
ゲーム「レイトン教授と不思議な村」の130 番目のパズル「Too Many Queens 5」 (クイーンの問題 5 ) は 8 つのクイーンのパズルです。^[29]

参照

注記

^ 64 から 8 個の正方形の組み合わせの数は二項係数₆₄ C ₈です。
^ nの値が他の値の場合、他の対称性も可能です。たとえば、5×5 の盤上に 5 つの非攻撃クイーンを配置すると、その配置は盤自体の 90° 回転と等しくなります。このような解法には、2 つのバリエーション (それ自体とその反射) しかありません。n > 1 の場合、解法がそれ自体の反射と等しくなることは不可能です。なぜなら、そのためには 2 つのクイーンが互いに向き合う必要があるからです。

参考文献

^ ab WW Rouse Ball (1960)「8人のクイーンの問題」、Mathematical Recreations and Essays、Macmillan、ニューヨーク、pp. 165–171。
^ O.-J. Dahl、EW Dijkstra、CAR Hoare Structured Programming、Academic Press、ロンドン、1972年ISBN 0-12-200550-3、pp. 72–82。
^ abc Bo Bernhardsson (1991). 「すべての N に対する N-クイーン問題の明示的解」. ACM SIGART 速報. 2 (2): 7. doi :10.1145/122319.122322. S2CID 10644706.
^ Hoffman, EJ; Loessi, JC; Moore, RC (1969年3月1日). 「mクイーンズ問題の解決のための構成」.数学雑誌. 42 (2): 66. doi :10.2307/2689192. JSTOR 2689192.2016年11月8日にWayback Machineにアーカイブされました
^ Q27プロジェクト
^ スロマン、レイラ（2021年9月21日）。「数学者がクイーンの攻撃に関するチェスの問題に答える」。クアンタマガジン。 2021年9月22日閲覧。
^ Simkin, Michael (2021年7月28日). 「$n$-クイーン構成の数」. arXiv : 2107.13460v2 [math.CO].
^ Luria, Zur (2017年5月15日). 「n-クイーン構成の数に関する新しい境界」. arXiv : 1705.05225v2 [math.CO].
^ バウテル、カンジダ;ピーター・キーヴァシュ（2021年9月16日）。「$n$-クイーンズ問題」。arXiv : 2109.08083v1 [math.CO]。
^ J. BarrとS. Rao (2006)、「高次元におけるnクイーン問題」、Elemente der Mathematik、vol 61 (4)、pp. 133–137。
^ Martin S. Pearson. 「チェス盤上のクイーン - 2次元を超えて」(php) . 2020年1月27日閲覧。
^チャタム、ダグ（2018年12月1日）。「n + kドラゴンキング問題に関する考察」レクリエーション数学マガジン。5 （10）：39–55。doi ： 10.2478 / rmm -2018-0007。
^ G. Pólya、Uber die "doppelt-periodischen" Losungen des n-Damen-問題、George Pólya: 論文集 Vol. 2 IV、GC。 Rota 編、MIT Press、ケンブリッジ、ロンドン、1984 年、237 ～ 247 ページ
^ Burger, AP; Cockayne, EJ; Mynhardt, CM (1997)、「クイーンズグラフにおける支配と冗長性」、離散数学、163 (1–3): 47–66、doi :10.1016/0012-365X(95)00327-S、hdl : 1828/2670、MR 1428557
^ ウィークリー、ウィリアム・D. (2018)、「25年間で世界中の女王」、ゲラ、ラルッカ、テレサ・W.ヘインズ、スティーブン・T.ヘデトニエミ（編）、グラフ理論：お気に入りの予想と未解決の問題– 2、数学の問題集、チャム：シュプリンガー、pp. 43–54、doi：10.1007 / 978-3-319-97686-0_5、ISBN 978-3-319-97684-6、MR 3889146
^ 「クイーンズとナイトの問題」。2005年10月16日時点のオリジナルよりアーカイブ。 2005年9月20日閲覧。
^ベル、ジョーダン; スティーブンス、ブレット (2009)。「n-クイーンの既知の結果と 研究分野の調査」。離散数学。309 (1): 1–31。doi : 10.1016/ j.disc.2007.12.043。
^ O. Demirörs、N. Rafraf、MM Tanik。魔方陣からn-クイーン解を得ることと、n-クイーン解から魔方陣を構築すること。レクリエーション数学ジャーナル、24:272–280、1992年
^ Gent, Ian P.; Jefferson, Christopher; Nightingale, Peter (2017年8月). 「n-Queens Completionの複雑性」. Journal of Artificial Intelligence Research . 59 : 815–848. doi : 10.1613/jair.5512 . hdl : 10023/11627 . ISSN 1076-9757 . 2017年9月7日閲覧。
^ Glock, Stefan; Correia, David Munhá; Sudakov, Benny (2022年7月6日). 「n-クイーン補完問題」.数学科学研究. 9 (41): 41. doi : 10.1007/s40687-022-00335-1 . PMC 9259550 . PMID 35815227. S2CID 244478527.
^ Rok Sosic と Jun Gu による「N クイーン問題に対する多項式時間アルゴリズム」(1990 年)。メモリの制約により実行できる最大数である 500,000 クイーンまでの実行時間について説明します。
^ スティーブン・ミントン、マーク・D・ジョンストン、アンドリュー・B・フィリップス、フィリップ・レアード（1992年12月1日）。「競合の最小化：制約充足とスケジュール問題のためのヒューリスティック修復法」人工知能。58 （ 1）：161–205。doi ：10.1016/0004-3702（92）90007- K。hdl：2060 / 19930006097。ISSN 0004-3702。S2CID 14830518 。
^ Sosic, R.; Gu, Jun (1994 年 10 月)。「競合を最小化する効率的なローカル検索: n クイーン問題のケーススタディ」IEEE Transactions on Knowledge and Data Engineering 6 ( 5): 661–668. doi :10.1109/69.317698. ISSN 1558-2191。
^ Qiu, Zongyan (2002年2月). 「n-queen問題のビットベクトル符号化」. ACM SIGPLAN Notices . 37 (2): 68–70. doi :10.1145/568600.568613.
^ Richards, Martin (1997). ビットパターンと再帰を使用した MCPL のバックトラッキングアルゴリズム(PDF) (技術レポート). ケンブリッジ大学コンピュータ研究所. UCAM-CL-TR-433.
^ Wirth, Niklaus (1976).アルゴリズム + データ構造 = プログラム. Prentice-Hall シリーズ自動計算. Prentice-Hall. Bibcode :1976adsp.book.....W. ISBN 978-0-13-022418-7。145ページ
^ Wirth, Niklaus (2012) [原著 2004]. 「8人のクイーンの問題」. アルゴリズムとデータ構造(PDF) . 訂正と承認された変更を加えたOberonバージョン。pp. 114–118。
^ DeMaria, Rusel (1993年11月15日). The 7th Guest: The Official Strategy Guide (PDF) . Prima Games. ISBN 978-1-5595-8468-5. 2021年4月22日閲覧。
^ “ナゾ130 クイーンの問題5”.ゲームの匠. 2021 年9 月 17 日に取得。

さらに読む

Bell, Jordan; Stevens, Brett (2009). 「n-クイーンの既知の結果と研究分野の調査」.離散数学. 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クイーン問題」.離散数学. 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、メキシコ。
Budd, Timothy (2002)。「ケーススタディ: 8 つのクイーンのパズル」(PDF)。オブジェクト指向プログラミング入門 (第 3 版)。Addison Wesley Longman。pp. 125–145。ISBN 0-201-76031-2。
Wirth, Niklaus (2004) [2012 年更新]。「8 人のクイーンの問題」。アルゴリズムとデータ構造(PDF)。修正と承認された変更を加えた Oberon バージョン。pp. 114–118。

外部リンク

Weisstein、Eric W.「クイーンズ問題」。MathWorld。
queens-cpm on GitHub CP/M 用 Turbo Pascal の 8 つのクイーンパズル
GitHubの eight-queens.py Python での 8 つのクイーンのパズルの 1 行の解決
100 を超えるさまざまなプログラミング言語でのソリューション ( Rosetta Code上)

[3] 64 から 8 個の正方形の組み合わせの数は二項係数₆₄ C ₈です。

[4] の値が他の値の場合、他の対称性も可能です。たとえば、5×5 の盤上に 5 つの非攻撃クイーンを配置すると、その配置は盤自体の 90° 回転と等しくなります。このような解法には、2 つのバリエーション (それ自体とその反射) しかありません。n > 1 の場合、解法がそれ自体の反射と等しくなることは不可能です。なぜなら、そのためには 2 つのクイーンが互いに向き合う必要があるからです。

[rouse_ball_1960-1] WW Rouse Ball (1960)「8人のクイーンの問題」、Mathematical Recreations and Essays、Macmillan、ニューヨーク、pp. 165–171。

[2] O.-J. Dahl、EW Dijkstra、CAR Hoare Structured Programming、Academic Press、ロンドン、1972年ISBN 0-12-200550-3、pp. 72–82。

[bernhardsson-5] Bo Bernhardsson (1991). 「すべての N に対する N-クイーン問題の明示的解」. ACM SIGART 速報. 2 (2): 7. doi :10.1145/122319.122322. S2CID 10644706.

[6] Hoffman, EJ; Loessi, JC; Moore, RC (1969年3月1日). 「mクイーンズ問題の解決のための構成」.数学雑誌. 42 (2): 66. doi :10.2307/2689192. JSTOR 2689192.2016年11月8日にWayback Machineにアーカイブされました

[7] Q27プロジェクト

[8] スロマン、レイラ（2021年9月21日）。「数学者がクイーンの攻撃に関するチェスの問題に答える」。クアンタマガジン。 2021年9月22日閲覧。

[9] Simkin, Michael (2021年7月28日). 「$n$-クイーン構成の数」. arXiv : 2107.13460v2 [math.CO].

[10] Luria, Zur (2017年5月15日). 「n-クイーン構成の数に関する新しい境界」. arXiv : 1705.05225v2 [math.CO].

[11] バウテル、カンジダ;ピーター・キーヴァシュ（2021年9月16日）。「$n$-クイーンズ問題」。arXiv : 2109.08083v1 [math.CO]。

[12] J. BarrとS. Rao (2006)、「高次元におけるnクイーン問題」、Elemente der Mathematik、vol 61 (4)、pp. 133–137。

[13] Martin S. Pearson. 「チェス盤上のクイーン - 2次元を超えて」(php) . 2020年1月27日閲覧。

[14] ^チャタム、ダグ（2018年12月1日）。「n + kドラゴンキング問題に関する考察」レクリエーション数学マガジン。5 （10）：39–55。doi ： 10.2478 / rmm -2018-0007。

[15] G. Pólya、Uber die "doppelt-periodischen" Losungen des n-Damen-問題、George Pólya: 論文集 Vol. 2 IV、GC。 Rota 編、MIT Press、ケンブリッジ、ロンドン、1984 年、237 ～ 247 ページ

[16] Burger, AP; Cockayne, EJ; Mynhardt, CM (1997)、「クイーンズグラフにおける支配と冗長性」、離散数学、163 (1–3): 47–66、doi :10.1016/0012-365X(95)00327-S、hdl : 1828/2670、MR 1428557

[17] ウィークリー、ウィリアム・D. (2018)、「25年間で世界中の女王」、ゲラ、ラルッカ、テレサ・W.ヘインズ、スティーブン・T.ヘデトニエミ（編）、グラフ理論：お気に入りの予想と未解決の問題– 2、数学の問題集、チャム：シュプリンガー、pp. 43–54、doi：10.1007 / 978-3-319-97686-0_5、ISBN 978-3-319-97684-6、MR 3889146

[18] 「クイーンズとナイトの問題」。2005年10月16日時点のオリジナルよりアーカイブ。 2005年9月20日閲覧。

[19] ^ベル、ジョーダン; スティーブンス、ブレット (2009)。「n-クイーンの既知の結果と 研究分野の調査」。離散数学。309 (1): 1–31。doi : 10.1016/ j.disc.2007.12.043。

[20] O. Demirörs、N. Rafraf、MM Tanik。魔方陣からn-クイーン解を得ることと、n-クイーン解から魔方陣を構築すること。レクリエーション数学ジャーナル、24:272–280、1992年

[21] Gent, Ian P.; Jefferson, Christopher; Nightingale, Peter (2017年8月). 「n-Queens Completionの複雑性」. Journal of Artificial Intelligence Research . 59 : 815–848. doi : 10.1613/jair.5512 . hdl : 10023/11627 . ISSN 1076-9757 . 2017年9月7日閲覧。

[22] Glock, Stefan; Correia, David Munhá; Sudakov, Benny (2022年7月6日). 「n-クイーン補完問題」.数学科学研究. 9 (41): 41. doi : 10.1007/s40687-022-00335-1 . PMC 9259550 . PMID 35815227. S2CID 244478527.

[23] Rok Sosic と Jun Gu による「N クイーン問題に対する多項式時間アルゴリズム」(1990 年)。メモリの制約により実行できる最大数である 500,000 クイーンまでの実行時間について説明します。

[24] スティーブン・ミントン、マーク・D・ジョンストン、アンドリュー・B・フィリップス、フィリップ・レアード（1992年12月1日）。「競合の最小化：制約充足とスケジュール問題のためのヒューリスティック修復法」人工知能。58 （ 1）：161–205。doi ：10.1016/0004-3702（92）90007- K。hdl：2060 / 19930006097。ISSN 0004-3702。S2CID 14830518 。

[25] Sosic, R.; Gu, Jun (1994 年 10 月)。「競合を最小化する効率的なローカル検索: n クイーン問題のケーススタディ」IEEE Transactions on Knowledge and Data Engineering 6 ( 5): 661–668. doi :10.1109/69.317698. ISSN 1558-2191。

[26] Qiu, Zongyan (2002年2月). 「n-queen問題のビットベクトル符号化」. ACM SIGPLAN Notices . 37 (2): 68–70. doi :10.1145/568600.568613.

[27] Richards, Martin (1997). ビットパターンと再帰を使用した MCPL のバックトラッキングアルゴリズム(PDF) (技術レポート). ケンブリッジ大学コンピュータ研究所. UCAM-CL-TR-433.

[28] Wirth, Niklaus (1976).アルゴリズム + データ構造 = プログラム. Prentice-Hall シリーズ自動計算. Prentice-Hall. Bibcode :1976adsp.book.....W. ISBN 978-0-13-022418-7。145ページ

[29] Wirth, Niklaus (2012) [原著 2004]. 「8人のクイーンの問題」. アルゴリズムとデータ構造(PDF) . 訂正と承認された変更を加えたOberonバージョン。pp. 114–118。

[30] DeMaria, Rusel (1993年11月15日). The 7th Guest: The Official Strategy Guide (PDF) . Prima Games. ISBN 978-1-5595-8468-5. 2021年4月22日閲覧。

[31] “ナゾ130 クイーンの問題5”.ゲームの匠. 2021 年9 月 17 日に取得。

歴史