エイト・クイーン

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

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

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

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

例Aではどの駒も他の駒に取られない位置にあるので正しい配置。例Bではの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までの解は次の通り。

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

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

出典

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

チェス
パズル