エイト・クイーン

エイト・クイーンとは、チェスの盤とコマを使用したパズルの名称である。

 ルール 
チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。

クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。将棋の飛車と角行を合わせた動きである。

4駒で簡略に解説すると、

例Aではどの駒も他の駒に取られない位置にあるので正しい配置。例Bでは20pxの2駒が互いに取られる位置にあるので誤った配置となる。

 歴史 
このパズルは、1848年にチェスプレイヤーのマックス・ベッツェルによって提案された。ガウスを含む多くの数学者がこの問題に挑戦した。1874年に Gunther が行列式を用いて解く方法を提案し、イギリスのグレイシャー (en:Glaisher) が全解が12個であることを確認した。

 解 
基本解は12種類ある。下記の解1〜11は、回転と鏡像でそれぞれ8種類の変形がある。解12は点対称なので、4種類の変形しかない。したがって、解の総数は 92（＝8×11＋4）になる。

 クイーン 
一辺のマスをとした変形版を「クイーン」パズルという。例えば「4-クイーン」では4×4のマスで4個の駒を使用する（他にも縦横比が1:1ではない矩形や、ペグ・ソリティアの盤面、不定形などいろいろ考えられるがここでは言及しない）。
 2-クイーンと3-クイーンには解がない。
 4-クイーン以上なら一辺のマス数に等しい数のクイーンが置ける。
単純に見てが増えるのに従って、全マス数個に対し置く駒の数は個であるから、置ける場所（の候補）の増え方により、解の数には組合せ爆発が起きる（ただしが5から6に増える場合は解の数が減少する）。2009年にドレスデン工科大学で26-クイーンが計算された。現在すべての解が判明している最大のものは、2016年にQ27 Projectによって計算された27-クイーンである。
=27までの解は次の通り。

基本解バリエーション解11120030041252106147640812929463521092724113412 680121 78714 200139 23373 7121445 752365 59615285 0532 279 184161 846 95514 772 5121711 977 93995 815 1041883 263 591666 090 62419621 012 7544 968 057 848204 878 666 80839 029 188 8842139 333 324 973314 666 222 71222336 376 244 0422 691 008 701 644233 029 242 658 21024 233 937 684 4402428 439 272 956 934227 514 171 973 73625275 986 683 743 4342 207 893 435 808 352262 789 712 466 510 28922 317 699 616 364 0442729 363 791 967 678 199234 907 967 154 122 528

大衆文化
コンピューターゲームので、ヘンリー・ストーフの屋敷のゲームルームに、ザ・クイーンズ・ジレンマ（The Queen's Dilemma）という8番目のパズルがある、このパズルは、事実上のエイト・クイーンのパズルである。
ニンテンドーDS用ゲームのレイトン教授と不思議な町で、物語の結末を知る者の部屋にある「クイーンの問題5」という130番目のナゾは、事実上エイト・クイーンのパズルである。

 関連項目 
 力まかせ探索
 バックトラッキング
 数学パズル
 利かずの駒並べ

 出典 

 外部リンク 
NQueens Project 「n-クイーン」パズルの解を求める分散コンピューティング 
General method n queens with implementation in java
8Queens in C,Java,C++

Category:チェス
Category:パズル